STL 容器
C++ 标准模板库 (STL) 提供了一组丰富的通用类和函数，它们实现了常见的数据结构和算法。容器是存储数据的对象。它们是模板类，这意味着它们可以容纳任何数据类型的元素。理解 STL 容器对于高效且稳健的 C++ 编程至关重要，它提供了 JavaScript 内置数组和对象类型的一个强大替代方案。
序列容器：vector、list、deque
序列容器以线性方式存储元素，允许通过其位置访问元素。
std::vector
- 动态数组： 类似于 JavaScript 数组，
std::vector是一个动态数组，其大小可以增长或缩小。 - 连续内存： 元素存储在连续的内存位置，允许高效的随机访问 (O(1))。
- 高效的尾部插入/删除： 在尾部添加/移除元素是高效的 (摊销 O(1))。
- 低效的中间插入/删除： 在中间插入/删除需要移动元素 (O(n))。
正在加载...
std::list
- 双向链表： 元素不连续存储。每个元素存储指向前一个和后一个元素的指针。
- 高效的任意位置插入/删除： 在列表中的任何位置添加/移除元素是高效的 (O(1))，一旦找到位置。
- 低效的随机访问： 通过索引访问元素需要遍历列表 (O(n))。
std::deque (双端队列)
- 块的动态数组： 将元素存储在非连续的内存块中。
- 高效的头部/尾部插入/删除： 在两端添加/移除元素是高效的 (摊销 O(1))。
- 高效的随机访问： 支持随机访问 (O(1))，尽管比
std::vector稍慢。
关联容器：map、set、unordered_map
关联容器以排序或哈希方式存储元素，允许根据键高效地查找。
std::map
- 排序的键值对： 以键值对的形式存储元素，按键排序。
- 唯一键： 每个键必须是唯一的。
- 对数时间复杂度： 查找、插入和删除操作通常是 O(log n)，因为其底层是树状结构（通常是红黑树）。
正在加载...
std::set
- 排序的唯一元素： 以排序顺序存储唯一元素。
- 对数时间复杂度： 查找、插入和删除是 O(log n)。
std::unordered_map
- 哈希的键值对： 使用哈希表存储键值对。
- 唯一键： 每个键必须是唯一的。
- 平均常数时间复杂度： 查找、插入和删除通常平均为 O(1)，但在最坏情况下（哈希冲突）可能退化为 O(n)。
std::unordered_set
- 哈希的唯一元素： 使用哈希表存储唯一元素。
- 平均常数时间复杂度： 查找、插入和删除通常平均为 O(1)。
容器适配器：stack、queue、priority_queue
容器适配器为底层容器提供受限接口，强制执行特定的数据访问模式。
std::stack
- LIFO (后进先出)： 元素从顶部添加和移除。
- 操作：
push、pop、top、empty、size。
std::queue
- FIFO (先进先出)： 元素添加到尾部，从头部移除。
- 操作：
push、pop、front、back、empty、size。
std::priority_queue
- 最高优先级优先： 元素根据其优先级（默认为最大元素）检索。
- 操作：
push、pop、top、empty、size。
迭代器概念和用法
迭代器是行为类似指针的对象，允许你遍历容器的元素。它们提供了一种通用的方式来访问元素，无论容器类型如何。
begin()：返回指向第一个元素的迭代器。end()：返回指向最后一个元素之后的元素的迭代器（一个哨兵）。*iterator：解引用迭代器以获取元素的值。++iterator：将迭代器移动到下一个元素。
正在加载...
容器性能特性分析
选择正确的容器对于性能至关重要。以下是常见操作的典型时间复杂度摘要：
| 容器 | 访问 (随机) | 插入 (任意位置) | 删除 (任意位置) | 搜索 (按值) |
|---|---|---|---|---|
std::vector | O(1) | O(n) | O(n) | O(n) |
std::list | O(n) | O(1) | O(1) | O(n) |
std::deque | O(1) | O(n) (中间), O(1) (两端) | O(n) (中间), O(1) (两端) | O(n) |
std::map | N/A | O(log n) | O(log n) | O(log n) |
std::set | N/A | O(log n) | O(log n) | O(log n) |
std::unordered_map | N/A | O(1) (平均), O(n) (最坏) | O(1) (平均), O(n) (最坏) | O(1) (平均), O(n) (最坏) |
std::unordered_set | N/A | O(1) (平均), O(n) (最坏) | O(1) (平均), O(n) (最坏) | O(1) (平均), O(n) (最坏) |
与 JavaScript 数组/对象的比较
JavaScript 的 Array 和 Object 类型功能非常强大，但它们抽象了底层的内存管理和特定的数据结构。C++ STL 容器提供了明确的选择，允许开发人员为其特定需求选择最高效的数据结构。
- JavaScript
Array： 对于数值索引，其行为有点像std::vector，但也可以作为字符串键的哈希映射。它是一个单一、灵活的数据结构。 - JavaScript
Object： 主要是一个哈希映射（键值存储），功能类似std::unordered_map或std::map，但没有 C++ 容器明确的性能保证或类型安全。
容器选择指南
std::vector： 序列的默认选择。当你需要快速随机访问和高效的尾部添加/删除时使用。避免频繁地在中间插入/删除。std::list： 当你需要频繁地在序列中的任何位置插入/删除，并且随机访问不是主要考虑时使用。std::deque： 当你需要高效地在两端插入/删除，并且也需要快速随机访问时使用。std::map/std::set： 当你需要排序的键值对 (map) 或唯一的排序元素 (set) 以及操作的对数时间复杂度时使用。当顺序很重要时很有用。std::unordered_map/std::unordered_set： 当你需要平均情况下 O(1) 的快速查找、插入和删除，并且元素顺序不重要时使用。哈希表类行为的理想选择。std::stack/std::queue/std::priority_queue： 当你需要特定的 LIFO、FIFO 或基于优先级的访问模式时分别使用。
练习题：
- 描述
std::vector和std::list在其底层数据结构以及插入/删除和随机访问的性能特性方面的主要差异。 - 何时会选择
std::map而不是std::unordered_map，反之亦然？解释其权衡。 - 迭代器如何简化 C++ 中不同 STL 容器的使用？提供一个使用迭代器遍历
std::vector和std::list的简单示例。
项目构想：
- 使用
std::map实现一个简单的联系人管理系统，其中键是联系人的姓名（字符串），值是包含其电话号码和电子邮件的结构/类。允许用户添加、删除、搜索和显示联系人。然后，尝试使用std::vector的结构实现相同的系统，并比较搜索操作的复杂性。