前言

本文介绍了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查找某个元素的时间复杂度为： $log_2 n$ ，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;
}