C++语法 | 相关知识点 | 可以通过点击 | 以下链接进行学习 | 一起加油! |
---|---|---|---|---|
命名空间 | 缺省参数与函数重载 | C++相关特性 | 类和对象-上篇 | 类和对象-中篇 |
类和对象-下篇 | 日期类 | C/C++内存管理 | 模板初阶 | String使用 |
String模拟实现 | Vector使用及其模拟实现 | List使用及其模拟实现 | 容器适配器Stack与Queue | Priority Queue与仿函数 |
模板进阶-模板特化 | 面向对象三大特性-继承机制 | 面向对象三大特性-多态机制 |
大家好,我是店小二!今天为大家带来 C++ STL 树形结构容器全解析:map、set、multimap、multiset 的使用与区别。本次分享主要聚焦于这几种容器的使用方法,帮助大家了解它们的基本功能和常用接口。需要提前说明的是,今天的内容偏重实用性,旨在让大家快速上手,没有深入探讨底层原理。希望能对大家有所帮助!
?个人主页:是店小二呀
?C语言笔记专栏:C语言笔记
?C++笔记专栏: C++笔记
?初阶数据结构笔记专栏: 初阶数据结构笔记
?Linux笔记专栏: Linux笔记
?喜欢的诗句:无人扶我青云志 我自踏雪至山巅
文章目录
一、序列式容器与关联式容器二、键值对三、树形结构的关联式容器 四、set4.1 set介绍3.2 set相关接口使用3.2.1 set构造函数3.2.2 set常见接口 3.3 set相关题目练习 五、multiset 5.1 multiset介绍5.2 multiset使用 六、map6.1 map介绍6.2 掌握pair与make_pair6.2.1 pair6.2.2 make_pair6.2.3 pair与make_pair区别 6.3 map对象多种插入场景6.3.1 map当中列表初始化 6.4 将数据存在结构体6.5 map相关接口使用6.5.1 erase6.5.2 operaor[]6.5.3 insert实现operator[]6.5.4 operaort[] 底层逻辑 八、map使用方面8.1 operator[]使用8.2 如何统计水果出现的次数并排序(map用法和排序稳定性)8.3 前K个高频单词 九、multimap
一、序列式容器与关联式容器
序列式容器:底层为线性序列的数据结构,里面存储的是元素本身,单纯的存储数据,存储的数据和数据之间没有啥关联,比如,vector、list、deque等容器关联式容器:也是用于存储数据的,与序列式容器不同的是,其里面存储的是<key, value>结构的键值对,在数据检索时比序列式容器效率更高。不仅仅是存储数据,一般还可以查找数据,存储的数据和数据之间很强关联性二、键值对
用来表示具有一一对应关系的一种结构,该结构中一般只包含两个成员变量key和value,其中key代表健值,而value表示与key对应的信息。比如:字典中必然存在英文单词与其对应的中文含义
三、树形结构的关联式容器
根据应用场景的不同,STL总共实现了两种不同结构的关联式容器:树型结构与哈希结构。树型结构的关联式容器主要有四种:map、set、multimap、multiset。这四种容器的共同点是:使用平衡搜索树(即红黑树)作为其底层结果,采用中序遍历,容器中的元素是一个有序的序列
四、set
4.1 set介绍
[set文档介绍](set - C++ Reference (cplusplus.com)):
set是按照一定次序存储元素的容器在set中,元素的value也标识它(value就是key,类型为T),并且每个value必须是唯一的,对此插入元素时,只需要插入value即可,不需要构造键值对在内部,set中的元素总是按照其内部比较对象(类型比较)所指示的特定严格弱排序准则进行排序set中的元素不可以重复(因此可以使用set进行去重)set中的元素默认按照小于来比较set中查找某个元素,时间复杂度为:O(logn)set中的元素不允许修改,保证数据排序和搜索树结构set容器通过key访问单个元素的速度通常比unordered_set容器慢,但它们允许根据顺序对子集进行直接迭代与map/multimap不同,map/multimap中存储的是真正的键值对<key, value>,set中只放value,但在底层实际存放的是由<value, value>构成的键值对set中的底层使用二叉搜索树(红黑树)来实现3.2 set相关接口使用
提前声明:set和map容器接口在使用方面是类型的,在set和map章节对于学习过的知识点不会过于展开描述,展示几个常见的接口。
map的模板参数说明:
T: set中存放元素的类型,实际在底层存储<value, value>的键值对。Compare:set中元素默认按照小于来比较,仿函数Alloc:set中元素空间的管理方式,使用STL提供的空间配置器管理set属于K模型搜索,具有去重和排序的功能。3.2.1 set构造函数
1.set无参构造
int main(){set<int> s1;s1.insert(1);s1.insert(2);s1.insert(3);s1.insert(1);set<int> ::iterator it = s1.begin();while (it != s1.end()){//*it = 1;cout << *it << " ";++it;}cout << endl;return 0;}
其中需要知道set中的元素不允许修改,保证数据排序和搜索树结构。
2.set迭代器区间构造
int main(){ vector<int> v = { 3, 2, 8, 1, 10, 2 }; set<int> s(v.begin(), v.end()); for (auto e : s) { cout << e << " "; } cout << endl; return 0;}
3.调用列表初始化
int main(){ set<int> s3 = { 3,2,8,1,10,2 }; for (auto e : s3) { cout << e << " "; } cout << endl; s3.erase(8); s3.erase(18); for (auto e : s3) { cout << e << " "; } cout << endl; auto pos = s3.find(10); if (pos != s3.end()) { cout << *pos << endl; s3.erase(pos); } else { cout << "找不到" << endl; } for (auto e : s3) { cout << e << " "; } cout << endl; return 0;}
3.2.2 set常见接口
#include <set>void TestSet(){ // 用数组array中的元素构造set int array[] = { 1, 3, 5, 7, 9, 2, 4, 6, 8, 0, 1, 3, 5, 7, 9, 2, 4, 6, 8, 0 }; set<int> s(array, array+sizeof(array)/sizeof(array)); cout << s.size() << endl; // 正向打印set中的元素,从打印结果中可以看出:set可去重 for (auto& e : s) cout << e << " "; cout << endl; // 使用迭代器逆向打印set中的元素 for (auto it = s.rbegin(); it != s.rend(); ++it) cout << *it << " "; cout << endl; // set中值为3的元素出现了几次 cout << s.count(3) << endl;}
3.3 set相关题目练习
我们需要知道,set是间接实现去重操作,如果存在该值就不再插入到set里面。
class Solution{ public: vector<int> intersection(vector<int>& nums1, vector<int>& nums2) { set<int> s1(nums1.begin(), nums1.end()); set<int> s2(nums2.begin(), nums2.end()); auto it1 = s1.begin(); auto it2 = s2.begin(); vector<int> v; while(it1 != s1.end() && it2 != s2.end()) { if(*it1 > *it2) it2++; else if(*it1 < *it2) it1++; else if(*it1 == *it2) { v.push_back(*it1); it1++;it2++; } } return v; }};这里拿出来的目的是体现了set的排序和去重的作用,在这种情况下可以帮助我们快速的做题。
五、multiset
5.1 multiset介绍
multiset当作可以set使用,同样属于key模型,区别在于muliset允许数据冗余也就是不去除重复数据。muliset是一种允许元素重复出现的集合类型,你可以像使用set一样使用它,但它会保留重复的元素并且不进行去重操作。
5.2 multiset使用
int main(){multiset<int> s1;s1.insert(1);s1.insert(11);s1.insert(3);s1.insert(1);s1.insert(4);s1.insert(2);s1.insert(4);s1.insert(2);s1.insert(1);s1.insert(2);s1.insert(1);multiset<int>::iterator it = s1.begin();while (it != s1.end()){//*it = 1;cout << *it << " ";++it;}cout << endl;auto pos = s1.find(2);while (pos != s1.end() && *pos == 2){cout << *pos << " ";++pos;}return 0;}
六、map
6.1 map介绍
[map文档介绍](map - C++ Reference (cplusplus.com)):
map是关联容器,它按照特定的次序(按照key来比较)存储由键值key和值value组合而成的元素在map中,键值key通常用于排序和唯一地标识元素,而值value中存储与此键值key关联的内容。键值key和值value的类型可能不同,并且在map的内部,key与value通过成员类型value_type绑定在一起,为其取别名称为pair:typedef pair<const key, T> value_type;
在内部,map中的元素总是按照键值key进行比较排序的。map中通过键值访问单个元素的速度通常比unordered_map容器慢,但map允许根据顺序对元素进行直接迭代(即对map中的元素进行迭代时,可以得到一个有序的序列)。map支持下标访问符,即在[]中放入key,就可以找到与key对应的value。map通常被实现为二叉搜索树(更准确的说:平衡二叉搜索树(红黑树))。 map的模板参数说明:
key: 键值对中key的类型T: 键值对中value的类型Compare: 比较器的类型,map中的元素是按照key来比较的,缺省情况下按照小于来比较,一般情况下(内置类型元素)该参数不需要传递,如果无法比较时(自定义类型),需要用户自己显式传递比较规则(一般情况下按照函数指针或者仿函数来传递)Alloc:通过空间配置器来申请底层空间,不需要用户传递,除非用户不想使用标准库提供的空间配置器注意:在使用map时,需要包含头文件key与value通过成员类型value_type绑定在一起,为其取别名称为pair:typedef pair<const key, T> value_type;
的意思就是说,之前key和value是单个单个的存储的,现在将key和value存在一个结构中。
6.2 掌握pair与make_pair
6.2.1 pair
在 C++ 中,pair
确实是一个模板类,允许用户将两个不同类型的数据组合在一起。模板的关键特性是它能够为不同类型的元素提供通用的实现,因此 pair
能够处理任意类型的两个数据项。
pair底层实现逻辑
template <class T1, class T2>struct pair{typedef T1 first_type;typedef T2 second_type; //KeyT1 first; //valueT2 second;pair():first(T1(), T2()){}pair(const T1& a, const T2& b):first(a), second(b){}};
6.2.2 make_pair
make_pair
是 C++ 标准库中的一个函数模板,用于简化 std::pair
对象的创建。它可以自动推导出 pair
的类型,因此在构造 pair
对象时,无需显式地指定模板参数类型。
6.2.3 pair与make_pair区别
相对于pair使用中需要明确数据类型,而make_pair是函数模板可以自动去推类型
函数模板:支持类型推导,编译器根据传递的参数自动推导模板参数。类模板:不支持类型推导,必须显式指定模板参数类型,因为类的结构和使用方式更复杂,无法通过简单的参数推导出类型。6.3 map对象多种插入场景
int main(){ map<string, string> dict; pair<string, string> kv1("sort", "排序"); dict.insert(kv1); //使用匿名对象 dict.insert(pair<string, string>("left", "左边")); //使用make_pair,省略类型的书写 dict.insert(make_pair("right", "右边")); //隐式类型转化 pair<string, string> kv2("string", "字符串"); dict.insert({ "string", "字符串" }); //初始化列表 map<string,string> dic2 = { {"string", "字符串"}, {"left", "左边"}, {"right", "右边"} }; return 0;}
**关于以上两种map初始化的方式,推荐使用第一种写法。**同时需要注意的是dict.insert({ "string", "字符串" });
这里不是列表初始化initializelist,而是调用pair构造函数,强制类型转化为pair类型插入数据。
6.3.1 map当中列表初始化
而对于map<string,string> dic2 = { {"string", "字符串"}, {"left", "左边"}, {"right", "右边"} };
属于初始化列表, std::map
的构造函数接受一个std::initializer_list<std::pair<const Key, T>>
类型的参数。所以当你使用 {"i", "dd"}
进行初始化时,它会被转换为 std::pair<const std::string, std::string>
类型,然后添加到 map
中。
6.4 将数据存在结构体
我们知道map中的元素类型是pair或make_pair,但是为什么map不分开来存储数据呢?而是需要将数据放在一个结构体中,通过结构体间接访问这些对象。
//map<string, string>::iterator it = dict.begin();//auto的作用就重复体现到了auto it = dict.begin();while (it != dict.end()){ // iterator key不能修改 value可以修改 // const_iterator key不能修改 value不能修改 //it->first += 'x'; it->second += 'x'; ++it;}cout << endl;
关于key不是能被修改的。在map中,键值key通常用于排序和唯一地标识元素,而值value中存储与此键值key关联的内容。对此key是不能随意修改的,可能会破坏搜索树结构,但key所对的内容value是支持修改的。
auto it = dict.begin();while (it != dict.end()){ cout << (*it).first << ":" << (*it).second << endl;}cout << endl;
对于如果不将key和value放在同一个结构体中,operator *只能返回一个值,但是我们希望可以得到key也可以得到value的值,对此将这两个变量放在结构体中,间接调用这两个变量,就会不出现冲突。对于上面的写法过于麻烦,这里喜欢使用→来解引用。
底层是调用operator ->接口,这里编译器会省略一个箭头进行优化,使得使用更加便捷。
6.5 map相关接口使用
6.5.1 erase
这里使用insert不会出现迭代器实现的问题,而erase可能会出现迭代器失效的问题,这里搜索树可以看成链表的加强版。
6.5.2 operaor[]
首先这里operator不是通过下标进行访问,而是通过key来进行访问对应value。关于operator[]实现不是通过find来实现而是通过insert来实现。
6.5.3 insert实现operator[]
解释上面两段话
key存在,插入失败,返回 ->pair < 存在的key所在节点的迭代器,false>
key不存在,插入成功,返回 ->pair < 新插入key所在节点的迭代器,true>
对此我们可以看出来,insert在find功能基础上增加了插入的功能。这里insert的功能就是查找 + 插入(如果该元素存在,就是查找)
6.5.4 operaort[] 底层逻辑
V& operator[](const K& key){ // 不管插入成功还是失败,pair中iterator始终指向key所在节点的iterator //这个V()就是调用默认构造,不是一个明确的数值 pair<iterator, bool> ret = this->insert(make_pair(key, V())); iterator it = ret.fisrt; return it->second;}
八、map使用方面
8.1 operator[]使用
int main(){ map<string, string> dict; dict.insert({ "string", "字符串" }); // 插入(一般不会这么用,单纯的插入) dict["right"]; // 插入left + 修改 left对应内容 dict["left"] = "左边"; // "查找" cout << dict["string"] << endl; // 修改 dict["right"] = "右边"; string str; cin >> str; if (dict.count(str)) { cout << "在" << endl; } else { cout << "不在" << endl; } return 0;}
8.2 如何统计水果出现的次数并排序(map用法和排序稳定性)
瑕疵版本
string arr[] = { "苹果", "西瓜", "苹果", "西瓜", "苹果", "苹果", "西瓜", "苹果", "香蕉", "苹果", "香蕉","苹果","草莓", "苹果","草莓" };map<string, int> countMap;for (auto& e : arr){ auto it = countMap.find(e); if (it != countMap.end()) { it->second++; } else { //const pair<string, int>& val = { e, 1 }; countMap.insert({ e, 1 }); }}for (auto& kv : countMap){ cout << kv.first << ":" << kv.second << endl;}cout << endl;
优化版本
通过operator[]学习,我们可以对上面代码进行优化。
string arr[] = { "苹果", "西瓜", "苹果", "西瓜", "苹果", "苹果", "西瓜","苹果", "香蕉", "苹果", "香蕉","苹果","草莓", "苹果","草莓" };map<string, int> countMap;for (auto& e : arr){countMap[e]++;}for (auto& kv : countMap){cout << kv.first << ":" << kv.second << endl;}cout << endl;
通过次数来排序
只需将countMap的first和second位置数据,分别存放在sortMap的second和first位置上就行了
map<int, string> sortMap;for (auto& kv : countMap){//sortMap[kv.second] = kv.first;sortMap.insert({ kv.second, kv.first });}cout << endl;for (auto& kv : sortMap){cout << kv.first << ":" << kv.second << endl;}cout << endl;}
这里问题就是香蕉不见。对此我们知道map底层是通过搜索树实现的,而二叉搜索树是不允许冗余数据,并且是通过K对比较的,如果出现重复的K不会进行插入操作。(现在是次数对内容,而不是内容对次数,搞清楚K现在是谁)
multimap允许冗余
真的需要排序,可以使用multimap 允许冗余.
8.3 前K个高频单词
如果是单纯排序话,可以符合按照次数进行排序,但是无法满足第二个需求,对此我们改写排序内部逻辑。
将内容插入map时完成了按照字典序排序的需求,但是接下来的快速排序属于不稳定排序,会破坏之前元素之间的相对位置,我们也可以将问题转换为使用一个稳定性好的排序,比如归并排序,map也提供了一个接口stable是稳定排序。
九、multimap
外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传
multimap使用事项:
Multimaps是关联式容器,它按照特定的顺序,存储由key和value映射成的键值对<key,value>,其中多个键值对之间的key是可以重复的在multimap中,通常按照key排序和惟一地标识元素,而映射的value存储与key关联的内容。key和value的类型可能不同,通过multimap内部的成员类型value_type组合在一起,value_type是组合key和value的键值对:typedef pair<const Key, T> value_type;在内部,multimap中的元素总是通过其内部比较对象,按照指定的特定严格弱排序标准对key进行排序的。multimap通过key访问单个元素的速度通常比unordered_multimap容器慢,但是使用迭代器直接遍历multimap中的元素可以得到关于key有序的序列。multimap在底层用二叉搜索树(红黑树)来实现。multimap中的key是可以重复的。multimap中的元素默认将key按照小于来比较multimap中没有重载operator[]操作,允许数据冗余,那么查找有冲突使用时与map包含的头文件相同以上就是本篇文章的所有内容,在此感谢大家的观看!这里是店小二呀C++笔记,希望对你在学习C++语言旅途中有所帮助!