侯捷《STL源码剖析》 | 容器的结构和分类(史上最简明的介绍）

容器的分类

序列式容器（sequence container）

• array(数组)
• vector（向量）
• deque（双端队列）
• List（双向链表）
• forward list（单向链表）

stack、queue底层可以调用deque实现。

关联式容器（associative container)

• set / Multiset
• map / Multimap

set、map基于红黑树（RBtree）的实现。
set中元素不能重复，Multiset中可以存储重复元素。
map中key不能重复，Multimap中可以重复。

Multimap中键值key与元素value的映照关系是多对多的关系，因此没有定义[]操作运算，而应使用c.insert()操作。

散列式容器（unordered container)

• unordered set / Multiset
• unordered map / Multimap

基于散列表（hash table）的实现。
hash table散列之后，若出现冲突，一般使用链表串联起来。
hash table中每块用来散射的区域叫做bucket（篮子）。
bucket中可以承载多个物体。

HashTable实际实现时，单个bucket中物体的数量不能超过bucket的数量，否则，扩充bucket。

更多精彩文章，欢迎关注公众号“Li的白日呓语”。