杭州网站设计网页,宿迁房产网查备案,做推送的网站推荐,wordpress 做api接口在本专栏的往期文章中#xff0c;我们已经学习了STL的部分容器#xff0c;如vector、list、stack、queue等#xff0c;这些容器统称为序列式容器#xff0c;因为其底层是线性序列的数据结构#xff0c;里面存储的是元素本身。而本篇文章我们要来认识一下关联式容器。
我们已经学习了STL的部分容器如vector、list、stack、queue等这些容器统称为序列式容器因为其底层是线性序列的数据结构里面存储的是元素本身。而本篇文章我们要来认识一下关联式容器。
关联式容器
在介绍关联式容器之前先来回顾一下已经学习的数据结构9——二叉搜索树在这篇文章中我们认识了什么是K模型和KV模型 K模型只有Key作为关键码结构中只需要存储Key关键码即为需要搜索到的值。 KV模型每一个关键码key都有与之对应的值Value即的键值对。 有了这个前提我们就可以认为 关联式容器就是KV模型的一种应用关联式容器也是用来存储数据的与序列式容器不同的是其里面存储的是结构的键值对在数据检索时比序列式容器效率更高。 根据应用场景的不同STL一共实现了两种不同结构的管理式容器树型结构与哈希结构。树型结 构的关联式容器主要有四种map、set、multimap、multiset。这四种容器的共同点是使用平衡搜索树(平衡搜索树是一种二叉搜索树)作为其底层结果容器中的元素是一个有序的序列。
set
set的官网介绍 1. set是按照一定次序存储元素的容器 2. 在set中元素的value也标识它(value就是key类型为T)并且每个value必须是唯一的。 set中的元素不能在容器中修改(元素总是const)但是可以从容器中插入或删除它们 3. 在内部set中的元素总是按照其内部比较对象(类型比较)所指示的特定严格弱排序准则进行排序 4. set容器通过key访问单个元素的速度通常比unordered_set容器慢但它们允许根据顺序对 子集进行直接迭代 5. set在底层是用二叉搜索树(红黑树)实现的。 set的使用
插入
int main()
{setint s;//1.插入s.insert(8);s.insert(1);s.insert(7);s.insert(13);s.insert(6);s.insert(3);s.insert(5);s.insert(9);s.insert(14);s.insert(9);return 0;
}
遍历
int main()
{setint s;//1.插入s.insert(8);s.insert(1);s.insert(7);s.insert(13);s.insert(6);s.insert(3);s.insert(5);s.insert(9);s.insert(14);s.insert(9);//2.迭代器遍历setint::iterator it s.begin();while (it ! s.end()){cout *it ;it;}cout endl;//3.范围for遍历for (auto e : s){cout e ;}cout endl;return 0;
} 查找
//4.查找setint::iterator pos s.find(14);if (pos ! s.end()){cout 已找到 endl;} 删除
//5.删除//① 用此方法删除目标值存在就删除不存在不做任何处理s.erase(2);s.erase(1);for (auto e : s){cout e ;}cout endl;//② 用此方法删除目标值存在就删除不存在会程序报错pos s.find(8);s.erase(pos);for (auto e : s){cout e ;}cout endl;pos s.find(1);s.erase(pos); lower_bound与upper_bound
//6.lower_bound与upper_bound 3 5 6 7 9 13 14auto start s.lower_bound(3); //lower_bound返回的值valcout *start endl;auto finish s.upper_bound(7); //upper_bound的返回值valcout *finish endl;//找区间[3,7]//while (start ! finish)//{// cout *start ;// start;//}//cout endl;//删除区间[3,7]s.erase(start, finish);for (auto e : s){cout e ;}cout endl; set小结 ①与map/multimap不同map/multimap中存储的是真正的键值对key,valueset中只放 value但在底层实际存放的是由value,value构成的键值对 ②set中插入元素时只需要插入value即可不需要构造键值对 ③set中的元素不可以重复(因此可以使用set进行去重) ④使用set的迭代器遍历set中的元素可以得到有序序列 ⑤set中的元素默认按照小于来比较 ⑥set中查找某个元素时间复杂度为log_2 n ⑦set中的元素不允许修改(因为修改之后不能保证二叉搜索树的有序性) ⑧set中的底层使用二叉搜索树(红黑树)来实现。 multiset
multiset的官网介绍 1. multiset是按照特定顺序存储元素的容器其中元素是可以重复的 2. 在multiset中元素的value也会识别它(因为multiset中本身存储的就是value,value组成的键值对因此value本身就是keykey就是value类型为T),multiset元素的值不能在容器中进行修改(因为元素总是const的)但可以从容器中插入或删除 3. 在内部multiset中的元素总是按照其内部比较规则(类型比较)所指示的特定严格弱排序准则进行排序 4. multiset容器通过key访问单个元素的速度通常比unordered_multiset容器慢但当使用迭代器遍历时会得到一个有序序列 5. multiset底层结构为二叉搜索树(红黑树)。 multiset的使用
multiset的使用与set的使用大致相同下面演示区别较大的地方
插入
int main()
{multisetint s;//1.插入s.insert(8);s.insert(1);s.insert(7);s.insert(13);s.insert(6);s.insert(3);s.insert(5);s.insert(9);s.insert(14);s.insert(9);s.insert(9);s.insert(9);s.insert(9);multisetint::iterator it s.begin();while (it ! s.end()){cout *it ;it;}cout endl;return 0;
} 也就是说set用来去重排序multiset用来排序 计数
//序列有几个9
cout s.count(9) endl; 查找 当序列中有多个重复的值时multiset的find返回中序遍历的第一个数 //3.查找it s.find(9);while (it ! s.end() *it 9){cout *it ;it;}cout endl; multiset小结 ①multiset中在底层中存储的是的键值对 ②mtltiset的插入接口中只需要插入即可 ③与set的区别是multiset中的元素可以重复set中value是唯一的 ④使用迭代器对multiset中的元素进行遍历可以得到有序的序列 ⑤multiset中的元素不能修改 ⑥在multiset中找某个元素时间复杂度为O(log_2 N) ⑦multiset的作用可以对元素进行排序。 map
map的官网介绍 1. map是关联式容器它是按照特定的次序(按照key来比较)存储是由键值key和值value组合而成的元素 2. 在map中键值key通常用于排序和唯一地标识元素而值value中存储与此键值key关联的内容。键值key和值value的类型可能不同并且在map的内部key与value通过成员类型 value_type绑定在一起为其取别名称为pair: typedef pair value_type; 3. 在内部map中的元素总是按照键值key进行比较排序的 4. map中通过键值访问单个元素的速度通常比unordered_map容器慢但map允许根据顺序对元素进行直接迭代(即对map中的元素进行迭代时可以得到一个有序的序列) 5. map支持下标访问符即在[ ]中放入key就可以找到与key对应的value 6. map通常被实现为二叉搜索树(更准确的说平衡二叉搜索树(红黑树))。 map的使用
插入
//1.插入mapstring, string dict;dict.insert(pairstring, string(pear, 梨));//pairstring, string kv(peach, 桃子);pairstring, string kv { peach, 桃子 };dict.insert(kv);//C11 多参数隐式类型转换构造函数dict.insert({ apple, 苹果 });//C98dict.insert(make_pair(banana, 香蕉));dict.insert(make_pair(banana, 香蕉2));
遍历
//2.遍历//①迭代器遍历mapstring, string::iterator it dict.begin();while (it ! dict.end()){//cout *it endl;//cout (*it).first (*it).second endl;cout it-first it-second endl;it;}cout endl;//②范围for遍历for (auto kv : dict){cout kv.first : kv.second endl;}cout endl;
结果如图 由打印结果可知
map的遍历顺序并不是按照插入顺序遍历的而是按照ASCII码表的顺序遍历的
map与set相似插入的key相同value不同不会插入也不会更新。
计数[ ]的使用 ①
//①string arr[] { 苹果, 西瓜, 苹果, 西瓜, 苹果, 苹果, 西瓜,
苹果, 香蕉, 苹果, 西瓜, 香蕉, 草莓 };mapstring, int countMap;for (auto e : arr){mapstring, int::iterator it countMap.find(e);if (it ! countMap.end()){it-second;}else{countMap.insert(make_pair(e, 1));}}for (auto kv : countMap){cout kv.first : kv.second endl;}cout endl;
结果如图 ②
operator[]的原理是 用key,T()构造一个键值对然后调用insert()函数将该键值对插入到map中 如果key已经存在插入失败insert函数返回该key所在位置的迭代器
如果key不存在插入成功insert函数返回新插入元素所在位置的迭代器operator[]函数最后将insert返回值键值对中的value返回
详解会体现在代码里
//②string arr[] { 苹果, 西瓜, 苹果, 西瓜, 苹果, 苹果, 西瓜,
苹果, 香蕉, 苹果, 西瓜, 香蕉, 草莓 };mapstring, int countMap;for (auto e : arr){pairmapstring, int::iterator, bool ret;ret countMap.insert(make_pair(e, 1));//insert的返回值类型为pair//而insert的返回值类型pair的第一个参数为iterator第二个参数为bool//若“e”已经存在则插入失败insert返回该“e”所在位置的迭代器和false//若“e”不存在则插入成功insert返回新插入元素所在位置的迭代器和true//而insert的返回值-迭代器解引用得到的也是pair类型此pair类型的第一个参数为key第二个参数为value//也可以理解为insert的返回值为(kv,bool)kv的返回值为(kv)if (ret.second false)//ret的first是kvsecond是bool{ret.first-second;//first是kvsecond是v}}for (auto kv : countMap){cout kv.first : kv.second endl;}cout endl; 上一段代码简单介绍map的 [ ] 是如何实现的
V operator[](const K key)
{pairiterator, bool ret insert(make_pair(key, V()));return ret.first-second;
}
那么②的代码就可以简写为
//②---③string arr[] { 苹果, 西瓜, 苹果, 西瓜, 苹果, 苹果, 西瓜,
苹果, 香蕉, 苹果, 西瓜, 香蕉, 草莓 };mapstring, int countMap;for (auto e : arr){countMap[e];}for (auto kv : countMap){cout kv.first : kv.second endl;}cout endl; 结果如图 []总结 所以[]又兼具
①插入②查找③修改④插入修改
int main()
{mapstring, string dict;dict.insert(make_pair(apple, 苹果));dict.insert(make_pair(pear, 梨));//插入dict[插入];//查找cout dict[pear] endl;//修改dict[apple] 大苹果;//插入修改dict[pear2] 梨2;for (auto kv : dict){cout kv.first : kv.second endl;}return 0;
} map小结 ①map中的的元素是键值对 ②map中的key是唯一的并且不能修改 ③默认按照小于的方式对key进行比较 ④map中的元素如果用迭代器去遍历可以得到一个有序的序列 ⑤map的底层为平衡搜索树(红黑树)查找效率比较高O(log_2 N) ⑥支持[]操作符operator[]中实际进行插入查找。 multimap
multimap的官网介绍 1. Multimaps是关联式容器它按照特定的顺序存储由key和value映射成的键值对其中多个键值对之间的key是可以重复的 2. 在multimap中通常按照key排序和惟一地标识元素而映射的value存储与key关联的内容。key和value的类型可能不同通过multimap内部的成员类型value_type组合在一起 value_type是组合key和value的键值对: typedef pair value_type; 3. 在内部multimap中的元素总是通过其内部比较对象按照指定的特定严格弱排序标准对 key进行排序的 4. multimap通过key访问单个元素的速度通常比unordered_multimap容器慢但是使用迭代 器直接遍历multimap中的元素可以得到关于key有序的序列 5. multimap在底层用二叉搜索树(红黑树)来实现。 multimap的使用 multimap与map类似不同点是multimap支持冗余 multimapstring, string dict;dict.insert(make_pair(banana, 香蕉));dict.insert(make_pair(banana, 香蕉2));dict.insert(make_pair(peach, 桃子));dict.insert(make_pair(peach, 桃子2));dict.insert(make_pair(pear, 梨));dict.insert(make_pair(apple, 苹果));for (auto kv : dict){cout kv.first : kv.second endl;}cout endl;
结果如图 multimap小结 ①multimap中的key是可以重复的 ② multimap中的元素默认将key按照小于来比较 ③multimap中没有重载operator[]操作(同学们可思考下为什么?) ④使用时与map包含的头文件相同。
