1.vector
(1). 支持的迭代器类别
为random_access_iterator_tag
(2). 内存组织
逻辑上连续的元素,线性地址空间内也连续。
(3). 内存扩张和收缩
a. 初始化时会默认分配一块可容纳指定数量的线性地址空间。
b. 执行reserve(n)
,在现有地址空间不足容纳n
个元素时,会分配新空间以便可容纳n
个元素。老空间会释放,老元素会转移。
c. 执行shrink_to_fit()
会在size()<capcity()
时,分配新空间恰好可容纳size()
个元素。老空间会释放,老元素会转移。
d. 执行insert
在现有空间无法容纳新元素时,触发容纳扩展。
(4). 线程安全
不提供线程安全保护。
2.list
(1). 支持的迭代器类别
为bidirectional_iterator_tag
(2). 内存组织
逻辑上连续的节点,线性地址空间不连续。
(3). 内存扩展和收缩
a. 每次插入新节点,需为其分配线性空间,再插入。
b. 每次移除节点,需释放其线性空间。
(4). 线程安全
不提供线程安全保护。
3.stack
(1). 支持的迭代器类别
不支持迭代器
(2). 内存组织
stack
是对逻辑操作施加限制的容器,即插入,删除只能在栈顶进行。
可以基于数组实现,也可基于链表实现。
(3). 线程安全
不提供线程安全保护。
4.deque
(1). 支持的迭代器类别
原则上可以不支持迭代器。
(2). 内存组织
deque
是对逻辑操作施加限制的容器,即插入必须在尾部,删除只能在头部。
可以基于数组实现,也可基于链表实现。
(3). 线程安全
不提供线程安全保护。
5.map,set,mulmap,mulset
map
和set
都是基于平衡二叉树实现的容器。
map
支持pair
形式的元素插入。set插入时直接是key。
mul
版本和非mul
版本的区别在于是否允许插入时,同一个key
被插入多次。
(1). 支持的迭代器类别
为bidirectional_iterator_tag
(2). 内存组织
有序二叉树组织。
(3). 线程安全
不提供线程安全保护。
6.unordered_map,unordered_set,mulunordered_map,mulunordered_set
基于链式哈希表实现的容器。
map
支持pair
形式的元素插入。set
插入时直接是key
。
mul
版本和非mul
版本的区别在于是否允许插入时,同一个key
被插入多次。
(1). 支持的迭代器类别
为forward_iterator_tag
(2). 内存组织
链式哈希表,一般采用数组作为槽结构。以便采用链表来组织同一个槽下各个元素。
(3). 线程安全
不提供线程安全保护。