关联容器
关联容器是c++中的一种数据结构，提供了一种通过键来访问值的方式。根据使用场景的不同，STL的关联容器有两种结构，树型结构和哈希结构。常见树形结构的关联容器有：map和set。map是一种键值对容器，里面存储的结构是<key，value>.set是一种集合容器，有序且唯一。常见的哈希结构的关联容器有unordered_map和unordered_set。
键值对
键值对用来表示具有一一对应关系的一种结构，该结构中包含两个成员变量key和value，key表示键值，value表示与key对应的值。我们常用的pair<key,value> 就是键值对。
下面观察STL源码中是如何定义pair的：
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) {} };
所以pair其实就是一个类模板，根据<>里的两个参数来实例化类，第一个参数表示key，第二个表示value。
pair的两个成员变量first表示key，second表示value。
set
set的介绍
在c++文档中是这么定义set的：
- set是按照一定次序存储元素的容器，其中
class Compare控制比较逻辑，默认是小于。可以是一个仿函数，也可以是一个函数指针。 - set中的key必须是唯一的。不能修改key但是可以删除或者插入一个key。
- 在内部，set中的元素总是按照其内部比较对象（类型比较）所指定的特定严格强弱排序准则进行排序。
- set访问元素的平均时间复杂度为O(logn).
- set的底层是通过二叉搜索树（红黑树）来实现的
与map等容器不同，set存储的元素其实只有value，在底层是<value,value>.所以在插入元素时，只需要提供value即可，不需要构造键值对。使用set的迭代器进行遍历set时，会得到一个有序的序列。这是因为遍历的方式其实是二叉搜索树的中序遍历。
set的使用
set的模板参数列表有三个：
T:元素类型Compare：用于控制set的比较逻辑，默认是小于
Alloc:控制set的空间管理方式，使用STL提供的空间管理配置器.
set的构造
函数声明1：
explicit set (const key_compare& comp = key_compare(), const allocator_type& alloc = allocator_type());
构造一个空的set，里面没有元素
函数声明2：
template <class InputIterator> set (InputIterator first, InputIterator last, const key_compare& comp = key_compare(), const allocator_type& alloc = allocator_type());
根据提供的范围[InputIterator,InputIerator last)里的值来一一构造。
函数声明3：
set (const set& x); • 1
拷贝构造，根据提供的一个set对象去构造一个一模一样的另一个set对象。
set的迭代器
begin和end
分别指向set第一个元素和最后一个元素的下一个位置。
rbegin和rend表示const修饰的begin和end。
rbegin和rend
方向迭代器，分别指向set最后一个元素的下一个位置和第一个元素的位置。
crbegin和crend表示被const修饰的 rbegin和rend。
注意，const迭代器并不是指迭代器本身不能被修改，而是指向的元素不能被修改。
set的容量
empty()
检测set中的元素是否为空，空返回true，否则false.
size（）
返回set中有效元素的个数
set的修改操作
下面讲一些比较常用的修改操作
insert
pair<iterator,bool> insert ( const value_type& x )
在set中插入元素x，实际上插入的是<x,x>构成的键值对，如果插入成功，返回一个迭代器和true构成的键值对。该迭代器指向插入set后的x。如果插入失败，说明x已经存在，返回一个迭代器和false构成的键值对。
erase
void erase ( iterator position ) void erase ( iterator first, iterator last )
- 删除set中position位置上的元素。
- 删除
[first,last)这个区间的所有元素
clear
void clear ( )
清空set中的所有元素
find
iterator find ( const key_type& x ) const
返回指向元素x的迭代器
count
size_type count ( const key_type& x ) const
返回set中值为x的元素的个数.
map
map的介绍
map的文档介绍：
- 键值对映射 ：map中的元素是一对键值对，每一个key都有一个value对应。
- 自动排序：与set类似，mao中的元素在插入的同时会进行排序，默认情况下是key小的排在前面。
- 唯一键：每个键在map中都是唯一的。
- map查找的时间复杂度是O(logn).
- 迭代器支持：支持使用迭代器来遍历map中的元素。本质上是搜索二叉树的中序遍历。
- 底层是用二叉搜索树（红黑树）实现的。
- 可以使用
[key]访问对应的value
map和set的特性其实很像，只不过map中的元素更像是一个键值对。
map的构造
函数声明1
explicit map (const key_compare& comp = key_compare(), const allocator_type& alloc = allocator_type());
构造一个空的map对象，没有元素。
函数声明2
template <class InputIterator> map (InputIterator first, InputIterator last, const key_compare& comp = key_compare(), const allocator_type& alloc = allocator_type());
迭代器范围构造map，根据[first，last)范围内的元素一一构造出与其对应的map元素。
函数声明3
map (const map& x);
拷贝构造
map的迭代器
begin和end
begin:首元素的位置，end最后一个元素的下一个位置
cbegin和cend：与begin和end意义相同，但cbegin和cend所指向的元素不能修改
rbegin和rend
反向迭代器，rbegin在end位置，rend在begin位置，其++和–操作与begin和end操作移动相反
crbegin和crend：与rbegin和rend意义相同，但crbegin和crend所指向的元素不能修改
map的[]访问
当访问的key不存在，[key]操作会先将key插入到map中，返回默认的value.否则直接返回其value值。
map的修改操作
multiset
multiset的文档介绍：
multiset和set的区别就在于multiset可以存相同的元素。因此我们可以使用multiset对数组进行排序。
其内部结构和set都是一样的，都是用二叉搜索树（红黑树）实现的。
multimap
multimap的文档介绍：
multimap和map的区别就在于multimap可以存重复的key。此外，multimap不支持[key]操作
其内部结构和map都是一样的，都是用二叉搜索树（红黑树）实现的。
