STL

STL 容器底层实现总结

顺序容器、关联容器及容器适配器

ZingLix September 20, 2018

顺序容器

可顺序访问的数据结构。

容器 数据结构
vector 数组
deque 数个缓冲区相接,由一个中央控制器管理
list 双向链表

比较

  • 随机访问
    • vector:支持快速随机访问,一次指针解引用
    • deque:支持随机访问,两次指针解引用(中央控制器和缓冲区两次)
    • list:不支持随机访问
  • 内存管理:
    • vector:扩充时须将所有的元素拷贝到新位置
    • deque:按需扩充一个缓冲区大小,无需拷贝
    • list:为各节点单独分配内存
  • 增删元素:
    • vector:在尾部可快速增删,中间插入会导致之后的元素拷贝
    • deque:在头尾可快速增删,中间插入会导致元素拷贝
    • list:在任意位置都可快速增删

关联容器

可快速查找( \(O(logN)\) )的容器,且可按键排序。

容器 数据结构 集合内容 键是否唯一
set 红黑树
map 红黑树 键值对
multiset 红黑树
multimap 红黑树 键值对

关联容器底层数据结构均为红黑树,因为红黑树性能平均下来最好,也因此这四个容器行为类似,一般操作时间复杂度一般均为 \(O(logN)\),差别仅在于是键集合还是键值对集合,以及键是否可重复。

无序关联容器

从 C++11 开始提供的可快速查找(均摊 \(O(1)\),最坏 \(O(n)\) )的无序容器。

容器 数据结构 集合内容 键是否唯一
unordered_set 哈希表
unordered_map 哈希表 键值对
unordered_multiset 哈希表
unordered_multimap 哈希表 键值对

相对于关联容器,上层行为表现一致,底层数据结构更换为了哈希表获得了更好的均摊性能,但同时付出了不可按序访问的代价。

容器适配器

在其他容器的接口上进行封装和改写实现。

容器 默认底层容器 描述
stack deque 堆栈,后进先出(LIFO)
queue deque 队列,先进先出(FIFO)
priority_queue vector 优先队列

stack 和 queue 默认用 deque 实现为了让当数据量很大时,不会因元素移动导致过多的时间消耗。而 priority_queue 利用 vector 则是因为为了实现优先队列用到了 heap 相关的函数,其中用到了大量的随机访问。