队列性容器 vector list deque
vector 线性顺序, 大小自动扩展. 创建vector后, 会自动在内存中分配一个连续的内存空间, 因此支持 [] 操作, 随机存取. 但是在增减时会造成内存拷贝, 效率较低, 所以vector仅设计成后端进行push/pop操作. vecotor一般在创建时就指定其空间大小.
list为双向链表, 内存空间可以不连续, 通过指针进行数据访问, 所以他的随机访问没有效率, 没有[]操作. 但是他支持任意位置上的增删.
deque是优化的对序列两端元素进行push/pop操作的容器, 支持比较快速的[]随机访问 (采用的是多个连续的存储块). 效率介于 list / vector 之间.
关联容器 set/multiset map/multimap. 默认升序排序
都是非线性的数结构(平衡检索二叉树--红黑树)
set元素是唯一的, 按照顺序培训的. multiset 不要求唯一.
map元素为kv键值对关系, 键不可重复且排序. multimap的键在容器中可以不唯一.
map/set 插入删除比vector快(因为vector是顺序存储, map/set是链式存储), 比list慢(因为list为线性的, map/set为二叉树). 而且map/set是排序的,插/删操作需要重新排序动作.
map/set的检索(检索复杂度Log(N))比vector慢, 比list((检索复杂度为容量大小)快(因为list需要逐个顺序检索).
