一、关联式容器与键值对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 版本)templateclassT1,classT2structpair{typedefT1 first_type;typedefT2 second_type;T1 first;//keyT2 second;//valuepair():first(T1()),second(T2())//默认构造{}pair(constT1a,constT2b):first(a),second(b){}};可以看到C 中的键值对是通过pair类来表示的pair类中的first就是键值keysecond就是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函数其定义如下templateclassT1,classT2pairT1,T2make_pair(T1 x,T2 y){return(pairT1,T2(x,y));}如上make_pair返回的是一个pair的匿名对象匿名对象会自动调用pair的默认构造完成初始化但由于make_pair是一个函数模板所以模板参数的类型可以根据实参来自动推导完成实例化这样我们就不用每次都显式指明参数类型了。注由于make_pair使用起来比pair方便很多所以我们一般都是直接使用make_pair而不使用pair。1.3 树形结构的关联式容器根据应用场景的不同STL 总共实现了两种不同结构的关联式容器 – 树型结构与哈希结构树型结构的关联式容器主要有四种 –map、set、multimap、multiset这四种容器的共同点是使用平衡二叉搜索树作为其底层结构容器中的元素是一个有序的序列本文将介绍这四个容器的使用。二、set2.1 set 的介绍set是按照一定次序存储元素的容器其底层是一棵平衡二叉搜索树 (红黑树)由于二叉搜索树的每个节点的值满足左孩子 根 右孩子并且二叉搜索树中没有重复的节点所以set可以用来排序、去重和查找同时由于这是一棵平衡树所以set查找的时间复杂度为 O(logN)效率非常高同时set是一种 K 模型的容器也就是说set中只有键值key而没有对应的value并且每个key都是唯一的set中的元素也不允许修改因为这可能会破坏搜索树的结构但是set允许插入和删除。set是 K 模型的容器所以set中插入元素时只需要插入key即可不需要构造键值对set中的元素不可以重复因此可以使用set进行去重由于set底层是搜索树所以使用set的迭代器遍历set中的元素可以得到有序序列即set可以用来排序set默认使用的仿函数为less所以set中的元素默认按照小于来比较由于set底层是平衡搜索树所以set中查找某个元素时间复杂度为 O(logN)set中的元素不允许修改因为这可能破坏搜索树的结构set中的底层使用平衡二叉搜索树 (红黑树) 来实现。注可能有的同学对 O(logN) 的时间复杂度没有什么具体的概念那么我们可以列举一组数据大家就很清楚了set从 1000 个数据中查找某个数据最多找 10 次从 100 万个数据中找某一个数据最多找 20 次从 10 亿个数据中找某一个数据最多找 30 次换一种说法如果以身份证号作为key值存入set中 (假设内存足够)那么我们从中国所有人中查找某一个身份证号对应的人时最多只用找 31 次相信现在大家对 O(logN) 是什么量级的存在已经有了很清楚的认识了。2.2 set 的使用构造和传统容器一样set也支持单个元素构造、迭代器区间构造以及拷贝构造迭代器set支持正向和反向迭代遍历遍历默认按升序顺序因为插入的时候仿函数是小于的因为底层是二叉搜索树迭代器遍历走的中序支持迭代器就意味着支持范围 forset的iterator和const_iterator都不支持迭代器修改数据修改关键字数据破坏了底层搜索树的结构。修改set有如下修改操作其中swap就是交换两棵树的根clear就是释放树中的所有节点emplace和emplace_hint我们放在 C11 章节中学习大家现在不用管它最重要的修改操作是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(){//无参构造setints1;//插入数据重复数据忽略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);//拷贝构造setints2(s1);//迭代器遍历setint::iterator it1s1.begin();while(it1!s1.end()){cout*(it1) ;it1;}coutendl;//增强forfor(autok:s2){coutk ;}coutendl;//找到8的迭代器setint::iterator it2s1.find(8);//输出迭代器的值cout*it2endl;//删除迭代器8s1.erase(it2);//增强forfor(autok:s1){coutk ;}coutendl;//迭代器失效for(autok:s2){//找到8的迭代器//没找到会返回end()setint::iterator it3s2.find(8);////删除迭代器8//if (it3 ! s2.end())//{// s2.erase(it3);// *it3;//}//删除迭代器8删除后会返回下一个迭代器的值if(it3!s2.end()){it3s2.erase(it3);*it3;}coutk ;}}三、multiset3.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是排序但是不去重multisetints{4,2,7,2,4,8,4,5,4,9};//列表初始化autoits.begin();while(it!s.end()){cout*it ;it;}coutendl;// 相比set不同的是x可能会存在多个find查找中序的第一个intx;cinx;autoposs.find(x);// 相比set不同的是count会返回x的实际个数couts.count(x)endl;// 相比set不同的是erase给值时会删除所有的xs.erase(x);for(autoe:s){coute ;}coutendl;}四、map4.1 map 的介绍Key就是map底层关键字的类型T是map底层value的类型。map默认要求Key支持小于比较如果不支持或者需要的话可以自行实现仿函数传给第三个模板参数map底层存储数据的内存是从空间配置器申请的。一般情况下我们都不需要传后两个模板参数。特别注意map允许修改节点中key对应的value的值但是不允许修改key因为这样可能会破坏搜索树的结构。map底层是用红黑树实现增删查改效率是 O(logN)迭代器遍历是走的中序所以是按key有序顺序遍历的。4.2 map 的使用构造其中列表构造需要给一个例子给大家mapstring,stringdict{{left,左边},{right,右边},{insert,插入}};迭代器map支持正向和反向迭代遍历遍历默认按key的升序顺序因为底层是二叉搜索树迭代器遍历走的中序支持迭代器就意味着支持范围 formap支持修改value数据不支持修改key数据修改了数据就破坏了底层搜索树的结构。修改修改中的重点的仍然是insert和eraseswap为交换两棵树的根clear为释放树中的每一个节点erase一样也有三种常用的是第一种和第二种删除指定键值的数据和删除指定迭代器位置的数据// 删除一个迭代器位置的值iteratorerase(const_iterator position);// 删除kk不存在返回0存在返回1size_typeerase(constkey_typek);// 删除一段迭代器区间的值iteratorerase(const_iterator first,const_iterator last);4.3 插入 pair 的方法和set一样map的insert也支持插入一个值、在某个迭代器位置插入值、插入一段迭代器区间我们还是学会第一个即可插入的过程就是二叉搜索树的插入过程和之前的set一样insert的返回值是pair类型pair中第一个元素代表插入的迭代器位置第二个元素代表是否插入成功 (插入重复节点会返回false)// 方法一直接新建插入pairmapstring,stringdict;pairstring,stringkv1(first,第一个);dict.insert(kv1);// 方法二匿名对象插入dict.insert(pairstring,string(second,第二个));// 方法三make_pairdict.insert(make_pair(sort,排序));// 方法四C11后可以直接插入基于 C11 的多参数的隐式类型转化dict.insert({sort,排序});insert插入一个pairkey, T对象如果key已经在map中插入失败则返回一个pairiterator,bool对象返回pair对象first是key所在结点的迭代器second是false。如果key不在map中插入成功则返回一个pairiterator,bool对象返回pair对象first是新插入key所在结点的迭代器second是true也就是说无论插入成功还是失败返回pairiterator,bool对象的first都会指向key所在的迭代器那么也就意味着insert插入失败时充当了查找的功能正是因为这一点insert可以用来实现operator[]需要注意的是这里有两个pair不要混淆了一个是map底层红黑树节点中存的pairkey, T另一个是insert返回值pairiterator,bool操作和set一样map中有count函数是因为multimap需要count函数count依旧可以拿来当查找接口用这里是为了保持一致性// 查找k返回k所在的迭代器没有找到返回end()iteratorfind(constkey_typek);// 查找k返回k的个数size_typecount(constkey_typek)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中插入失败则返回一个pairiterator,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相等值迭代器, false4.5 map 使用范例4.5.1 统计水果出现的次数 find 和 iteratorvoidmap_test2(){vectorstringv{苹果,西瓜,苹果,西瓜,苹果,苹果,西瓜,苹果,香蕉,苹果,香蕉};mapstring,intm1;for(string str:v){//在map里面找水果mapstring,int::iterator retm1.find(str);//不在if(retm1.end()){m1.insert({str,1});}//在就加加else{ret-second;}}// 遍历输出//必须带const。k不能改for(pairconststring,intk:m1){coutk.first-k.second ;}}4.5.2 统计水果出现的次数 []voidmap_test1(){string arr[]{苹果,西瓜,苹果,西瓜,苹果,苹果,西瓜,苹果,香蕉,苹果,香蕉};mapstring,intm1;for(stringstr:arr){m1[str];// 有就计数1没有就插入默认0再1}// 遍历输出//必须带const。k不能改for(pairconststring,intk:m1){coutk.first-k.second ;}}4.5.3 字典voidmap_test3(){mapstring,stringdict;//向map中插入元素的方式用pair直接来构造键值对pairstring,stringp1(banan,香蕉);dict.insert(p1);//匿名构造dict.insert(pairstring,string(peach,桃子));//为了方便我们建议直接用make_pair函数来构造键值对dict.insert(make_pair(apple,苹果));// 将orange, 插入map中插入成功返回value的引用将“橘子”赋值给该引用结果dict[orange]橘子;// 遍历输出//必须带const。k不能改for(pairconststring,stringk:dict){coutk.first-k.second ;}coutendl;autoretdict.insert(make_pair(peach,桃));//布尔值if(ret.second)coutpeach, 桃不在map中, 已经插入endl;elsecout键值为 peach 的元素已经存在ret.first-first---ret.first-second 插入失败endl;dict.erase(apple);if(1dict.count(apple))coutapple还在endl;elsecoutapple被吃了endl;}五、multimap5.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冗余multimapstring,intm{{语文,70},{数学,80},{语文,60},{物理,70},};//列表初始化autoitm.begin();// 遍历输出//必须带const。k不能改for(pairconststring,intk:m){coutk.first-k.second ;}coutendl;// 相比map不同的是k可能会存在多个find查找中序的第一个autoposm.find(语文);if(pos!m.end()){coutfind 找到的第一个语文pos-first-pos-secondendl;}// 相比map不同的是count会返回x的实际个数coutm.count(语文)endl;// 相比map不同的是erase给值时会删除所有的xm.erase(语文);for(pairconststring,intk:m){coutk.first-k.second ;}coutendl;}