【C++】16. set 和 map

在之前的博客中，我们已经接触过STL中的部分容器，比如：vector、list、deque等，这些容器统称为序列式容器，因为其底层为线性序列的数据结构，里面存储的是元素本身。

我们这篇博客的内容是关联式容器？它与序列式容器有什么区别？
关联式容器也是用来存储数据的，与序列式容器不同的是，其里面存储的是<key, value>结构的键值对，在数据检索时比序列式容器效率更高。
关联式容器分为树形关联式容器和哈希关联式容器。

一、键值对

键值对用来表示具有一一对应关系的一种结构，该结构中一般只包含两个成员变量key和value，key代表键值，value表示与key对应的信息。比如：现在要建立一个英汉互译的字典，那该字典中必然有英文单词与其对应的中文含义，而且，英文单词与其中文含义是一一对应的关系，即通过该应该单词，在词典中就可以找到与其对应的中文含义。
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(a), second(b)
	{}
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14

二、树形关联式容器

树型结构的关联式容器主要有四种：map、set、multimap、multiset。这四种容器的共同点是：使用平衡搜索树(即红黑树)作为其底层结果，容器中的元素是一个有序的序列。下面一依次介绍每一个容器。

2.1 set

2.1.1 set的构造函数

2.1.2 set的迭代器

2.1.3 set的容量操作

2.1.4 set的修改操作

2.2 multiset

set和multiset的主要区别在于：set中存储的元素不能重复，而multiset中的元素可以重复

multiset中的find函数在查找时，总是查找到中序遍历到该元素的第一个位置

因此，set的作用是排序加去重，multiset的作用是排序

2.3 map

2.3.1 map的构造函数

2.3.2 set的迭代器

2.3.3 set的容量操作与元素访问

问题：当key不在map中时，通过operator获取对应value时会发生什么问题？
注意：在元素访问时，有一个与operator[]类似的操作at()(该函数不常用)函数，都是通过key找到与key对应的value然后返回其引用，不同的是：当key不存在时，operator[]用默认value与key构造键值对然后插入，返回该默认value，at()函数直接抛异常。

2.3.4 set的修改操作

1. map中的的元素是键值对
2. map中的key是唯一的，并且不能修改
3. 默认按照小于的方式对key进行比较
4. map中的元素如果用迭代器去遍历，可以得到一个有序的序列
5. map的底层为平衡搜索树(红黑树)，查找效率比较高$O(lo{g}_{2}N)$
6. 支持[]操作符，operator[]中实际进行插入查找。

2.4 multimap

map中的key是唯一的，而multimap中key是可以重复的。