C++(STL源码)：16---容器的分类与介绍（序列式容器、关联式容器）

一、容器介绍

• STL容器是由一些运用最广的一些数据结构实现出来的
• 常用的数据结构有array（数组）、list（链表）、tree（树）、stack（堆栈）、queue（队列）、hash table（散列表）、set（集合）、map（映射表）...等等
• 这些数据结构分为序列式（sequence）和关联式（associative）两种

容器种类

• 上图是各种容器的衍生层关系（这里所谓的衍生，并非派生关系，而是内含关系）
• 例如heap内涵一个vector、priority-queue内含一个heap、stack和queue都含一个deque、set/map/multiset/multimap都含有一个RB-tree、hash_都内含一个hashtbale

二、序列式容器

• 概念：所谓序列式容器，其中的元素都是可序的，但是未必都是有序的
• 分类：
  • vector、list、deque、stack、queue、priority-queue等
  • 其中stack、queue由于只是将deque改头换面而已，所以它们是一种配接器（adapter）
  • 备注：C++语言本身提供一个序列式array（不属于STL范畴）
• 详细介绍：
  • vector：
  • list：
  • deque：
  • stack：
  • queue：
  • heap：
  • priority_queue：
  • slist：

三、关联式容器

• 概念：关联式容器，每笔数据（每个数据）都有一个键值（key）和一个实值（value）
• 特点：
  • 当元素被插入到关联式容器中时，容器内部数据结构（RB-tree或hash-table等）依据其键值大小，以某种特定规则将这个元素放置于适当位置
  • 关联式容器没有头尾（只有最大元素和最小元素），所以不会有push_back()、push_front()、pop_back()、pop_front()、begin()、end()等操作
• 分类：
  • 分为set（集合）、map（映射表）两大类，以及两大类的衍生体multiset（多键集合）、multimap（多键映射表）
  • SGI STL还提供了一个不在标准规格之列的关联式容器：hash table（散列表）以及以此hash table为底层机制而完成的hash_set（散列集合）、hash_map（散列映射表）、hash_multiset（散列多键集合）、hash_multimap（散列多键映射表）
• 底层实现：
  • 关联式容器的内部结构是一个balanced binary tree（平衡二叉树），以便获得良好的搜索效率。balanced binary tree有许多种类，包括AVL-tree、RB-tree、AA-tree，其中最被广泛应用于STL的是RB-tree（红黑树）
  • set、map、multiset、multimap底层均以RB-tree（红黑树）完成。RB-tree（红黑树）也是一个独立容器，但并不开放给外界使用
• 详细介绍：
  • set：
  • map：
  • multiset：
  • multimap：
  • hashtable：
  • hash_set：
  • hash_map：
  • hash_multiset：
  • hash_multimap：