一、关联式容器 

        与序列式容器相同，关联式容器也是用于存储数据的，不同的是，关联式容器里存储的是<key, value>结构的键值对，在数据检索时比序列式容器效率更高。

二、键值对

        用来表示具有一一对应的一种结构，该结构中一般只包含两个成员变量key和value，key代表键值，value表示与key对应的信息。

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(a), second(b) {}
};

三、树形结构的关联式容器

        根据应用场景的不同，STL总共实现了两种不同结构的关联式容器：树形结构和哈希结构。

        树形结构的关联式容器主要有四种：map、set、multimap、multiset，这种四种容器的共同点是：使用平衡搜索树（红黑树）作为其底层结构，容器中的元素是一个有序的序列。

四、map

1.map文档介绍

（1）map是关联式容器，它按照特定的次序（按key来比较）存储由键值key和值value组合而成的元素。

（2）在map中，键值key通常用于排序和唯一的标识元素，而值value中存储与此键值key关联的内容。键值key和value的类型可能不同，并且在map内部，key与value通过成员类型value_type绑定在一起，为其取别名称pair：typedef pair value_type。

（3）在内部，map中的元素总是按照键值key进行比较排序。

（4）map中通过键值访问单个元素的速度通常比unordered_map容器慢，但map允许根据顺序对元素进行直接迭代（即对map中的元素进行迭代时，可以得到一个有序的序列）。

（5）map支持下标访问符，即在[]中放入key，就可以找到与key对应的value。

（6）map通常被实现为二叉搜索树（更准确的说：平衡二叉搜索树（红黑树））。

2.map的使用

2.1 map的模板参数列表

template <class Key,                                 //map::key_typeclass T,                                   //map::mapped_typeclass Compare = less<Key>,                 //map::key_compareclass Alloc = allocator<pair<const Key, T>>//map::allocator_type
> class map;

Key：键值对中key的类型；

T：键值对中value的类型；

Compare：比较器的类型，map中的元素是按照key来比较的，缺省情况下按照小于来比较，一般情况下（内置类型元素）该参数不需要传递，如果无法比较时（自定义类型），需要用户自己显示传递比较规则（一般情况下按照函数指针或仿函数来传递）；

Alloc：通过空间配置器来申请底层空间，不需要用户传递，除非用户不想使用标准库提供的空间配置器。

2.2 map的构造

2.3 map的迭代器

 

2.4 map的容量与元素访问

当key不存在时，通过operator获取对应value时会发生什么？

        当key不存在时，operator[]会使用默认的value和key构造键值对然后插入map中，并返回该默认的value。

元素访问操作at()，其key不存在时，会发生什么？

        该函数也是通过key找到与之对应的value，然后返回其引用。与operator[]不同的是，当key1不存在时，at()函数会直接抛异常。

2.5 map中元素的修改

2.6 map总结

（1）map中的元素是键值对；

（2）map中的key是唯一的，并且不能修改；

（3）默认按照小于的方式对key进行比较；

（4）map中的元素如果用迭代器遍历，可以得到一个有序的序列；

（5）map的底层为平衡搜索树（红黑树），查找效率较高，为O()；

（6）map支持[]操作符，operator[]中实际进行插入查找。

五、multimap

1. multimap文档介绍

（1）multimap是关联式容器，它按照特定顺序，存储由key和value组成的键值对<key,value>，其中多个键值对之间的key是可以重复的。

（2）在multimap中，通常按照key排序和唯一的标识元素，而映射的value存储与key关联。key和value的类型可能不同，通过multimap内部的成员类型value_type组合在一起，value_type是组合key和value的键值对：typedef pair<const key, T> value_type。

（3）在内部，multimap中的元素总数通过其内部比较对象，按照指定的特定严格弱排序标准对key进行排序。

（4）multimap通过key访问单个元素的速度通常比unordered_multimap容器慢，但是使用迭代器直接遍历multimap中的元素可以得到关于key有序序列。

（5）multimap在底层使用的是二叉搜索树（红黑树）来实现。

注意：

        multimap与map的唯一不同就是：map的key是唯一的，而multimap的key是可以重复的。

2. multimap的使用

        multimap的功能与map类似，其接口可以参考map使用。唯一区别就是multimap的key可以重复，所以multimap也没有实现重载operator[]操作。

六、set

1.set文档介绍

（1）set是按照一定次序存储元素的容器。

（2）在set中，元素的value也标识它（value就是key，类型为T），并且每个value必须唯一。set中的元素不能在容器中修改（元素总是const），但是可以从容器中插入或删除它们。

（3）在内部，set中的元素总是按照其内部比较对象（类型比较）所指示的特定严格弱排序准则进行排序。

（4）set容器通过key访问单个元素的速度通常比unordered_set容器慢，但它们允许根据顺序对子集进行直接迭代。

（5）set底层采用的是二叉搜索树（红黑树）实现的。

注意：

（1）与map/multimap不同，map/multimap中存储的是真正的键值对<key, value>，set中只存放value，但在底层实际存放的是由<value, value>构成的键值对。

（2）set中插入元素时，只需要插入value即可，不需要构造键值对。

（3）set中元素不可以重复（因此可以使用set去重）。

（4）使用set迭代器遍历set中元素时，可以得到有序序列。

（5）set中的元素默认按照小于来比较（升序）。

（6）set中查找某个元素时，时间复杂度为

（7）set中的元素不允许修改。

（8）set中的底层是使用二叉搜索树（红黑树）来实现。

2.set的使用

2.1 set模板参数列表

template < class T,                        // set::key_type/value_typeclass Compare = less<T>,        // set::key_compare/value_compareclass Alloc = allocator<T>      // set::allocator_type> class set;

T：set中存放元素的类型，实际在底层存储<value, value>的键值对。

Compare：set中元素默认按照小于来比较。

Alloc：set中元素空间的管理方式，使用STL提供的空间配置器管理。

2.2 set的构造

2.3 set的迭代器

 2.4 set的容量

 2.5 set的修改操作

七、multiset

1. multiset文档介绍

（1）multiset是按照特定顺序存储元素的容器，其中元素是可以重复的。

（2）在multiset中，元素的value也会识别它（因为multiset中本身存储的就是<value,value>组成的键值对，因此value本身也是key，key就是value），multiset元素的值不能在容器中进行修改（因为元素总是const），但可以从容器中插入或删除。

（3）在multiset内部，元素总是按照其内部的比较规则所指示的特定严格弱排序准则进行排序。

（4）multiset容器通过key访问单个元素的速度通常比unordered_multiset容器慢，但当使用迭代器遍历时，可以得到一个有序序列。

（5）multiset底层结构为二叉搜索树（红黑树）。

总结：

（1）multiset在底层中存储的是<value,value>的键值对。

（2）multiset的插入接口中，只需要插入元素value即可。

（3）与set的区别：multiset中的元素可以重复，而set中的元素是唯一的。

（4）使用迭代器对multiset中的元素进行遍历，可以得到有序序列。

（5）multiset中的元素不能修改。

（6）在multiset中查找某个元素，时间复杂度为O（）。

（7）multiset的作用：可以对元素进行排序。

2. multiset的使用

        multiset的接口与set基本相同，可以参考set使用。