一、关联式容器与键值对

1.1 关联式容器

C++ 初阶的时候，我们已经接触了 STL 中的部分容器并进行了模拟实现，比如vector、list、stack、queue等，这些容器统称为序列式容器，因为其底层为线性序列的数据结构，里面存储的是元素本身；

同样，关联式容器也是用来存储数据的，但与序列式容器不同的是，关联式容器里面存储的是<key, value>结构的键值对，因此在数据检索时比序列式容器效率更高。

1.2 键值对 pair

键值对是用来表示具有一一对应关系的一种结构，该结构中一般只包含两个成员变量 –key和value；其中key代表键值，value代表与key对应的信息。

我们在上一节学习二叉搜索树的时候提到的 KV 模型 (key-value 模型) 中的 KV 其实就是键值对；我们可以用上一节中提到的英汉互译的例子来理解 key-value 键值对 – 现在要建立一个英汉互译的字典，那该字典中必然有英文单词与其对应的中文含义，而且，英文单词与其中文含义是一一对应的关系，即通过该英文单词，在词典中就可以找到与其对应的中文含义。

STL 中键值对的定义如下：(SGI 版本)

template<classT1,classT2>structpair{typedefT1 first_type;typedefT2 second_type;T1 first;//keyT2 second;//valuepair():first(T1()),second(T2())//默认构造{}pair(constT1&a,constT2&b):first(a),second(b){}};

可以看到，C++ 中的键值对是通过pair类来表示的，pair类中的first就是键值key，second就是key对应的信息value；那么以后我们在设计 KV 模型的容器时只需要在容器/容器的每一个节点中定义一个pair对象即可；

这里有的同学可能会有疑问，为什么不直接在容器中定义key和value变量，而是将key、value合并到pair中整体作为一个类型来使用呢？这是因为 C++ 一次只能返回一个值，如果我们将key和value单独定义在容器中，那么我们就无法同时返回key和value；而如果我们将key、value定义到另一个类中，那我们就可以直接返回pair，然后再到pair中分别去取first和second即可。

• make_pair函数

  由于pair是类模板，所以我们通常是以显式实例化 + 匿名对象的方式来进行使用，但是由于显式实例化比较麻烦，所以 C++ 还提供了make_pair函数，其定义如下：

template<classT1,classT2>pair<T1,T2>make_pair(T1 x,T2 y){return(pair<T1,T2>(x,y));}

如上，make_pair返回的是一个pair的匿名对象，匿名对象会自动调用pair的默认构造完成初始化；但由于make_pair是一个函数模板，所以模板参数的类型可以根据实参来自动推导完成实例化，这样我们就不用每次都显式指明参数类型了。

注：由于make_pair使用起来比pair方便很多，所以我们一般都是直接使用make_pair，而不使用pair。

1.3 树形结构的关联式容器

根据应用场景的不同，STL 总共实现了两种不同结构的关联式容器 – 树型结构与哈希结构；树型结构的关联式容器主要有四种 –map、set、multimap、multiset，这四种容器的共同点是使用平衡二叉搜索树作为其底层结构，容器中的元素是一个有序的序列；本文将介绍这四个容器的使用。

二、set

2.1 set 的介绍

set是按照一定次序存储元素的容器，其底层是一棵平衡二叉搜索树 (红黑树)，由于二叉搜索树的每个节点的值满足左孩子 < 根 < 右孩子，并且二叉搜索树中没有重复的节点，所以set可以用来排序、去重和查找，同时由于这是一棵平衡树，所以set查找的时间复杂度为 O(logN)，效率非常高；

同时，set是一种 K 模型的容器，也就是说，set中只有键值key，而没有对应的value，并且每个key都是唯一的；set中的元素也不允许修改，因为这可能会破坏搜索树的结构，但是set允许插入和删除。

1. set是 K 模型的容器，所以set中插入元素时，只需要插入key即可，不需要构造键值对；
2. set中的元素不可以重复，因此可以使用set进行去重；
3. 由于set底层是搜索树，所以使用set的迭代器遍历set中的元素，可以得到有序序列，即set可以用来排序；
4. set默认使用的仿函数为less，所以set中的元素默认按照小于来比较；
5. 由于set底层是平衡搜索树，所以set中查找某个元素，时间复杂度为 O(logN)；
6. set中的元素不允许修改，因为这可能破坏搜索树的结构；
7. set中的底层使用平衡二叉搜索树 (红黑树) 来实现。

注：可能有的同学对 O(logN) 的时间复杂度没有什么具体的概念，那么我们可以列举一组数据大家就很清楚了：set从 1000 个数据中查找某个数据最多找 10 次，从 100 万个数据中找某一个数据最多找 20 次，从 10 亿个数据中找某一个数据最多找 30 次；换一种说法，如果以身份证号作为key值存入set中 (假设内存足够)，那么我们从中国所有人中查找某一个身份证号对应的人时最多只用找 31 次；相信现在大家对 O(logN) 是什么量级的存在已经有了很清楚的认识了。

2.2 set 的使用

• 构造

  和传统容器一样，set也支持单个元素构造、迭代器区间构造以及拷贝构造：

• 迭代器

  set支持正向和反向迭代遍历，遍历默认按升序顺序（因为插入的时候仿函数是小于的），因为底层是二叉搜索树，迭代器遍历走的中序；支持迭代器就意味着支持范围 for，set的iterator和const_iterator都不支持迭代器修改数据，修改关键字数据，破坏了底层搜索树的结构。

• 修改

  set有如下修改操作

  其中swap就是交换两棵树的根，clear就是释放树中的所有节点，emplace和emplace_hint我们放在 C++11 章节中学习，大家现在不用管它；最重要的修改操作是insert和erase（会失效）；

  insert支持插入一个值、在某个迭代器位置插入值、插入一段迭代器区间（底层也是调用一个一个值插入的），我们学会第一个即可，插入的过程就是二叉搜索树的插入过程；需要注意的是insert的返回值是pair类型，pair中第一个元素代表插入的迭代器位置，第二个元素代表是否插入成功 (插入重复节点会返回false)：

  erase也有三种，常用的是第一种和第二种，删除指定键值的数据和删除指定迭代器位置的数据：

• 操作

  set还有一些其他操作相关的函数：

  其中比较重要的只有find，由于set中不允许出现相同的key，因此在set中count函数的返回值只有 1/0，可以说没有什么价值，set中定义count主要是因为count在set中用于查找一个元素在不在，在multiset中用于查找一个元素出现的次数，这里是为了保持一致；lower_bound（返回大于等于的第一个值）和upper_bound（返回大于的第一个值）是得到一个左闭右开的迭代器区间，因为我们经常要用左闭右开的区间，所以这样设计，然后我们可以对这段区间进行某些操作。

  find的作用是在搜索树中查找key对应的节点，然后返回节点位置的迭代器，如果找不到，find会返回end()：

2.3 set 使用范例

voidset_test1(){//无参构造set<int>s1;//插入数据（重复数据忽略）s1.insert(1);s1.insert(6);s1.insert(5);s1.insert(9);s1.insert(4);s1.insert(8);s1.insert(8);s1.insert(6);s1.insert(2);//拷贝构造set<int>s2(s1);//迭代器遍历set<int>::iterator it1=s1.begin();while(it1!=s1.end()){cout<<*(it1)<<" ";it1++;}cout<<endl;//增强forfor(autok:s2){cout<<k<<" ";}cout<<endl;//找到8的迭代器set<int>::iterator it2=s1.find(8);//输出迭代器的值cout<<*it2<<endl;//删除迭代器8s1.erase(it2);//增强forfor(autok:s1){cout<<k<<" ";}cout<<endl;//迭代器失效for(autok:s2){//找到8的迭代器//没找到会返回end()set<int>::iterator it3=s2.find(8);////删除迭代器8//if (it3 != s2.end())//{// s2.erase(it3);// *it3;//}//删除迭代器8删除后会返回下一个迭代器的值if(it3!=s2.end()){it3=s2.erase(it3);*it3;}cout<<k<<" ";}}

三、multiset

3.1 multiset 的介绍

multiset也是 K 模型的容器，它和set唯一的区别在于multiset中允许存在重复的key值节点，所以multiset可以用来排序和查找，但是不能用来去重。

3.2 multiset 的使用

multiset的使用其实和set也几乎一样，唯一需要注意的是find和count函数 – 由于multiset中允许存在重复key值的节点，所以multiset中count函数就有作用了，我们可以通过count函数来统计同一key在multiset中的数量：

multiset中find函数的使用也和set有所区别 – 由于set中没有重复的节点，所以find时要么返回该节点位置的迭代器，要么返回end()；而multiset中可能有重复的节点，所以find时返回的是同一key值中的哪一个节点呢？实际上find返回的是中序遍历过程中第一个匹配的节点位置的迭代器：

3.3 multiset 使用范例

voidmultiset_test1(){// 相比set不同的是，multiset是排序，但是不去重multiset<int>s={4,2,7,2,4,8,4,5,4,9};//列表初始化autoit=s.begin();while(it!=s.end()){cout<<*it<<" ";++it;}cout<<endl;// 相比set不同的是，x可能会存在多个，find查找中序的第一个intx;cin>>x;autopos=s.find(x);// 相比set不同的是，count会返回x的实际个数cout<<s.count(x)<<endl;// 相比set不同的是，erase给值时会删除所有的xs.erase(x);for(autoe:s){cout<<e<<" ";}cout<<endl;}

四、map

4.1 map 的介绍

1. Key就是map底层关键字的类型，T是map底层value的类型。
2. map默认要求Key支持小于比较，如果不支持或者需要的话可以自行实现仿函数传给第三个模板参数，
3. map底层存储数据的内存是从空间配置器申请的。
4. 一般情况下，我们都不需要传后两个模板参数。

特别注意：map允许修改节点中key对应的value的值，但是不允许修改key，因为这样可能会破坏搜索树的结构。

map底层是用红黑树实现，增删查改效率是 O(logN)，迭代器遍历是走的中序，所以是按key有序顺序遍历的。

4.2 map 的使用

• 构造

  其中列表构造需要给一个例子给大家：

map<string,string>dict={{"left","左边"},{"right","右边"},{"insert","插入"}};

• 迭代器

  map支持正向和反向迭代遍历，遍历默认按key的升序顺序，因为底层是二叉搜索树，迭代器遍历走的中序；支持迭代器就意味着支持范围 for，map支持修改value数据，不支持修改key数据，修改了数据，就破坏了底层搜索树的结构。

• 修改

  修改中的重点的仍然是insert和erase，swap为交换两棵树的根，clear为释放树中的每一个节点；

  erase一样也有三种，常用的是第一种和第二种，删除指定键值的数据和删除指定迭代器位置的数据：

// 删除一个迭代器位置的值iteratorerase(const_iterator position);// 删除k，k不存在返回0，存在返回1size_typeerase(constkey_type&k);// 删除一段迭代器区间的值iteratorerase(const_iterator first,const_iterator last);

4.3 插入 pair 的方法

和set一样，map的insert也支持插入一个值、在某个迭代器位置插入值、插入一段迭代器区间，我们还是学会第一个即可，插入的过程就是二叉搜索树的插入过程，和之前的set一样insert的返回值是pair类型，pair中第一个元素代表插入的迭代器位置，第二个元素代表是否插入成功 (插入重复节点会返回false)

// 方法一：直接新建插入pairmap<string,string>dict;pair<string,string>kv1("first","第一个");dict.insert(kv1);// 方法二：匿名对象插入dict.insert(pair<string,string>("second","第二个"));// 方法三：make_pairdict.insert(make_pair("sort","排序"));// 方法四：C++11后可以直接插入：（基于 C++11 的多参数的隐式类型转化）dict.insert({"sort","排序"});

1. insert插入一个pair<key, T>对象
2. 如果key已经在map中，插入失败，则返回一个pair<iterator,bool>对象，返回pair对象first是key所在结点的迭代器，second是false。
3. 如果key不在map中，插入成功，则返回一个pair<iterator,bool>对象，返回pair对象first是新插入key所在结点的迭代器，second是true
4. 也就是说无论插入成功还是失败，返回pair<iterator,bool>对象的first都会指向key所在的迭代器
5. 那么也就意味着insert插入失败时充当了查找的功能，正是因为这一点，insert可以用来实现operator[]
6. 需要注意的是这里有两个pair，不要混淆了，一个是map底层红黑树节点中存的pair<key, T>，另一个是insert返回值pair<iterator,bool>

• 操作

  和set一样，map中有count函数是因为multimap需要count函数，count依旧可以拿来当查找接口用，这里是为了保持一致性：

// 查找k，返回k所在的迭代器，没有找到返回end()iteratorfind(constkey_type&k);// 查找k，返回k的个数size_typecount(constkey_type&k)const;

4.4 operator[] 数据修改

operator[]增查改三位一体，那么operator[]的底层是什么？C++ 官方网站中是这么说的，这说明operator[]的底层是一个insert。

(*((this)->insert(make_pair(k, mapped_type())).first)).second

((this)->insert(make_pair(k, mapped_type())).first)

我们前面说了insert可以查找，一样的会返回迭代器位置，这里就是找到了一样的迭代器位置

如果key已经在map中，插入失败，则返回一个pair<iterator,bool>对象，返回pair对象first是key所在结点的迭代器，second是false。

(*((this)->insert(make_pair(k, mapped_type())).first)).second

对迭代器解引用取出pair再取出val

如果k不在map中，insert会插入k和mapped_type默认值，同时[]返回结点中存储mapped_type值的引用，那么我们可以通过引用修改该映射值。所以[]具备了插入 + 修改功能。

如果k在map中，insert会插入失败，但是insert返回pair对象的first是指向key结点的迭代器，返回值同时[]返回结点中存储mapped_type值的引用，所以[]具备了查找 + 修改的功能。

总结

插入成功:pair<新插入值所在迭代器, true>

插入失败:pair<已经存在的跟key相等值迭代器, false>

4.5 map 使用范例

4.5.1 统计水果出现的次数 find 和 iterator

voidmap_test2(){vector<string>v={"苹果","西瓜","苹果","西瓜","苹果","苹果","西瓜","苹果","香蕉","苹果","香蕉"};map<string,int>m1;for(string str:v){//在map里面找水果map<string,int>::iterator ret=m1.find(str);//不在if(ret==m1.end()){m1.insert({str,1});}//在就加加else{ret->second++;}}// 遍历输出//必须带const。k不能改for(pair<conststring,int>&k:m1){cout<<k.first<<"->"<<k.second<<" ";}}

4.5.2 统计水果出现的次数 []

voidmap_test1(){string arr[]={"苹果","西瓜","苹果","西瓜","苹果","苹果","西瓜","苹果","香蕉","苹果","香蕉"};map<string,int>m1;for(string&str:arr){m1[str]++;// 有就计数+1，没有就插入默认0再+1}// 遍历输出//必须带const。k不能改for(pair<conststring,int>&k:m1){cout<<k.first<<"->"<<k.second<<" ";}}

4.5.3 字典

voidmap_test3(){map<string,string>dict;//向map中插入元素的方式：用pair直接来构造键值对pair<string,string>p1("banan","香蕉");dict.insert(p1);//匿名构造dict.insert(pair<string,string>("peach","桃子"));//为了方便，我们建议直接用make_pair函数来构造键值对dict.insert(make_pair("apple","苹果"));// 将<"orange", "">插入map中，插入成功，返回value的引用，将“橘子”赋值给该引用结果，dict["orange"]="橘子";// 遍历输出//必须带const。k不能改for(pair<conststring,string>&k:dict){cout<<k.first<<"->"<<k.second<<" ";}cout<<endl;autoret=dict.insert(make_pair("peach","桃"));//布尔值if(ret.second)cout<<"<peach, 桃>不在map中, 已经插入"<<endl;elsecout<<"键值为 peach 的元素已经存在："<<ret.first->first<<"--->"<<ret.first->second<<" 插入失败"<<endl;dict.erase("apple");if(1==dict.count("apple"))cout<<"apple还在"<<endl;elsecout<<"apple被吃了"<<endl;}

五、multimap

5.1 multimap 介绍与使用

multimap和map的使用基本完全类似，主要区别点在于multimap支持关键值key冗余，那么insert/find/count/erase都围绕着支持关键值key冗余有所差异，这里跟set和multiset完全一样，比如find时，有多个key，返回中序第一个。其次就是multimap不支持[]，因为支持key冗余 (人话就是：用operator[]找一个key，但是这里面有很多个key，不知道返回哪个key指向的value)。

count返回和key值相等的节点的个数：

5.2 multimap 使用范例

voidmultimap_test1(){// 相比map不同的是，multimap支持key冗余multimap<string,int>m={{"语文",70},{"数学",80},{"语文",60},{"物理",70},};//列表初始化autoit=m.begin();// 遍历输出//必须带const。k不能改for(pair<conststring,int>&k:m){cout<<k.first<<"->"<<k.second<<" ";}cout<<endl;// 相比map不同的是，k可能会存在多个，find查找中序的第一个autopos=m.find("语文");if(pos!=m.end()){cout<<"find 找到的第一个语文："<<pos->first<<"->"<<pos->second<<endl;}// 相比map不同的是，count会返回x的实际个数cout<<m.count("语文")<<endl;// 相比map不同的是，erase给值时会删除所有的xm.erase("语文");for(pair<conststring,int>&k:m){cout<<k.first<<"->"<<k.second<<" ";}cout<<endl;}