C++ STL 容器

C++ 的 STL（Standard Template Library） 提供了多种容器，分为以下几类：

1. 序列容器（Sequence Containers）
2. 关联容器（Associative Containers）
3. 无序关联容器（Unordered Associative Containers）
4. 容器适配器（Container Adapters）

以下是常见 STL 容器的分类、内部实现和时间复杂度：

---

1. 序列容器（Sequence Containers）

序列容器按顺序存储元素，允许在任意位置插入和删除。

（1）std::vector

• 内部实现：动态数组。
• 特点：
  • 内存连续，支持随机访问。
  • 尾部插入和删除效率高，中间插入和删除效率低。
• 时间复杂度：
  • 访问元素：O(1)
  • 尾部插入/删除：O(1)（均摊）
  • 中间插入/删除：O(n)

（2）std::deque

• 内部实现：分段连续空间（双端队列）。
• 特点：
  • 支持高效的头尾插入和删除。
  • 内存非完全连续，但支持随机访问。
• 时间复杂度：
  • 访问元素：O(1)
  • 头尾插入/删除：O(1)
  • 中间插入/删除：O(n)

（3）std::list

• 内部实现：双向链表。
• 特点：
  • 支持高效的元素插入和删除。
  • 不支持随机访问。
• 时间复杂度：
  • 插入/删除元素：O(1)（已知位置）
  • 访问元素：O(n)

（4）std::forward_list

• 内部实现：单向链表。
• 特点：
  • 比 std::list 更节省内存。
  • 只支持单向遍历。
• 时间复杂度：
  • 插入/删除元素：O(1)（已知位置）
  • 访问元素：O(n)

---

2. 关联容器（Associative Containers）

关联容器按键（key）排序，支持高效查找。

（1）std::set

• 内部实现：红黑树（平衡二叉搜索树）。
• 特点：
  • 元素唯一，按值排序。
• 时间复杂度：
  • 插入/删除/查找：O(log n)

（2）std::multiset

• 内部实现：红黑树。
• 特点：
  • 允许重复元素，按值排序。
• 时间复杂度：
  • 插入/删除/查找：O(log n)

（3）std::map

• 内部实现：红黑树。
• 特点：
  • 键值对存储，按键排序。
• 时间复杂度：
  • 插入/删除/查找：O(log n)

（4）std::multimap

• 内部实现：红黑树。
• 特点：
  • 允许重复键，按键排序。
• 时间复杂度：
  • 插入/删除/查找：O(log n)

---

3. 无序关联容器（Unordered Associative Containers）

无序关联容器使用哈希表实现，支持高效查找。

（1）std::unordered_set

• 内部实现：哈希表。
• 特点：
  • 元素唯一，无序存储。
• 时间复杂度：
  • 插入/删除/查找：平均 O(1)，最坏 O(n)

（2）std::unordered_multiset

• 内部实现：哈希表。
• 特点：
  • 允许重复元素，无序存储。
• 时间复杂度：
  • 插入/删除/查找：平均 O(1)，最坏 O(n)

（3）std::unordered_map

• 内部实现：哈希表。
• 特点：
  • 键值对存储，无序存储。
• 时间复杂度：
  • 插入/删除/查找：平均 O(1)，最坏 O(n)

（4）std::unordered_multimap

• 内部实现：哈希表。
• 特点：
  • 允许重复键，无序存储。
• 时间复杂度：
  • 插入/删除/查找：平均 O(1)，最坏 O(n)

---

4. 容器适配器（Container Adapters）

容器适配器基于其他容器实现，提供特定接口。

（1）std::stack

• 内部实现：默认基于 std::deque。
• 特点：
  • 后进先出（LIFO）。
• 时间复杂度：
  • 插入/删除：O(1)
  • 访问栈顶元素：O(1)

（2）std::queue

• 内部实现：默认基于 std::deque。
• 特点：
  • 先进先出（FIFO）。
• 时间复杂度：
  • 插入/删除：O(1)
  • 访问队首元素：O(1)

（3）std::priority_queue

• 内部实现：默认基于 std::vector，使用堆（heap）实现。
• 特点：
  • 元素按优先级排序，默认最大堆。
• 时间复杂度：
  • 插入：O(log n)
  • 删除：O(log n)
  • 访问堆顶元素：O(1)

---

总结

容器类型	容器名称	内部实现	访问	插入/删除	查找
序列容器	std::vector	动态数组	O(1)	O(n)/O(1)	-
	std::deque	分段连续空间	O(1)	O(n)/O(1)	-
	std::list	双向链表	O(n)	O(1)	-
	std::forward_list	单向链表	O(n)	O(1)	-
关联容器	std::set	红黑树	-	O(log n)	O(log n)
	std::multiset	红黑树	-	O(log n)	O(log n)
	std::map	红黑树	-	O(log n)	O(log n)
	std::multimap	红黑树	-	O(log n)	O(log n)
无序关联容器	std::unordered_set	哈希表	-	O(1)/O(n)	O(1)/O(n)
	std::unordered_multiset	哈希表	-	O(1)/O(n)	O(1)/O(n)
	std::unordered_map	哈希表	-	O(1)/O(n)	O(1)/O(n)
	std::unordered_multimap	哈希表	-	O(1)/O(n)	O(1)/O(n)
容器适配器	std::stack	默认 std::deque	O(1)	O(1)	-
	std::queue	默认 std::deque	O(1)	O(1)	-
	std::priority_queue	默认 std::vector	O(1)	O(log n)	-

根据需求选择合适的容器，可以显著提高程序性能。

以下为各种时间复杂度的趋势对比图，供参考。