STL中的关联容器分为set和map两大类，以及他们的衍生体multiset和multimap，这些容器均由红黑树（RB-tree）实现。另外，STL还提供了不在标准之外的关联式容器：hashtable以及以此为底层机制的hash_set，hash_map和他两的multi衍生体。
以红黑树和哈希表为底层结构构造的容器最大的不同是前者为直接排序而后者不是。
1.红黑树
我的这篇博客介绍了红黑树和AVL树的大概轮廓，具体插座和查找细节可以参考《算法导论》，此处不介绍这些细节了。红黑树是一种接近平衡的平衡二叉搜索树，拥有良好的查找、插入复杂度。
STL中的RB-tree提供了两种插入操作：insert_unique()和insert_equal()，前者表示被插入节点的key值独一无二，后者表示key可以相同。
注意：RB-tree与hashtable一样，仅处理key值操作，所有value值不处理，仅用于查找的返回。
2.set
set以RB-tree为底层数据结构，其key值和value值相同。我们不能通过set迭代器动态更改元素值，这是与其底层RB-tree有关，RB-tree只能操作动态增删和查找，而对树内结构的key值发生更改无法维护（至少默认没有维护），所以set的迭代器为const_iterator。set与list相同的某些性质是：当客户端对它进行元素新增操作或删除时，操作之前的迭代器依然有效。
面对关联容器，应该使用其所提供的find函数来搜索，而不是algorithm头内的find，因为后者是顺序遍历。
3.map
map与set不同的是其key值与value值不同，在RB-tree中的结点以pair形式存在。其余大同小异：Key值对应RB-tree中的排序值，调用RB-tree的insert_unique()进行插入。
4.multiset
multiset与set的唯一差别在于key值允许相同，所以调用的RB-tree接口为insert_equal()。
5.multimap
参考map和multiset。注意：multimap不是一个key值映射多个value，树中只有一个key值，而映射的value有多个。而是有不同的pair
6.hashtable
哈希表有不同的散列方式：线性探测散列、二次线性探测再散列、链地址法……在hashtable中采用的是链地址法：采用一维线性表（hashtable中的专有名词叫：buckets）维持hash后的值，每个线性表元素后面挂链表处理重复。其第一维查找复杂度为O(1)，而第二维链表只能顺序查找，插入操作为头插法。
在hashtable的实现中，buckets采用vector实现，链表则采用list。buckets大小采用特定的质数实现（存于__stl_prime_list中），每个链表默认大小不大于buckets的大小，如果大于则引发扩容调整：buckets扩大（选择__stl_prime_list中下一个比当前大的质数），老的链表进行重新哈希调整。调整的目的在于减少查找的时间复杂度。
hashtable中的哈希函数可以由用户指定，默认对于整数只能是取模操作，对于字符串（char *）则转为整数后再取模，对于string、double等类型不提供默认哈希函数，只能由用户指定哈希函数。
如果一个迭代器指向某一个链表的最后一个元素，则其++返回的迭代器是下一个链表的开头，这样我们就可以用来遍历了：首先迭代器指向第一个链表的开头，然后不断++，直至最后。
同样拥用insert_unique()和insert_equal()接口处理key值的唯一和相同。
注意：与RB-tree类似，仅处理key值操作，所有value值不处理，仅用于查找的返回。
7.hash_set
基于hashtable实现，key值与value一致，用于哈希处理，无法自动排序。
8.hash_map
基于hashtable实现，仅用key值进行哈希处理。与map不同的是不同自动排序。
9.hash_multiset
参见hash_set，唯一不同的在于哈希表中key值可以相同。
10.hash_multimap
参见hash_multiset，hash_map和multimap。
参考
《STL源码剖析》 http://vinllen.com/read-black-tree/
说明
装载请注明链接：http://vinllen.com/stlzhong-de-guan-lian-shi-rong-qi