容器分类

容器大致分为两类

• 序列式容器
  • Array
  • Vector
  • Deque
  • List
  • Forward-List
• 关联式容器
  • 有序容器——使用红黑树实现
    • Set/Multiset
    • Map/Multimap
  • 不定序容器——使用哈希表实现
    • Unordered Set/Multiset
    • Unordered Map/Multimap

哈希表

最被广泛使用的哈希表实现方法：

• 哈希表中有许多篮子（bucket），每个篮子是一个链表，发生哈希碰撞时将元素加入链表

容器之间的实现方式

• 容器之间为“基层与衍生层”的关系
  • 衍生值的并非继承，而是复合（容器之间往往是has-a关系）
  • 如：stack中有一个deque、set中有一个rb_tree（红黑树）