前言
本文介绍了C++STL中的关联式容器map和set的相关概念，主要介绍了它们的概念和使用。
一、关联式容器
我们之前了解的STL容器中的vector、list、deque等都被称为序列式容器，因为它们的底层为线性序列的数据结构，存储的是元素本身。
那么什么是关联式容器呢？他与序列式容器又有什么区别呢？
实际上，关联式容器也是用来存储数据的，但它与序列是不同它所存储的是<key, value>结构的键值对，这种存储方式在进行数据检索时比序列式容器的效率高。
二、键值对
键值对是用于表示具有一一对应关系的一种结构，这种结构中一般只包含两个成员变量key和value，其中key代表键值，value表示与key对应的信息。
例如，英汉词典，单词与它的中文含义之间是一一对应的关系，即通过该词就能在词典中找到它的中文含义。那么单词就是key键值，中文含义就是value这个键值对应的信息。
SGI-STL中对于键值对的定义：
template <class T1, class T2> struct pair { typedef T1 first_type; typedef T2 second_type; T1 first; T2 second; pair() :first(T1()) ,second(T2()) {} pair(const T1& a,const T2& b) :first(T1(a)) ,second(T2(b)) {} };
三、树形结构的关联式容器
1.概念
根据应用场景的不同，STL共实现了两种不同结构的关联式容器：树形结构和哈希结构。
树形结构的关联式容器有四种：map、set、multimap、multiset。这四种容器的共同特点是：它们的底层都是一个平衡搜索树（红黑树），容器中的元素是一个有序的序列。
哈希结构的关联式容器有两种：unordermap、unorderset。它们的底层实现是哈希表。
2.set
set的介绍
- set是按照一定次序存储元素的容器，set中的元素总是按照内部比较对象（类型比较）所指示的特定排序准则进行排序，使用set的迭代器遍历set可以得到有序序列，注意：set中的元素默认按小于进行排序；
- 与map不同，map中存储的是键值对<key,value>，set中只放value，但是底层实际存放的是<value,value>构成的键值对；
- 在set中，元素的value也可以标识它（value就是key，类型为T），并且每一个value都必须是唯一的，即set中的元素是不能重复的，因此可以用set进行去重；
- set中的元素不能在容器中进行修改，只能进行增、删、查等操作；
- set查找某个元素的时间复杂度为：l o g 2 n log_2 nlog2n，set容器通过key访问单个元素的效率比unordered_set效率低，但是它允许根据顺序对元素进行直接迭代；
- set的底层是二叉搜索树（红黑树）。
set的使用
- set的模板参数列表
Compare 参数是比较器类型，一般不需要显示传递，如果无法比较（自定义类型），需要用户自己显示传递比较规则（一般情况下按照函数指针或者仿函数来传递）。 - set的构造
- set的迭代器
- set的容量
- set的操作
- set的应用举例
#include<set> int main() { int arr[] = { 1, 2, 5, 6, 4, 7, 32, 45, 6, 9, 10, 3}; set<int> si(arr, arr+sizeof(arr)/sizeof(arr[0])); cout << si.size() << endl; //正向打印si中的元素 for (auto e : si) { cout << e <<" "; } cout << endl; //逆向打印si中的元素 for (auto it = si.rbegin(); it != si.rend(); ++it) { cout << *it <<" "; } cout << endl; cout << si.count(3) << endl; return 0; }
运行截图：
3.map
map的介绍
- 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的使用
- map的模板参数列表
Compare 参数是比较器类型，一般不需要显示传递（缺省为小于比较，即升序排序），如果无法比较（自定义类型），需要用户自己显示传递比较规则（一般情况下按照函数指针或者仿函数来传递）。 - map的构造
- map的迭代器
- map的容量
- map的元素访问
- map的操作
大部分操作与set类似，参考set的使用即可。 - map的应用举例
#include<map> #include<string> int main() { map<string, string> m; m.insert(make_pair("peach", "桃子")); m.insert(pair<string, string>( "banana","香蕉")); m["apple"] = "苹果"; cout << m.size() << endl; cout << m.count("apple") << endl; for (auto it : m) { cout << it.first << ":" << it.second << endl; } //插入桃子 auto ret = m.insert(make_pair("peach", "桃子"));//如果插入成功ret.second是true；如果插入失败ret.second是false； if (ret.second)cout << "<peach, 桃子>不在m中，插入成功" << endl; else cout << "插入失败" << endl; //删除苹果 m.erase("apple"); if (m.count("apple")) cout << "苹果还在" << endl; else cout << "苹果已经被删除" << endl; return 0; }
4.multiset
与set的区别是，multiset可以存储重复的元素，其他的性质操作都与set相同。
用一个代码看一下它与set的区别：
#include <set>//set和multiset的头文件都是set void TestSet() { int array[] = { 2, 1, 3, 3, 9, 6, 0, 5, 8, 4, 7 }; // 注意：multiset在底层实际存储的是<int, int>的键值对 set<int> s(array, array + sizeof(array) / sizeof(array[0])); for (auto& e : s) cout << e << " "; cout << endl; } void TestmultiSet() { int array[] = { 2, 1, 3, 3, 9, 6, 0, 5, 8, 4, 7 }; // 注意：multiset在底层实际存储的是<int, int>的键值对 multiset<int> s(array, array + sizeof(array) / sizeof(array[0])); for (auto& e : s) cout << e << " "; cout << endl; } int main() { TestSet(); TestmultiSet(); return 0; }
5.multimap
与map的区别是map中的key是唯一的，multimap中的key是可以重复的，即多个键值对之间的key值可以重复。
性质、功能与map是类似的，但是multimap没有重载operator[]操作。
总结
以上就是今天要讲的内容，本文介绍了C++STL中的关联式容器map和set的相关概念。本文作者目前也是正在学习C++相关的知识，如果文章中的内容有错误或者不严谨的部分，欢迎大家在评论区指出，也欢迎大家在评论区提问、交流。
最后，如果本篇文章对你有所启发的话，希望可以多多支持作者，谢谢大家！
