【C++】set和map

set和map1、序列式容器和关联式容器前面STL中的部分容器如string、vector、list、deque、array、forward_list等这些容器统称为序列式容器因为逻辑结构为线性序列的数据结构两个位置存储的值之间⼀般没有紧密的关联关系比如交换⼀下他依旧是序列式容器。关联容器也是用来存储数据的与序列式容器不同的是关联式容器逻辑结构通常是非线性结构里面是key,value结构的键值对两个位置有紧密的关联关系交换⼀下他的存储结构就被破坏了。map和set底层是红黑树红黑树是一颗平衡二叉搜索树。set是key搜索场景的结构map是key/value搜索场景的结构。2、set2.1 set的介绍set是按照一定次序存储元素的容器在set中的元素的value也标识它并且每个value必须是唯一的set中的元素不能在容器中修改但可以从容器中插入或删除它们在内部set中的元素总是按照其内部比较对象指示的特定严格弱排序标准进行排序set容器通过key访问单个元素总是按照其内部比较对象所指示的特定严格弱排序set中的值不能修改数量可以变set底层是用红黑树实现增删查效率是O(㏒N)总结set两大核心特性自动去重不能存放相同元素插入重复值会直接失效自动升序排序容器内元素永远从小到大有序2.2 set的使用2.2.1 set的模版参数列表templateclassT,// set::key_type/value_typeclassComparelessT,// set::key_compare/value_compareclassAllocallocatorT// set::allocator_typeclassset;T是set中存放元素的类型成员类型key和value的混叠compare是仿函数Alloc是set中元素的空间管理方式2.2.2 set的构造构造类型标识完整函数声明构造空的setexplicit set (const key_compare comp key_compare(), const allocator_type alloc allocator_type());用[first, last)区间中的元素构造settemplateset (InputIterator first, InputIterator last,const key_compare comp key_compare(),const allocator_type alloc allocator_type());set的拷贝构造set (const set x);2.2.3 set的迭代器函数返回值作用begin()iterator返回指向集合最小元素的正向迭代器end()iterator返回集合末尾后一位无有效元素终止标记cbegin()const_iterator常量正向首迭代器只读cend()const_iterator常量正向尾后迭代器rbegin()reverse_iterator反向首迭代器指向最大元素rend()reverse_iterator反向尾后迭代器crbegin()const_reverse_iterator常量反向首迭代器crend()const_reverse_iterator常量反向尾后迭代器setints{5,1,5,3,4,2,6,83,9,10,22};// 中序排序去重setint::iterator its.begin();while(it!s.end()){// 普通迭代器也不支持修改// *it 1;cout*it ;it;}//输出1 2 3 4 5 6 9 10 22 83coutendl;2.2.4 set的增删查函数名功能分类核心作用返回值简易示例insert修改操作插入元素自动去重排序重复插入无效pairiterator, bools.insert(6);erase修改操作删除元素支持值 / 迭代器 / 区间三种传参删除迭代器无返回传值返回删除个数s.erase(6);swap修改操作交换两个同类型 set交换元素、比较器、分配器voids1.swap(s2);clear修改操作清空容器所有元素size 置 0voids.clear();find查找操作查找指定值找到返回对应迭代器未找到返回 end ()iterator / const_iteratorauto it s.find(3);count查找操作统计目标元素数量set 元素唯一仅返回 0 或 1size_tif(s.count(2))lower_bound边界查找返回第一个大于等于目标值的迭代器iterator / const_iterators.lower_bound(4);upper_bound边界查找返回第一个大于目标值的迭代器iterator / const_iterators.upper_bound(4);set的使用案例setints{5,1,5,3,4,2,6,83,9,10,22};setint::iterator its.begin();while(it!s.end()){// 普通迭代器也不支持修改// *it 1;cout*it ;it;}//输出1 2 3 4 5 6 9 10 22 83coutendl;s.insert(60);s.erase(6);for(autoe:s){coute ;}coutendl;//输出1 2 3 4 5 9 10 22 60 83//两个find函数时间复杂度不一样autoret1s.find(3);// O(logN)// auto ret1 find(s.begin(), s.end(), 3); // O(N)if(ret1!s.end()){cout找到3了endl;}else{cout没有找到endl;}if(s.count(3))//count用来计数如果count不为0则含有3{cout找到3了endl;}else{cout没有找到endl;}// [3, 9]// 3autoit1s.lower_bound(3);//3// 9autoit2s.upper_bound(9);//10// [it1, it2)for(autoitit1;it!it2;it){cout*it ;}coutendl;//输出3 4 5 9s.erase(it1,it2);//删除3 4 5 9for(autoe:s){coute ;}coutendl;//输出1 2 10 22 60 833、multisetmultiset是按照特定顺序存储元素的容器且其中元素可以重复在multiset中元素的value也标识了它在内部multiset中的元素总是按照其内部的比较对象指示的特定严格若序准则排序multiset的底层结构是二叉搜索树总结multiset的核心三大特性允许存放重复元素自动升序排序相同值会全部保留multiset和set的接口相同multiset的使用案例如下multisetints{5,1,5,3,4,2,6,83,5,5,9,9,22};//允许重复// 中序排序setint::iterator its.begin();while(it!s.end()){// 普通迭代器也不支持修改//*it 1;cout*it ;it;}coutendl;//输出1 2 3 4 5 5 5 5 6 9 9 22 83s.insert(5);for(autoe:s){coute ;}coutendl;//输出1 2 3 4 5 5 5 5 5 6 9 9 22 83intx;cinx;autoposs.find(x);//遍历所有等于x的元素while(pos!s.end()*posx){cout*pos ;pos;}coutendl;//输入5输出5 5 5 5 5couts.erase(5)endl;//返回值是本次删除的元素的总数量//输出5for(autoe:s){coute ;}coutendl;//输出1 2 3 4 6 9 9 22 83couts.count(9)endl;//剩余容器中有2个9输出24、map4.1 map的介绍map是关联容器它按照特定的顺序排序存储由键值key和value组合而成在map中键值key通常用于排序和唯一标识元素在map内部key与value通过成员类型value_type绑定在一起叫做pair总结map核心特性有序底层是红黑树内部从小到大排序键唯一同一个key只能有一条数据key不能修改pair的firstkey是const,不能改value可以修改4.2 map的使用4.2.1 map的模板参数说明templateclassKey,// map::key_typeclassT,// map::mapped_typeclassComparelessKey,// map::key_compareclassAllocallocatorpairconstKey,T//map::allocator_typeclassmap;key键值对key类型T键值对value类型Compare比较器的类型Alloc通过空间配置器来申请底层空间不需要用户传递4.2.2 map的构造构造函数类型函数原型核心功能与说明空构造默认构造explicit map (const key_compare comp key_compare(), const allocator_type alloc allocator_type());创建一个空的 map 容器可自定义 key 的比较规则comp和内存分配器alloc默认使用升序比较、标准分配器范围构造template map (InputIterator first, InputIterator last, const key_compare comp key_compare(), const allocator_type alloc allocator_type());从迭代器范围[first, last)中拷贝元素初始化 map支持自定义比较规则和分配器拷贝构造map (const map x);用已有的 map 对象x创建一个完全相同的副本4.2.3 map的迭代器函数名返回迭代器类型遍历方向读写权限begin()iterator 正向迭代器从小到大升序可读、可修改 valueend()iterator 正向尾后迭代器--rbegin()reverse_iterator 反向迭代器从大到小降序可读、可修改 valuerend()reverse_iterator 反向尾后迭代器--cbegin()const_iterator 常量正向迭代器从小到大升序仅可读禁止修改 valuecend()const_iterator 常量正向尾后迭代器--crbegin()const_reverse_iterator 常量反向迭代器从大到小降序仅可读禁止修改 valuecrend()const_reverse_iterator 常量反向尾后迭代器--4.2.4 map的容量函数名函数原型返回值功能说明代码示例empty()bool empty() const;true / false判断容器是否为空1. 无元素返回 true2. 存在元素返回 falseif(mp.empty()) cout 空容器;size()size_type size() const;无符号整数元素总个数获取 map 当前存储的键值对总数cout 元素数量 mp.size();4.2.5 map的元素访问Toperator[](constkey_typek);三个核心行为赋值写入已有该键直接覆盖对应的valuemapint,stringmp;mp[1]A;mp[1]B;// key1已存在覆盖值为B读取取值用下标读取已有键拿到value引用coutmp[1];// 输出Bmp[1]123;// 通过引用修改值自动插入访问不存在的key时自动新建键值对存入 mapvalue 默认初始化。string smp[99];// 原本无key99执行后自动插入 {99, }总结示例voidtest_map1(){mapstring,stringdict{{left,左边},{right,右边},{insert,插入},{string,字符串}};dict.insert(pairstring,string(sort,排序));dict.insert(make_pair(const,常量属性));dict.insert({string,字符串});// 推荐dict.insert({string,xxxx});// 插入失败插入只看keydict[set];// 插入dict[set]集合;// 修改dict[string]xxxx;// 修改dict[begin]开始;// 插入修改coutdict[set]endl;// 查找 输出集合}4.2.6 map中元素的修改函数重载形式核心功能返回值关键特性 示例insert1.insert(pairKey,T)2.insert({k,v})3.insert(first,last)插入键值对pairiterator, bool / iteratorkey 重复则插入失败不会覆盖原有 valuemp.insert({“apple”, “苹果”});erase重载 1size_type erase(const key_type k)根据 key 删除对应元素size_type0 或 1key 不存在不报错map 键唯一最多删 1 个int cnt mp.erase(“apple”);erase重载 2iterator erase(iterator it)删除迭代器指向单个元素被删元素的下一个迭代器必须保证 it 合法有效不能传 end ()auto it mp.find(2); mp.erase(it);erase重载 3void erase(iterator first, iterator last)删除区间[first, last)全部元素void无返回左闭右开区间批量删除一段连续元素mp.erase(mp.begin(), mp.find(3));swapvoid swap(map x)交换两个同类型 map 全部内容void只交换内部指针效率极高不拷贝元素mp1.swap(mp2);clearvoid clear()清空容器所有键值对void执行后size()0empty()truemp.clear();finditerator find(const key_type k)查找指定 keyiterator找到返回元素迭代器没找到返回end()不新增元素auto it mp.find(“test”);countsize_type count(const key_type k)统计 key 存在次数size_type0 或 1map 键唯一仅用来判断 key 是否存在if(mp.count(“test”)){}4.3 map的使用案例voidtest_map1(){pairstring,stringkv1(sort,排序);//pairstring, string kv2(left, 左边);//pairstring, string kv3(right, 右边);//pairstring, string kv4 { insert, 插入 };//mapstring, string dict { kv1, kv2, kv3};mapstring,stringdict{{left,左边},{right,右边},{insert,插入},{string,字符串}};dict.insert(pairstring,string(sort,排序));dict.insert(make_pair(const,常量属性));dict.insert({string,字符串});// 推荐dict.insert({string,xxxx});// 插入失败插入只看keydict[set];// 插入dict[set]集合;// 修改dict[string]xxxx;// 修改dict[begin]开始;// 插入修改coutdict[set]endl;// 查找//mapstring, string::iterator it dict.begin();autoitdict.begin();while(it!dict.end()){// key不能修改value可以修改// it-first x;it-secondx;//cout (*it).first : (*it).second endl;//cout it.operator-()-first : it-second endl;coutit-first:it-secondendl;it;}coutendl;/*for (auto kv : dict) { cout kv.first : kv.second endl; }*/for(auto[k,v]:dict){coutk:vendl;}// 结构化绑定 C14/17auto[x,y]kv1;//x1等价于kv1.first 的别名y1相当于kv1.second的别名auto[x1,y1]kv1;x1x;//只改副本不影响原kv1xk;string arr[]{苹果,西瓜,苹果,西瓜,苹果,苹果,西瓜,苹果,香蕉,苹果,香蕉};mapstring,intcountMap;//for (auto str : arr)//{// //mapstring, int::iterator it countMap.find(str);// auto it countMap.find(str);// if(it ! countMap.end())// {// it-second; //first是keysecond是valuefirst不能修改// }// else// {// countMap.insert({str, 1});// }//}for(autostr:arr){countMap[str];}for(auto[k,v]:countMap){coutk:vendl;}}5、multimap5.1 multimap的介绍multimap是关联式容器存储由key和value映射成的键值对key, value其中多个键值对之间的key是可以重复的在内部multimap中的元素总是通过内部的比较对象按照指定的特定严格弱排序标准对key进行排序的multimap以二叉搜索树的形式实现multimap核心特征总结map同一个key只能存1份key唯一multimap允许多个元素拥有完全相同的key一个key可以对应多组不同valueeg:mp.insert({1,A});mp.insert({1,B});// 合法同key共存注意multimap不支持 operator[] 下标运算符 mp[key]因为multimap存在重复key编译器无法确定你要访问哪一个key对应的valueinsert 永远插入成功5.2 multimap的使用multimap的接口可以参考mapvoidtest_map2(){multimapstring,stringdict{{left,左边},{right,右边},{insert,插入},{string,字符串}};dict.insert(pairstring,string(sort,排序));dict.insert(make_pair(const,常量属性));dict.insert({string,字符串});// 推荐dict.insert({string,xxxx});// 插入失败插入只看key}