C++ STL容器相关操作的复杂度分析

序列容器

​vector:

• •

  随机访问: O(1)

• •

  尾部插入/删除: O(1) (均摊)

• •

  中间插入/删除: O(n)

• •

  查找: O(n)

​deque:

• •

  随机访问: O(1)

• •

  头尾插入/删除: O(1)

• •

  中间插入/删除: O(n)

• •

  查找: O(n)

​list/forward_list:

• •

  任意位置插入/删除: O(1)

• •

  随机访问: O(n)

• •

  查找: O(n)

关联容器

​set/multiset (红黑树实现)​:

• •

  插入/删除/查找: O(log n)

• •

  最小值/最大值: O(1)

​map/multimap (红黑树实现)​:

• •

  插入/删除/查找: O(log n)

​unordered_set/unordered_map (哈希表实现)​:

• •

  平均插入/删除/查找: O(1)

• •

  最坏情况: O(n)

容器适配器

​stack/queue:

• •

  所有操作: O(1) (基于底层容器)

​priority_queue:

• •

  插入: O(log n)

• •

  删除顶部: O(log n)

• •

  访问顶部: O(1)

均摊复杂度考虑了动态扩容的情况。