C++ STL 容器介绍#

C++ 标准模板库（STL）是 C++ 语言的基石之一，它提供了一套性能卓越、经过严格测试的通用算法和数据结构。其中，容器是 STL 最核心的部分，它们是用于管理和存储对象集合的类模板。正确地选择容器，不仅能让代码更简洁、更安全，还能显著提升程序的性能。

本文将全面介绍 C++ 中常见的各类容器，分析它们的内部实现、优缺点以及最佳适用场景，帮助你今后在项目开发中做出明智的选择。

C++ 容器主要可以分为三类：顺序容器、关联容器和无序关联容器。

#顺序容器 (Sequence Containers)

顺序容器中的元素按照严格的线性顺序排列。你可以精确地控制每个元素的位置。

#std::vector

• 特点：动态数组。所有元素在内存中连续存储。
• 优点：
  • 访问最快：通过索引 [] 或 .at() 进行随机访问的时间复杂度为 O(1)，并且由于内存连续，能很好地利用 CPU 缓存。
  • 尾部操作高效：在尾部添加/删除元素（.push_back(), .pop_back()）的平均时间复杂度为 O(1)。
• 缺点：
  • 中间插入/删除慢：在容器开头或中间插入/删除元素的时间复杂度为 O(n)，因为它需要移动之后的所有元素。
  • 可能触发重分配：当 vector 容量不足时，它会重新分配一块更大的内存，并将所有旧元素拷贝过去，这可能是一个耗时的操作。
• 适用场景：需要快速随机访问，且主要在尾部进行添加/删除操作的场景。这是最常用、最应该被首选的容器。

#std::deque (Double-Ended Queue)

• 特点：双端队列。其内部实现并非一整块连续内存，而是由多个连续的内存块（chunks）链接而成。
• 优点：
  • 两端操作高效：支持在头部和尾部快速添加/删除元素，时间复杂度均为 O(1)。
  • 支持随机访问：虽然其随机访问性能略逊于 vector（需要两次指针解引用），但时间复杂度仍为 O(1)。
• 缺点：
  • 中间插入/删除慢：与 vector 类似，中间操作的时间复杂度为 O(n)。
  • 内存不连续：缓存命中率低于 vector，遍历速度可能稍慢。
• 适用场景：需要频繁地在容器的两端进行插入和删除操作的场景，例如实现一个既能先进先出又能后进先出的队列。

#std::list

• 特点：双向链表。每个元素都存储着指向前一个和后一个元素的指针。
• 优点：在任何位置插入/删除元素都非常快（O(1)），前提是你已经拥有指向该位置的迭代器。
• 缺点：
  • 不支持随机访问：无法通过索引（如 list[i]）访问元素。要访问第 n 个元素，必须从头或尾开始遍历 n 次，时间复杂度为 O(n)。
  • 内存开销大：每个元素都需要额外的空间来存储前后指针。
• 适用场景：需要对集合进行大量、不规律的插入和删除操作，而对随机访问没有要求的场景。

#std::array (C++11)

• 特点：固定大小的数组，是对 C 风格数组的现代封装。大小在编译时确定，不可改变。
• 优点：性能与 C 风格数组完全相同，但提供了更安全、更方便的接口（如获取大小、迭代器支持、边界检查等）。
• 缺点：大小固定，缺乏灵活性。
• 适用场景：当你明确知道需要一个在编译期就确定大小的数组时。

#关联容器 (Associative Containers)

关联容器根据键 (key) 来高效地排序和存储元素。它们非常适合用于快速查找。

#std::map

• 特点：存储键-值对 (key-value pairs)，其中键是唯一的。内部通常由红黑树实现，元素自动按键的升序排序。
• 优点：可以根据键快速查找、插入和删除元素，平均时间复杂度为 O(log n)。
• 适用场景：需要存储键值对，并且要求元素能自动排序的场景。

#std::set

• 特点：只存储唯一的键。和 map 一样，内部也是由红黑树实现，元素自动排序。
• 优点：快速查找、插入和删除（O(log n)）。常用于检查一个元素是否存在于一个集合中。
• 适用场景：需要存储不重复的元素，并要求它们保持有序。

std::multimap 和 std::multiset 分别是 map 和 set 的多键版本，它们允许存储重复的键。

#无序关联容器 (Unordered Associative Containers)

这类容器在 C++11 中引入，它们也存储键或键值对，但基于哈希表 (Hash Table) 实现，不保证元素有序，换来的是更快的平均性能。

#std::unordered_map

• 特点：存储键-值对，键是唯一的。通过哈希函数将键映射到桶 (bucket) 中以实现快速访问。
• 优点：提供了最快的平均查找、插入和删除速度，平均时间复杂度为 O(1)。
• 缺点：
  • 元素是无序的。
  • 在最坏情况下（所有元素哈希到同一个桶中），性能会退化到 O(n)。
  • 需要为哈希表本身和键的哈希值消耗额外内存。
• 适用场景：追求极致查找性能，且不关心元素顺序的场景。这是 std::map 的常用高性能替代品。

#std::unordered_set

• 特点：只存储唯一的键，基于哈希表实现。
• 优点：最快的平均查找、插入和删除速度（O(1)）。
• 适用场景：需要以最高性能判断一个元素是否存在于集合中，且不关心顺序。

#总结与选择建议

为了方便选择，下表总结了各类容器的特点：

需求	推荐容器	备选方案	时间复杂度 (平均)
快速随机访问	std::vector	std::deque, std::array	O(1)
大量中间插入/删除	std::list	std::forward_list	O(1)
快速两端插入/删除	std::deque	std::list	O(1)
键值对存储 (有序)	std::map	std::multimap	O(log n)
键值对存储 (最快查找)	std::unordered_map	std::unordered_multimap	O(1)
存储唯一元素 (有序)	std::set	std::multiset	O(log n)
存储唯一元素 (最快查找)	std::unordered_set	std::unordered_multiset	O(1)

通用建议：

1. 如果不确定用什么，std::vector 通常是最好的第一选择。它的性能优秀且用途广泛。
2. 如果需要按键查找，并且不要求排序，std::unordered_map 是 std::map 的高性能替代品。
3. 只有在需要频繁在容器中间进行插入/删除时，才考虑使用 std::list。