关联式容器（associative containers）
根据数据在容器中的排列特性，容器可分为序列式（sequence）和关联式（associative）两种。
标准的STL关联式容器分为set（集合）和map（映射表）两大类，以及两大类的衍生体multiset（多键集合）和multimap（多键映射表）。这些容器的底层机制均是以RB-tree（红黑树）完成。RB-tree也是一个独立的容器，但并不开放给外界使用。
此外，SGI STL还提供一个不在规格标准之列的关联式容器：hash table（散列表），以及以此hash table为底层机制而完成的hash_set（散列集合）、hash_map（散列映射表）、hash_multiset（散列多键集合）、hash_multimap（散列多键映射表）。
所谓关联式容器，观念上类似关联数据库：每个数据都有一个键值（key）和一个实值（value）。当元素被插入到关联式容器中时，容器内部结构（RB-tree或hash-table）便依照其键值大小，以某种特定规则将这个元素放置于适当的位置。
一般而言，关联式容器的内部结构是一个balance binary tree（平衡二叉树）以获得良好的效率。
关联式容器（associative containers）,布布扣,bubuko.com
原文：http://www.cnblogs.com/sage-blog/p/3903566.html