C++:set/multiset和map/multimap文档详细解析
Hello大家好！ 很高兴与大家见面！ 给生活添点快乐，开始今天的编程之路。
我的博客:<但愿.
我的专栏:C语言、题目精讲、算法与数据结构、C++
欢迎点赞，关注
目录
前言
一 容器的分类(根据容器中各个数据之间的关系）
1.1序列式容器
1.1.1序列式容器的概念
1.1.2序列式容器的例子
1.2关联式容器
1.2.1关联式容器的概念
1.2.2关联式容器的例子
二 set/multiset
2.1参考文档(multiset包在set中所以其没有头文件）
2.2set类的介绍
2.2.1set类的实现的简单介绍
2.2.2set类的接口介绍
2.2.2.1set类构造接口
2.2.2.2set类的迭代器接口
2.2.2.3set类的find接口(查找）
2.2.2.3.1set类的find接口(查找）的解析
2.2.2.3.2算法库中的查找函数和set类的find接口(查找）的对比
2.2.2.4set类的erase接口(删除）
2.2.2.5set类的count接口(判断一个值是否存在）
2.2.2.6set类的lower_boundt接口和upper_bound接口(找边界)
2.2.3multiset类的接口介绍
2.2.3.1multiset类的find接口(查找)
2.2.3.2multiset类的cound接口(判断是否存在)
2.2.3.3multiset类的erase接口(删除)
2.2.4set/multiset的总结
三 map/multimap
3.1map和multimap参考⽂档
3.2pair类型(map底层的红⿊树节点中的数据）介绍
3.3map类的介绍
3.3.1map类实现的介绍
3.3.2map类的接口介绍
3.3.2.1map类的insert和迭代器接口
3.3.2.2map类的erase接口
3.3.2.3map类[]接口(重点）
3.3.2multimap类的接口介绍
3.3.2.1multimap类的inset接口
3.3.2.2multimap类的[]接口
3.3.2.3multimap类的equal_range接口
前言
set是我们前面讲的(key)类型的搜索二叉树，multiset和set一样只是multiset支持插入重复的；map是(key,vallue)类型的搜索二叉树，multimap和map一样只是multimap也支持插入重负的搜索二叉树。
这里要注意的是
1set/multiset和map/multimap的底层都是红⿊树(⼀颗平衡的搜索二叉树)。
2set不支持插入重复的，multiset支持插入重复的；map不支持插入重复的(这里提供key判断是否重复),multimap支持插入重复的。
2set/multiset不支持修改，而map/multimap支持修改value，不支持修改key(因为map/multimap是通过其中的key判断是否相同，要注意(key)类型的二叉树都是通过key进行判断所以key不能改变[一变就不能保证是搜索二叉树的结构]，而(key,value)类型的也是通过key进行判断所以key也不能改变[一变就不能保证是搜索二叉树的结构]。
一 容器的分类(根据容器中各个数据之间的关系）
1.1序列式容器
1.1.1序列式容器的概念
序列式容器逻辑上呈现一条线性(类似于顺式结构中的顺序表等)，数据于数据之间并没有关联，目的只是单纯的把数据储存起来。顺序容器中的元素是按他们在容器中的存储位置来顺序保存和访问的。
1.1.2序列式容器的例子
前⾯我们已经接触过STL中的部分容器如：string、vector、list、deque、array、forward_list等，这些容器统称为序列式容器，因为逻辑结构为线性序列的数据结构，两个位置存储的值之间⼀般没有紧密的关联关系，⽐如交换⼀下，他依旧是序列式容器。顺序容器中的元素是按他们在容器中的存储位置来顺序保存和访问的。
1.2关联式容器
1.2.1关联式容器的概念
和搜索二叉树一样逻辑上不呈现一条线性，数据之间紧密关联，不是随便排，插入一个数据又规定的位置(没有某个位置的插入，按照自己的规则插入）所以并没有什么头部/尾部的插入(只有一个位置的插入),目的不只是单纯的插入数据。建立这种关联式为了方便查找搜索。
1.2.2关联式容器的例子
关联式容器也是⽤来存储数据的，与序列式容器不同的是，关联式容器逻辑结构通常是⾮线性结构，两个位置有紧密的关联关系，交换⼀下，他的存储结构就被破坏了。顺序容器中的元素是按关键字来保存和访问的。关联式容器有map/set系列和unordered_map/unordered_set系列。
二 set/multiset
2.1参考文档(multiset包在set中所以其没有头文件）
2.2set类的介绍
2.2.1set类的实现的简单介绍
•set的声明如下，T就是set底层关键字的类型。•set默认要求T⽀持⼩于⽐较，如果不⽀持或者想按⾃⼰的需求⾛可以⾃⾏实现仿函数传给第⼆个模版参数。•set底层存储数据的内存是从空间配置器申请的，如果需要可以⾃⼰实现内存池，传给第三个参数。•由于缺省值所以⼀般情况下，我们都不需要传后两个模版参数，只有当默认值不满足我们需求时在自己传参。•set底层是⽤红⿊树实现，增删查效率是 ，迭代器遍历是⾛的搜索树的中序，所以是有序的。
template < class T, // set::key_type/value_type class Compare = less<T>, // set::key_compare/value_compare class Alloc = allocator<T> // set::allocator_type > class set;2.2.2set类的接口介绍
前⾯部分我们讲了vector/list等容器的使⽤，STL容器接⼝设计，⾼度相似，所以这⾥我们就不再⼀个接⼝⼀个接⼝的介绍，挑⽐较重要/不同的接⼝进⾏介绍。
2.2.2.1set类构造接口
set类构造接口和我们的vector/list等容器的使⽤一样，这里我们着重了解一下使用
initializer_list构造(即使用多个一下构造C++11支持)其原理还是遍历initializer_list的每个值在插入。
【示例】
int main() { set<int> s; // 插入一段initializer_list列表值，已经存在的值插入失败 s.insert({ 2,8,3,9 }); }2.2.2.2set类的迭代器接口
注意set类的迭代器是一个双向迭代器，由于set不支持修改，所以迭代器也不支持修改(不管是普通迭代器还是const迭代器都是一样)，注意set的迭代器会走中序遍历(即begin()是搜索二叉是最左边的节点)。其所有还是和之前讲的vector/list等容器的使⽤一样。
【示例】
int main() { // 去重+升序排序(默认) set<int> s; // 去重+降序排序（给一个大于的仿函数） //set<int, greater<int>> s; s.insert(5); s.insert(2); s.insert(7); s.insert(5); set<int>::iterator it = s.begin();//set的迭代器会走中序遍历(即begin()是搜索二叉是最左边的节点) while (it != s.end()) { // *it = 5;//set不支持修改，所以迭代器也不支持修改 cout << *it << " "; ++it; } cout << endl; //插入string类型 set<string> strset = { "sort", "insert", "add" }; // 遍历string比较ascll码大小顺序遍历的 for (auto& e : strset) { cout << e << " "; } cout << endl; return 0; }【运行结果】
由于set不支持修改，所以迭代器也不支持修改，所以这里对于迭代器变量it进行改变会报错，set的迭代器会走中序遍历(即begin()是搜索二叉是最左边的节点)，而set的模板参数中的仿函数是一个降序，所以输出结果是一个降序序列
2.2.2.3set类的find接口(查找）
2.2.2.3.1set类的find接口(查找）的解析
这里要注意的是set的find接口的返回值是一个迭代器类型(前⾯部分我们讲了vector/list等容器的find接口返回值的是bool类型)，注意如果没有找到就返回迭代器end()。
2.2.2.3.2算法库中的查找函数和set类的find接口(查找）的对比
算法库中的查找函find(begin(),end()，x)，是一个函数模板，参数是一个容器的迭代器区间，进行的是暴力查找(时间复杂度(O(N))，这是一个专门为vector、list这样的容器准备的(线性序列式容器)；而set类的find接口(查找）进行的是set内部的查找，是按照搜索二叉树的构造进行查找的(是一个平衡搜索二叉树，O(logN))。
【示例】
int main() { set<int> s; // 插入一段initializer_list列表值，已经存在的值插入失败 s.insert({ 2,8,3,9 }); int x; cin >> x; //find返回一个迭代器位置，如果存在就返回对应节点的位置，如果不存在就返回迭代器end() auto pos = s.find(x); if (pos != s.end()) { cout << "存在" << endl; } else { cout << "不存在" << endl; } return 0; }【运行结果】
2.2.2.4set类的erase接口(删除）
这里我们通过其参数进行解析，如果其参数是一个迭代器，则一般是和find接口进行配合使用(find接口的返回值是一个迭代器类型）；如果参数一段迭代器区间和以前一样；如果参数是一个值，就删除对应值的节点，要注意的是这时返回值的类似是size_t(删除的个数）而不是bool类型(前面部分我们讲了vector/list等容器的返回值的类型的是bool)这是为了和multiset兼容由于multiset支持插入重复值，所以此时删除的值可能不止一个如果此时返回值是bool类型就不行。
【示例】
int main() { set<int> s; s.insert({ 2,8,3,9,7,10,12,14 }); // 直接删除x,这时返回值的类似是size_t(删除的个数）而不是bool类型 int x; cin >> x; int num = s.erase(x); cout << num << endl; if (num == 0) { cout << x << "不存在！" << endl; } for (auto e : s) { cout << e << " "; } cout << endl; // 直接查找在利用迭代器删除x, //如果其参数是一个迭代器，则一般是和find接口进行配合使用(find接口的返回值是一个迭代器类型） int x; cin >> x; auto pos = s.find(x); if (pos != s.end()) { s.erase(pos); } else { cout << x << "不存在！" << endl; } for (auto e : s) { cout << e << " "; } cout << endl; //也可以是一段迭代器区间和以前一样 s.erase(s.begin()++,s.end()); return 0; }【运行结果】
2.2.2.5set类的count接口(判断一个值是否存在）
判断一个值是否存在我们上面是通过find的返回值与迭代器end()进行比较。而count接口可以判断一个数据是否存在(相比通过find的返回值与迭代器end()进行比较更舒服，所以只是单纯判断数据是否存在比find更好)，要注意该接口的返回值不是bool类型而是size_t类型(返回数据存在的个数)，这也是为了兼容multiset由于multiset其中一个值存在的个数可能又多个如果此时返回bool类型就不行。
【示例】
int main() { set<int> s; s.insert({ 2,8,3,9,7,10,12,14 }); int x; cin >> x; //方法一，前面的老方法，先查找，由于find的返回值是一个迭代器类型，在和对应的end()比较即可 /*auto pos = s.find(x); if (pos != s.end())*/ //方法二使用count接口，由于cound返回的是数据存在的个数由于set不支持插入重复的数据， // 所以set的count接口的返回值只有两种(1或0)所以在set中常常用count接口的返回值作为判断条件 cout << s.count(x) << endl; if(s.count(x)) { cout << x << "存在！" << endl; } else { cout << x << "不存在！" << endl; } return 0; }【运行结果】
2.2.2.6set类的lower_boundt接口和upper_bound接口(找边界)
lower_boundt找>=key的值返回迭代器类型；upper_bound找>key的值返回迭代器，注意如果未找到就返回end(所以这里不用担心右边界)。这里本质上是为了找的一段[)左闭右开的区间，因为在C++里面不管是容器函数算法都要传一段[)左闭右开的区间。其实我们的算法库中也有该效果的函数(<algorithm>中)。
【示例】
int main() { std::set<int> myset; for (int i = 1; i < 10; i++) myset.insert(i * 10); // 10 20 30 40 50 60 70 80 90 for (auto e : myset) { cout << e << " "; } cout << endl; // 实现查找到的[itlow,itup)包含[30, 60]区间 // 返回 >= 30 auto itlow = myset.lower_bound(30); // 返回 > 60 auto itup = myset.upper_bound(60); myset.erase(itlow, itup); for (auto e : myset) { cout << e << " "; } cout << endl; //// 实现查找到的[itlow,itup)包含[35, 65]区间 // 返回 >= 35 auto itlow = myset.lower_bound(35); // 返回 > 65 auto itup = myset.upper_bound(65); myset.erase(itlow, itup); for (auto e : myset) { cout << e << " "; } cout << endl; // 实现查找到的[itlow,itup)包含[30, 90]区间 auto itlow = myset.lower_bound(30); auto itup = myset.upper_bound(90); myset.erase(itlow, itup); for (auto e : myset) { cout << e << " "; } cout << endl; return 0; }2.2.3multiset类的接口介绍
multiset类的接口和set类的接口高度类似(由于multiset包在set中所以multiset并没有头文件)，所以这里我这讲它们一些接口的不同。
2.2.3.1multiset类的find接口(查找)
由于multiset支持插入重复的数据，所以在查找一个值时可能有多个，那它返回的时哪个呢（是遍历时遇到的第一个；还是进行中序遍历的第一个）注意这里返回的时中序的第一个。
这里时怎么找到中序中的第一个：
先进行中序遍历，遍历相遇到第一个与要查找的值相等的第一个节点(由于二叉搜索树的特点，即右子树的值一定比根节点的值大)，此时在去它的左子树种查找，如果没找到此时根节点就是，如果有还有查找(不断查找左子树，直到左子树为空）。
【示例】
int main() { // 相比set不同的是，multiset是排序，但是不去重 multiset<int> s = { 4,2,7,2,4,8,4,5,4,9 }; auto it = s.begin(); while (it != s.end()) { cout << *it << " "; ++it; } cout << endl; // find返回中序的第一个4 auto pos = s.find(4); while (*pos == 4) { cout << *pos << " "; ++pos; } cout << endl; return 0; } 【运行结果】
2.2.3.2multiset类的cound接口(判断是否存在)
由于cound接口返回的数据存在的个数(而set要么是零个要么是一个)，对于multiset不仅可以判断是否存在，还可以判断数据有几个。
【示例】
int main() { multiset<int> s = { 4,2,7,2,4,8,4,5,4,9 }; //cound返回在存在的个数 cout << s.count(4) << endl; cout << s.count(5) << endl; cout << s.count(6) << endl; return 0; }【运行结果】
2.2.3.3multiset类的erase接口(删除)
这里我们也是通过其参数进行解析，如果参数是一个值，就删除所有对应值的节点(其他两种情况和set一样）,所以在multiset种如果只想删除一个就要用find进行配合，如果想删除所有与值相同的就直接参值即可。
【示例】
int main() { multiset<int> s = { 4,2,7,2,4,8,4,5,4,9 }; // 删除所有的4,此时要传值，注意此时返回值是返回删除个数 cout << s.erase(4) << endl; // 删除中序第一个4，此时要配合find使用 /*auto pos = s.find(4); if(pos != s.end()) s.erase(pos);*/ auto it = s.begin(); while (it != s.end()) { cout << *it << " "; ++it; } cout << endl; return 0; }【运行结果】
2.2.4set/multiset的总结
对于要去重+排序或者去重时用set；对于自己排序时用(multiset）但是如果是对于大量数据进行排序时有不如先将数据放到vector中在调用sqrt(排序)先从时间复杂度分析multiset的排序时间复杂度时(ON*logN),而vector中在调用sqrt(排序)所有的时归并排序所以时间复杂度也是O(N*logN)。所以这里种方法都是同一量级的方法，但是树/链式结构的空间访问的缓存命中率不比vector高，所以先将数据放到vector中在调用sqrt(排序）的效率更高。
三 map/multimap
3.1map和multimap参考⽂档
3.2pair类型(map底层的红⿊树节点中的数据）介绍
map底层的红⿊树节点中的数据，使⽤pair<Key, T>存储键值对数据。
typedef pair<const Key, T> value_type; template <class T1, class T2> 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) {} template<class U, class V> pair (const pair<U,V>& pr): first(pr.first), second(pr.second) {} }; template <class T1,class T2> inline pair<T1,T2> make_pair (T1 x, T2 y) { return ( pair<T1,T2>(x,y) ); }3.3map类的介绍
3.3.1map类实现的介绍
map的声明如下，Key就是map底层关键字的类型，T是map底层value的类型，set默认要求Key⽀持⼩于⽐较，如果不⽀持或者需要的话可以⾃⾏实现仿函数传给第⼆个模版参数，map底层存储数据的内存是从空间配置器申请的。⼀般情况下，我们都不需要传后两个模版参数。map底层是⽤红⿊树实现，增删查改效率是 O(logN) ，迭代器遍历是⾛的中序，所以是按key有序顺序遍历的。
template < class Key, // map::key_type class T, // map::mapped_type class Compare = less<Key>, // map::key_compare class Alloc = allocator<pair<const Key,T> > // map::allocator_type > class map;3.3.2map类的接口介绍
前⾯部分我们讲了set/multiset的使⽤，STL容器接⼝设计，⾼度相似map和 set/multiset的使⽤更是高度相似，所以这⾥我们就不再⼀个接⼝⼀个接⼝的介绍，挑⽐较重要/和set/multiset不同的接⼝进⾏介绍。
3.3.2.1map类的insert和迭代器接口
前面我们插入的都是一个数据类型，而这里插入的是一个为(key,value）类型即pairl类型【这里并没有将两个数据分开插入而是同时插入，前面实现搜索二叉树是分开来插的】，这也就意味着map的迭代器无法解引用(要调用operator*重载函数，该函数无法实现返回两个值）。
【示例】
int main() { map<string, string> dict; pair<string, string> kv1("sort", "排序"); dict.insert(kv1);//插入一个有名对象 dict.insert(pair<string, string>("left", "左边"));//插入一个匿名对象 dict.insert(make_pair("left", "左边"));//C++11 dict.insert({ "right", "右边" });//使用隐时类型转换 //map<string, string>::iterator it = dict.begin(); auto it = dict.begin(); //*it;迭代器不支持解引用，因为迭代器解引用会调用operator*无法返回两个变量 while (it != dict.end()) { //由于pair类型不支持"<<"和“>>"提取查找，访问pair成员的两种方法 //cout << (*it).first <<":" << (*it).second <<endl; cout << it->first << ":" << it->second << endl; ++it; } return 0; }3.3.2.2map类的erase接口
这个接口和set类似，只有注意这里传值不是传(key,value)类型，这里只传key。
3.3.2.3map类[]接口(重点）
【示例】
int main() { //map-的[]接口的多种功能(因为底层调用了insert； map<string, string> dict; dict.insert({ "sort", "" }); // + dict["left"] = "";//没有会插入 // 插入 dict["right"];//没有就会插入-没个对应的value就是默认值 // 修改-插入+修改 dict["right"] = "ұ";//修改因为前面已经插入，前面是默认值这里对对应的value进行修改 //如果没有上面的插入就会是插入+修改，对于没有的插入后可对对应的value进行修改 // 查找功能但是要保证你查找的存在，不然会变成插入功能 //有传key可以得到对应的value,并且可以对对应的value进行读写 cout << dict["left"] << endl;//读 dict["left"] = "wzy";//写 dict.insert({ "sort", "xxxx" });//由于map不支持插入重复，而这里是通过key判断的,所以这里的"sort"所给的vale值"xxx"不会覆盖原value值 return 0; }3.3.2multimap类的接口介绍
multimap类和map类高度类似，这里我这讲它们的不同。
3.3.2.1multimap类的inset接口
由于multimap支持插入重复的，而multimap是通过key判断的所以对于multimap不管是什么类型都会插入。而对于mapkey相同是不支持插入的。
【示例】
int main() { //由于multimap支持插入重复值，而是否重复是通过key判断的，对应的value不管可以相同也可以不同 //所以对于multimap不管key和value两者是否相同都会插入，即multimap只管插入不管什么都会插入 multimap<string, string> dict; dict.insert({ "sort", "" }); dict.insert({ "sort", "" }); dict.insert({ "sort", "xxxx" }); dict.insert({ "left", "" }); //对于map是不支持插入重复的，由于这里是通过key判断的,就意味着如果插入的值前面有一个相等的对于map此时就不会改变原value }3.3.2.2multimap类的[]接口
multimap类无[]接口，因为无意义，有大问题，因为给key对应的value有多个不知道是哪个。
3.3.2.3multimap类的equal_range接口
前面我没讲这个接口是因为这个接口是对pair类型进行操作的，而前面的set/multiset不是pair类型，这个接口的作用是获取与传的值相等的元素；与loewr_bound和upper_bound不同这两个是获得边界。
【示例】
int main() { multimap<string, string> dict; dict.insert({ "sort", "" }); dict.insert({ "sort", "" }); dict.insert({ "sort", "xxxx" }); dict.insert({ "left", "" }); //dict.erase("sort"); auto itpair = dict.equal_range("sort"); auto it = itpair.first; while (it != itpair.second) { cout << it->first << ":" << it->second << endl; ++it; } cout << endl; return 0; }【运行结果】
本篇文章就到此结束，欢迎大家订阅我的专栏，欢迎大家指正，希望有所能帮到读者更好了解C++STL知识 ，觉得有帮助的还请三联支持一下~后续会不断更新算法与数据结构相关知识，我们下期再见。
我的博客即将同步至腾讯云开发者社区，邀请大家一同入驻：https://cloud.tencent.com/developer/support-plan?invite_code=c8vjkz6dqle
