• 非特殊说明函数 size empty 复杂度均为常数

顺序容器

顺序容器是提供能够按顺序访问元素功能的容器

vector

  • 内部实现: 连续内存
  • 常见操作复杂度:
    • 随机访问 O(1)O(1) // operator[] at
    • 在尾部增删元素 O(1)O(1) //push_back pop_back
    • 增删元素 O(n)O(n) //insert erase
  • vector 会在需要时自动调整所占内存的大小。与对应的静态数组相比,vector 所占的内存通常要更多,因为它还分配了额外的内存以应对将来可能的扩张。于是,vector 就不必在每次插入元素时都重新分配一次内存了,除非这块预留的内存用尽。

deque

  • 内部实现: 单独分配的固定大小数组(内存)的序列 (非连续存储)
  • 常见操作复杂度:
    • 随机访问 O(1)O(1) //operator[] at
    • 在结尾或开头插入或移除元素 O(1)O(1) //push_back pop_back push_front pop_front
    • 插入或移除元素 O(n)O(n) //insert erase

list

  • 内部实现: 双向链表

  • 常见操作复杂度:

    • 随机访问 不支持
    • 插入删除元素 若指定位置则为O(1)O(1),否则为O(n)O(n)
    • 排序 O(nlogn)O(nlogn)
  • size复杂度: C++11 前为线性或常数,后为常数

关联容器

关联容器通过使用已排序的数据结构,提供O(logn)O(log n)时间复杂度的快速搜索

set

  • 内部实现: 红黑树
  • 常见操作复杂度:
    • 随机访问 不支持
    • 查找元素 find O(logn)O(logn),count O(logn+count)O(logn + count)
    • 插入删除元素 一般为O(logn)O(logn)

map

  • 内部实现: 红黑树
  • 常见操作复杂度:
    • 随机访问 O(logn) //operator[] at
    • 查找元素 find O(logn)O(logn),count O(logn+count)O(logn + count)
    • 插入删除元素 一般为O(logn)O(logn)

无序关联容器

无序关联容器是提供基于哈希(Hash)表进行平均O(1)O(1)时间复杂度,最坏O(n)O(n)时间复杂度搜索功能的容器

unordered_set

  • 内部实现: 哈希表
  • 常见操作复杂度: 搜索,插入,删除均摊O(1)O(1),最坏O(n)O(n)

unordered_map

  • 内部实现: 哈希表
  • 常见操作复杂度: 搜索,插入,删除均摊O(1)O(1),最坏O(n)O(n)

容器适配器

容器适配器提供顺序容器的特殊接口

stack

  • 内部实现: 接口自deque

queue

  • 内部实现: 接口自deque

priority_queue

  • 内部实现: 接口自vector,使用堆实现
  • 常见操作复杂度:
    • 插入删除(只支持在头尾) O(logn)O(logn) //push pop
    • top O(1)O(1)

参考: