一.序列式容器和关联式容器1.序列式容器前面接触的STL容器如vector、list、string等都属于序列式容器因为它们逻辑结构为线性序列的数据结构两两位置间储存的值没什么紧密的关系即使交换位置后它仍是序列式容器。该容器中元素是按照它们在容器中的位置来顺序保存或访问的2.关联式容器我们接下来要学习的set和map就是关联式容器与序列式不同的是关联式容器逻辑结构往往是非线性的两个位置间有紧密的关系交换位置后它的储存结构就被破坏了。该容器中的元素是按关键字来保存和访问的3.set和map的底层是红黑树即一颗平衡二叉搜索树现阶段可以把它当成普通二叉搜索树对待set就是之前学的key型二叉搜索树map就是key_val型。二.set1.set的介绍1.set的声明如下T就是set的关键字的类型2.set默认要求T可以进行小于比较如果不支持可以自己写个仿函数传给它的第二个参数3.一般情况下我们都不需要传后两个参数4.set的底层是红黑树增删查的效率为logN迭代器遍历走的是中序所以遍历打印出来的数据是有序的5.STL容器的接口高度相似所以set也有许多和vector等差不多的接口6.普通的set不允许储存重复的值而multiset可以。2.set的构造与迭代器迭代器set的迭代器是双向迭代器其性质和list的迭代器一样。用迭代器遍历是中序遍历。它获取迭代器的接口也是这么一些构造分为无参构造拷贝构造迭代器区间构造和初始化列表构造。默认是左子树放小值右子树放大值可以通过传仿函数到comp这个位置改。vectorintv({1,6,2,7,3,8,2});setints1(v.begin(),v.end());//迭代器遍历是中序遍历for(autoe:s1){coute ;}coutendl;3.set的增删查insert可以插入一个值也可以插入一个迭代器区间的全部值但最常用的是插入一个值vectorintv({1,6,2,7,3,8,2});setints1(v.begin(),v.end());intx1;while(cinxx!0){s1.insert(x);for(autoe:s1){coute ;}coutendl;}find传所要找的参数如果有与该参数相等的元素则返回该元素对应的迭代器如果没有就返回set.end()vectorintv({1,6,2,7,3,8,2});setints1(v.begin(),v.end());autoposs1.find(3);erase:可以删除指定迭代器区间的所有元素可以删除指定迭代器位置的元素可以删除等于指定参数的元素vectorintv({1,6,2,7,3,8,2});setints1(v.begin(),v.end());//删除区间中的全部内容s1.erase(s1.begin(),--s1.end());for(autoe:s1){coute ;}coutendl;autoposs1.find(3);s1.erase(pos);s1.erase(2);for(autoe:s1){coute ;}coutendl;count:传入一个参数返回set中与其相等的元素的个数如果没有则返回0vectorintv({1,6,2,7,3,8,2});setints1(v.begin(),v.end());size_t ts1.count(3);该接口在普通的set中没什么意义因为普通的set不能储存相同的值其返回值要么是1要么是0。lower_bound 和upper_boundlower_bound会返回第一个大于等于所传参数的元素对应的迭代器upper_bound会返回第一个大于所传参数的元素对应的迭代器第一个都是相对于中序遍历而言。voidset_test2(){setintmyset;for(inti1;i10;i){myset.insert(i*10);}//中序遍历setint::iterator pos1myset.lower_bound(33);setint::iterator pos2myset.upper_bound(80);//setint::iterator pos1 myset.lower_bound(40);//返回第一个大于等于参数值的节点//setint::iterator pos2 myset.upper_bound(80);//返回第一个大于参数值的节点//以上两种结果是一样的myset.erase(pos1,pos2);for(autoe:myset){coute ;}coutendl;}三.muitisetmuitiset就是可以储存重复值的setvectorintv({3,4,5,1,3,7,9,3,5,4,4,4});multisetintmyset(v.begin(),v.end());for(autoe:myset){coute ;}coutendl;find:对multiset对象使用find返回的是中序遍历找到的第一个与它相等的值。erase:当用erase删除具体的值时会把multiset中等于该值的元素全部删除。vectorintv({3,4,5,1,3,7,9,3,5,4,4,4});multisetintmyset(v.begin(),v.end());myset.erase(4);//会把值为4的全部删除for(autoe:myset){coute ;}cout:cout在multiset中就比较实用它可以返回对象中与所传参数值相同的个数vectorintv({3,4,5,1,3,7,9,3,5,4,4,4});multisetintmyset(v.begin(),v.end());coutmyset.count(2) myset.count(3) myset.count(4) myset.count(5)endl;四.mapmap与set一样分为普通的map和multimap后者能在结构中储存多个相同的值。1.map的介绍其声明如下map就是key_val型的二叉搜索树。1.Key就是map底层关键字的类型T就是map底层value的类型2.map与set一样默认左子树放小右子树放大也可以通过传递仿函数来调整3.与set一样一般不需要传后两个参数4.中序遍历增删查改的效率为logN这里与set很大的不同就是map支持改但可以改的时val关键字key仍然不许改。2.pair模板类在库中有一个叫pair的模板类其声明如下它有两个模板参数它们分别是pair中两个成员变量的类型它的结构差不多是这样的typedefpairconstKey,Tvalue_type;templateclassT1,classT2structpair{typedefT1 first_type;typedefT2 second_type;T1 first;T2 second;pair():first(T1()),second(T2()){}pair(constT1a,constT2b):first(a),second(b){}};它可以储存两个不同类型的值比如我们可以把key和value储存给它然后用它来构造map对象。实际上map底层的红黑树节点中的数据就是使用pairkey,val键值对来储存的。当我们创建一个储存pair类型的vector再对其进行匿名插入时vectorpairint,stringv;v.push_back(pairint,string(1,one));可见要反复写pair的模板参数类型还是比较麻烦的因此库中给了一个函数模板可以让我们更轻松的使用匿名插入templateclassT1,classT2inlinepairT1,T2make_pair(T1 x,T2 y){return(pairT1,T2(x,y));}有了这个我们就可以vectorpairint,stringv;v.push_back(make_pair(1,one));3.map的构造与迭代器构造map的构造有无参构造、拷贝构造、初始化列表构造和迭代器区间构造。用初始化列表构造时初始化列表储存的数据类型必须时pair类型mapstring,stringmy_map{{left,左边},{right,右边},{front,前面}};迭代器map的迭代器与set的差不多区别map的迭代器解引用后返回的是一个键值对所以不能直接打印它解引用后的值需要配合-或’.来使用mapstring,stringmy_map{{left,左边},{right,右边},{front,前面}};for(autoit:my_map)//其迭代器返回的是pair指针it类型的是pair{coutit.first:it.secondendl;//first指的是keysecond指的是val}4.map的增删查insertmap支持单值插入也支持迭代器区间插入中间的为指定位置插入但一般不会用。只插入一个值时返回值为pairiterator,bool类型如果插入成功(map中没有与插入元素相等的值)first就是指向这个新插入的元素second的值为true如果插入失败(map中有与插入元素相等的值):first就指向与参数相等的元素的位置second为false。set的insert返回值也是这样的。mapstring,stringmy_map{{left,左边},{right,右边},{front,前面}};pairstring,stringp1(back,后面);my_map.insert(p1);my_map.insert(pairstring,string(on,上面));my_map.insert(make_pair(student,学生));for(autoit:my_map){coutit.first:it.secondendl;}erase:其功能与set一样但需要注意的是map的数据虽然有键值对pair储存但不用迭代器指定元素删除时参数只需要传一个与key类型一样的参数即可而不是传一个pairmy_map.erase(on);find:find所传参数也是只有一个和key类型相同的值如果成功找到则返回对应的迭代器没找到则返回map::end.lower_bound和upper_bound其用法与set中的一样传参也是只用传一个与key类型相同的参数。5.operator[]map的[]重载与我们之前见到的都不一样map的迭代器是双向迭代器所以它无法通过下标访问其成员这也就表示着map的[]重载的不一样。它的声明如下[]中的值的类型是key类型的返回值的类型是value类型的。当我们传入的元素已经存在于map中时它会放回该值再map中对应的value的引用我们就可以对其进行修改当我们传入的元素不存在于map中时它就相当于一个insert。mapstring,stringmy_map{{left,左边},{right,右边},{front,前面}};my_map[on]上面;//相当于insert一个{on,上面”}my_map[left]左;//对my_map中的{left,左边}进行了修改;五.multimapmultimap与map的区别就在于它允许key值相同的元素存在其对应的value值可同可不同。还有需要注意的是multimap没有[]重载。equal_range该接口在set、multiset、map都有。它的作用是传入一个key类型的值会返回一个pairiterator,iterator的键值对fisrt是找到的第一个大于等于参数的元素所对应的迭代器second是找到的第一个大于该参数的元素所对应的迭代器。也就是说它的功能相当于lower_bound和upper_bound的结合返回一个迭代器区间其中的值全部相等。