【c++】set和map的使用
🔥个人主页：Quitecoder
🔥专栏：c++笔记仓
目录
- 1. 关联式容器
- 2. 键值对
- 3. 树形结构的关联式容器
- `3.1 set`
- 3.1.1 set的使用
- `lower_bound`
- `upper_bound`
- 3.2 map
- 3.2.1 map的使用
- `operator[]`
- multiset
- multimap
1. 关联式容器
在初阶阶段，我们已经接触过STL中的部分容器，比如：vector、list、deque。forward_list(C++11)等，这些容器统称为序列式容器，因为其底层为线性序列的数据结构，里面
存储的是元素本身。那什么是关联式容器？它与序列式容器有什么区别？
关联式容器也是用来存储数据的，与序列式容器不同的是，其里面存储的是结构的
键值对，在数据检索时比序列式容器效率更高
2. 键值对
用来表示具有一一对应关系的一种结构，该结构中一般只包含两个成员变量key和value，key代
表键值，value表示与key对应的信息。比如：现在要建立一个英汉互译的字典，那该字典中必然
有英文单词与其对应的中文含义，而且，英文单词与其中文含义是一一对应的关系，即通过该应
该单词，在词典中就可以找到与其对应的中文含义
template struct pair { typedef T1 first_type; typedef T2 second_type; T1 first; T2 second; pair() : first(T1()), second(T2()) {} pair(const T1& a, const T2& b) : first(a), second(b) {} };3. 树形结构的关联式容器
根据应用场景的不桶，STL总共实现了两种不同结构的管理式容器：树型结构与哈希结构。树型结构的关联式容器主要有四种：map、set、multimap、multiset。这四种容器的共同点是：使用平衡搜索树(即红黑树)作为其底层结果，容器中的元素是一个有序的序列。下面一依次介绍每一个容器
3.1 set
- . set是按照一定次序存储元素的容器
- . 在set中，元素的value也标识它(value就是key，类型为T)，并且每个value必须是唯一的。set中的元素不能在容器中修改(元素总是const)，但是可以从容器中插入或删除它们。
- . 在内部，set中的元素总是按照其内部比较对象(类型比较)所指示的特定严格弱排序准则进行排序。
- . set容器通过key访问单个元素的速度通常比unordered_set容器慢，但它们允许根据顺序对子集进行直接迭代。
- . set在底层是用二叉搜索树(红黑树)实现的
注意：
- 与map/multimap不同，map/multimap中存储的是真正的键值对，set中只放
value，但在底层实际存放的是由构成的键值对。
- set中插入元素时，只需要插入value即可，不需要构造键值对。
- set中的元素不可以重复(因此可以使用set进行去重)。
- 使用set的迭代器遍历set中的元素，可以得到有序序列
- set中的元素默认按照小于来比较
- set中查找某个元素，时间复杂度为： l o g 2 n log_2 n log2n
- set中的元素不允许修改
- set中的底层使用二叉搜索树(红黑树)来实现
3.1.1 set的使用
- T: set中存放元素的类型，实际在底层存储的键值对。
- Compare：set中元素默认按照小于来比较
- Alloc：set中元素空间的管理方式，使用STL提供的空间配置器管理
构造函数：
（1）：构造空的set
（2）：用[first, last)区间中的元素构造set
（3）：set的拷贝构造
迭代器：
容量：
对元素修改：
在set中插入元素x，实际插入的是构成的键值对，如果插入成功，返回,如果插入失败，说明x在set中已经存在，返回
（1）：删除set中position位置上的元素
（2）：删除set中值为x的元素，返回删除的元素的个数
（3）：删除set中[first, last)区间中的元素
交换set中的元素
将set中的元素清空
返回set中值为x的元素的位置
返回set中值为x的元素的个数
在C++中，set 是基于红黑树实现的一个关联容器，它存储有序的不重复元素。这意味着 set 内部元素默认是按照升序排列的，且每个元素值都是唯一的。
set 提供了两个非常有用的成员函数，lower_bound 和 upper_bound，它们用于在有序容器中查找特定元素范围的迭代器。
lower_bound
lower_bound 函数返回一个指向当前set中不小于给定值的第一个元素的迭代器。如果给定值在set中不存在，它将返回指向下一个更大的元素的迭代器；如果给定值大于set中的任何元素，它将返回指向set末尾的迭代器。
换句话说，lower_bound 返回的是指向set中第一个不小于（即大于等于）给定值的元素的迭代器
用法示例:
std::set s; s.insert(1); s.insert(3); s.insert(5); auto it_lower = s.lower_bound(3); // it_lower 现在指向元素 3 auto it_lower2 = s.lower_bound(4); // it_lower2 现在指向元素 5
upper_bound
upper_bound 函数返回一个指向当前set中大于给定值的第一个元素的迭代器。如果所有的元素都小于给定值，它将返回指向set末尾的迭代器。
upper_bound 返回的是指向set中第一个大于给定值的元素的迭代器。
用法示例:
std::set s; s.insert(1); s.insert(3); s.insert(5); auto it_upper = s.upper_bound(3); // it_upper 现在指向元素 5 auto it_upper2 = s.upper_bound(5); // it_upper2 现在指向 set 的末尾
注意点
- lower_bound 和 upper_bound 如果给定值不存在于set中，它们不会向 set 添加元素。
- 这两个函数同样适用于 multiset 和 map，multimap 等关联容器，其行为是类似的。
- 它们的返回类型是对应容器的迭代器（或const迭代器，取决于容器实例是否是const）。
- 它们的时间复杂度通常是对数复杂度，也就是O(log n)，因为set背后的数据结构是红黑树，它是一种自平衡的二叉搜索树。
在处理范围查询或是在有序集合中寻找下界或上界时，lower_bound 和 upper_bound 函数非常有用
3.2 map
- map是关联容器，它按照特定的次序(按照key来比较)存储由键值key和值value组合而成的元
素。
- 在map中，键值key通常用于排序和惟一地标识元素，而值value中存储与此键值key关联的
内容。键值key和值value的类型可能不同，并且在map的内部，key与value通过成员类型value_type绑定在一起，为其取别名称为pair:typedef pair value_type;
- 在内部，map中的元素总是按照键值key进行比较排序的。
- map中通过键值访问单个元素的速度通常比unordered_map容器慢，但map允许根据顺序对元素进行直接迭代(即对map中的元素进行迭代时，可以得到一个有序的序列)。
- map支持下标访问符，即在[]中放入key，就可以找到与key对应的value。
- map通常被实现为二叉搜索树(平衡二叉搜索树(红黑树))
3.2.1 map的使用
大部分都与map相同，这里只看特殊的：
这里的key是不能修改的，用pair键值对存储
这里insert插入的是一个键值对，我们来使用一下：
void test_map1() { map dict; pair kv1("banana", "香蕉"); dict.insert(kv1); dict.insert(pair("left", "左边")); dict.insert(make_pair("apple", "苹果")); dict.insert({ "right" ,"右边" }); }方法1: 使用pair对象直接插入
std::pair kv1("banana", "香蕉"); dict.insert(kv1);这里，首先创建了一个名为kv1的pair对象，包含键“banana”和值“香蕉”。然后使用insert方法将其插入到dict中
方法2: 使用构造函数构造pair直接插入
dict.insert(std::pair("left", "左边"));这里直接使用std::pair的构造函数创建了一个匿名的pair对象，并将它插入到dict中。这个pair对象包含键“left”和值“左边”。
方法3: 使用make_pair创建pair直接插入
dict.insert(std::make_pair("apple", "苹果"));在此，std::make_pair函数模板被用来创建一个匿名的pair对象，并直接插入到dict中。这个pair对象包含键“apple”和值“苹果”。make_pair有助于减少冗长的类型名称，因为模板类型参数会被自动推导
make_pair返回值为pair类型
第四种插入方式：
dict.insert({ "right" ,"右边" });不是初始化列表（initializer list）的标准用法，这里是构造函数的隐式类型转换。这种方式实际上利用了std::pair的构造函数，它能接收两个参数并将它们转换为一个pair对象。因为std::map的insert方法重载接收一个std::pair类型的对象，编译器可以通过构造函数隐式类型转换，从提供的两个值创建一个pair对象。
map初始化列表使用：
mapdict2 = { {"banana", "香蕉"},{"left", "左边"} };我们遍历上面的dict：
错误方法：
auto it = dict.begin(); while (it != dict.end()) { cout //std::cout string arr[] = { "苹果", "西瓜", "苹果", "西瓜", "苹果", "苹果", "西瓜", "苹果", "香蕉", "苹果", "香蕉","苹果","草莓", "苹果","草莓" }; map countMap[e]++; //auto it = countMap.find(e); //if (it != countMap.end()) //{ // it-second++; //} //else //{ // //const pair cout 1, "one"}); if (result.second) { // 插入成功，result.first 指向新插入的元素 } else { // 插入失败，result.first 指向现存相同键的元素 } std::multiset std::cout std::multimap std::cout std::cout public: class comp{ public: bool operator()(pair return (p1.secondp2.second)||(p1.second==p2.second&&p1.first map m1[word]++; } vector v2.push_back(v1[i].first); } return v2; } };
- 与map/multimap不同，map/multimap中存储的是真正的键值对，set中只放
