【STL】容器概观与分类

容器，置物之所也。

当然我是不喜欢这句话的…容器嘛，数据结构…存放数据的结构体…

常用的数据结构有如下几种类型：

array——数组

list——链表

tree——树

stack——栈

queue——队列

hash_table——散列表

set——集合

map——映射

等等…

这里是 SGI STL 的各种容器，本图以内缩进方式来表达基层与衍生层的关系

 

这里的衍生并非派生关系，而是内含关系。

例如：heap内含一个vector，priority_queue 内含一个heap

stack 和  queue 都内含一个 deque （其实也可以用list 和 vector来生成）

set map等等都内含 RBTree（红黑树）

hash_set … hash_map 都内含 hashtable(散列表)

 

序列式容器：

C++语言本身提供 array(数组)

STL 提供了 vector list deque stack queue priority_queue 等等。

这里会讨论以下容器的实现：

vector

list

deque

stack

queue

heap

priority_queue

slist

其中stack 和 queue 是一种配接器（适配器 adapter）。

 

关联式容器：

可以分为 set(集合) 和 map(映射表) 两大类。

它们的内部实现 多是 RBTree 或者 HashTable

所以会讨论以下知识点；

二叉搜索树

平衡二叉搜索树

AVLTree

单旋转 和 双旋转

RB-Tree

set

map

multiset

multimap

hashtable

hash_set

hash_map

hash_multiset

hash_multimap