【C++】STL有序关联容器的双生花：set/multiset 和 map/multimap 使用指南
🔥拾Ծ光：个人主页👨🏻💻
👏👏👏欢迎来到我的专栏:
🎉《C++》
📌《数据结构》
💡《C语言》
目录
1.7、区间查找——lower_bound/upper_bound
前言：
“你有没有遇到过这样的需求：需要快速查找一组数据中的唯一元素，或者统计某个键出现的次数？在C++中，如果用数组或列表手动实现，不仅代码冗长，效率还低。而STL（标准模板库）中的关联容器——set、multiset、map 和 multimap，正是为解决这类问题而生的。本文将带你从零掌握它们的用法，告别低效的手动实现！”
⭐️⭐️⭐️文档直达：《set容器》，《multiset容器》，《map容器》，《multimap容器》
1、set容器
常用接口说明：
1.1、构造函数——constructor
最常用的就是上面的三种构造函数，构造方式如下：
void test01() { vector<int> v({ 4,5,2,9,6,8,3,1,7,7,7,7 }); set<int> st1(v.begin(), v.end()); // 迭代器区间构造 set<int> st2(st1); // 拷贝构造 set<int> st3({ 4,5,2,9,6,8,3,1,7,7,7,7 }); // 初始化列表构造 }1.2、迭代器——iterator
begin()和end() 最常用，都是结合在一些其他场景使用，比如，遍历set对象，或者用于迭代器区间构造等场景。由于set底层特殊的数据结构，begin返回的迭代器指向最小的元素。
void test02() { set<int> st({ 4,5,2,9,6,8,3,1,7,7,7,7 }); // 初始化列表构造 auto begin = st.begin(); // 返回第一个节点的迭代器 auto end = st.end(); // 返回最后一个节点后一个位置的迭代器 cout << *begin << endl; cout << *(--end) << endl; // --end找到最后一个有效节点 }
我们可以用迭代器实现一个打印函数，方便我们后面观察
1.3、插入——insert
set底层的数据结构就是平衡二叉搜索树（红黑树），所以插入数据满足二叉搜索树的规则，但是，set不允许插入相同的值。插入数据的形式也比较多，最常用的就是上面的第一种。我们看到，对于第一种插入数据的接口，最特别的就是它的返回值，这和我们以前见到的都不一样。其实它的返回值pair类类型的对象。其中pair对象的第一个值为迭代器，如果要插入的值原来不存在，则返回新插入节点的迭代器，如果原来存在，则返回值与val相等的那个节点；第二个值为bool类型的变量。下面就是pair类：
然后我们插入数据来观察一下：
void test03() { set<int> st; pair<set<int>::iterator, bool> p1,p2; // 创建pair对象,记下插入数据后的返回值 // 插入数据 p1 = st.insert(5); st.insert(3); p2 = st.insert(5); // 插入原来已经存在的值 cout << *(p1.first) << endl; // 检查pair对象的第一个值是否为插入节点的迭代器 if (p2.second) cout << "原来不存在" << endl; else cout << "原来存在" << endl; }
通过打印结果，pair对象p1的first指向插入节点的迭代器；当插入值相等的节点时，pair对象的second的值为false，则打印出原来存在。
1.4、删除——erase
void test04() { set<int> st({ 4,5,2,9,6,8,3,1,7,7,7,7 }); // 初始化列表构造 Print_container(st); set<int>::iterator it = st.erase(st.begin()); // 删除第一个节点 cout << *it << endl; }
当删除第一个节点之后，erase函数返回该节点后一个节点的迭代器，要删除节点的迭代器失效。
1.5、查找——find
找到就返回节点的迭代器，没找到就返回set::end()。
void test05() { set<int> st({ 4,5,2,9,6,8,3,1,7,7,7,7 }); // 初始化列表构造 auto it = st.find(5); if(it!=st.end()) { cout << *it << endl; } }1.6、统计指定节点个数——count
由于set不允许插入相同的值，所以存在就返回1，反之返回0。所以，count也可以用来查找元素。
void test06() { set<int> st({ 4,5,2,9,6,8,3,1,7,7,7,7 }); // 初始化列表构造 cout << st.count(5) << endl; cout << st.count(50) << endl; }
1.7、区间查找——lower_bound/upper_bound
// 删除区间内的值 void test07() { set<int> st1({ 20,10,50,30,10,90,70,40,80 }); Print_container(st1); // 删除[30,50) auto begin1 = st1.find(30); auto end1 = st1.find(50); while (begin1 != end1) { begin1 = st1.erase(begin1); } Print_container(st1); // 10 20 50 70 80 90 // 删除[30,50] // lower_bound/upper_bound set<int> st2({ 20,10,50,30,10,90,70,40,80 }); Print_container(st2); auto begin2 = st2.lower_bound(30); auto end2 = st2.upper_bound(50); while (begin2 != end2) { begin2 = st2.erase(begin2); } Print_container(st2); // 10 20 70 80 90 }lower_bound和upper_bound还有一个优势：可以根据set中不存在的值来确定区间。
2、multiset容器
multiset容器相比于set容器，不同点就在与其支持插入相同的值，其他方面与set完全一样。由于multiset支持插入相同的值，所以，其有一部分的接口与set略有所差异，比如，查找val时多个节点的值与val相等，那么该返回哪一个；对于有相同值的节点删除时应该删掉哪一个；count统计节点个数时返回值可能大于1等。
常用接口说明：
2.1、插入——insert
void test1() { multiset<int> multi; multi.insert(3); multi.insert(2); multi.insert(3); multi.insert(3); Print_container(multi); }
2.2、查找——find
当有相同的值时，find返回中序遍历得到的序列中的第一个。
我们做一个实验验证一下：
只有当find返回中序遍历的序列的第一个3的节点的迭代器时，才能完整打印出所有的3。
2.3、删除——erase
与set容器的erase函数基本相同，只是，当multiset的erase函数删除重复的节点时，会一次将所有具有相同值的节点全部删除。
2.4、统计节点个数——count
void test4() { multiset<int> multi; multi.insert(3); multi.insert(3); multi.insert(3); multi.insert(3); Print_container(multi); cout << multi.count(3); }
2.5、返回相同节点的迭代器区间——equal_range
3、map容器
常用接口说明：
map的常用接口其实与set差别不大，因为map执行查找，删除，统计节点个数，区间查找（lower_bound/upper_bound），以及equal_range都是根据其键值来完成的，与映射值无关，这一点与set容器完全一致，并没有什么较大的差异，除了insert插入时可能需要更新映射值等一些小差异。
3.1、构造函数——constructor
3.2、插入——insert
最常用的就是第一个函数，它的返回值pair类类型的对象。其中pair对象的第一个值为迭代器，如果要插入的值原来不存在，则返回新插入节点的迭代器，如果原来存在，则返回值与val相等的那个节点；第二个值为bool类型的变量。
map对象应该有一个键值和映射值，那么应该怎么插入呢？
我们在前面已经介绍了pair类，而pair对象恰好有两个值，所以我们可以用键值和映射值构造pair对象，然后插入。
void test01() { map<string, string> dict1; pair<string, string> p("first", "第一"); // 构造pair对象 dict1.insert(p); // 插入 dict1.insert(pair<string, string>("second", "第二")); // 构造匿名对象 // 隐式类型转化（单参数/多参数） dict1.insert({ "third", "第三" }); // make_pair dict1.insert(make_pair("forth", "第四")); // 初始化列表 map<string, string> dict2 = { {"left", "左边"}, {"right", "右边"}, {"insert", "插入"},{ "string", "字符串" } }; Print_Container(dict1); Print_Container(dict2); }当插入新节点的键值相等，映射值不会更新。
3.3、operator[ ]
map::operator[ ]可以向map对象中插入数据，当要插入的数据map对象中不存在时，直接插入；当原来已经存在时，可以修改映射值；若插入数据时不给定映射值，则映射值采用默认值。所以可以看出，operator[ ] 具有 查找 + 插入 + 修改映射值的功能。 operator[ ] 的返回值是mapped_type类型的引用，通过查看文档，mapped_type其实就是映射值的类型，所以，operator[ ] 返回一个节点的映射值。
void test_4() { map<string, string> dict; dict.insert({ "left", "左边" }); dict.insert(make_pair("right", "右边")); // 原来不存在的：查找+插入 dict["sort"]; // 查找+插入+修改 dict["string"] = "字符串"; // 查找+修改 dict["left"] = "左边的"; // 测试返回值 auto it = dict["left"]; cout << it << endl; }
返回了left节点的映射值。
实现一个打印函数，方便观察
这里有一个map常见的场景：当我们想要统计一串字符串中元素的出现次数，就可以将元素作为键值，将出现次数作为映射值，利用operator[ ] 有查找+插入+修改功能和返回映射值的特点来统计出现次数。
4、multimap容器
multimap几乎与map一样，只是multimap支持插入相同键值的节点，即节点的值能重复。下面通过两个接口函数来感受一下
4.1、插入——insert
void Test01() { multimap<string, string> mp; mp.insert(make_pair("left", "左边")); mp.insert(make_pair("left", "左边")); mp.insert(make_pair("left", "左边")); Print_Container(mp); }
4.2、删除——erase
void Test02() { multimap<string, string> mp; mp.insert(make_pair("left", "左边")); mp.insert(make_pair("left", "左边")); mp.insert(make_pair("left", "左边")); mp.erase("left"); Print_Container(mp); }
