C++ 容器与迭代器

应根据所需的查找、遍历、插入、擦除、内存局部性和引用稳定性来选择容器。复杂度描述操作在满足前置条件时的性质；失效规则和所有权则决定设计在修改后是否仍然正确。

选择容器 #

• std::vector 是需要连续存储、随机访问、缓存局部性以及通过 data() 与 C 互操作时的默认序列容器。追加操作具有摊销常数时间复杂度。容量的任何增长都会使所有迭代器、指针和引用失效；如果容量不增长，插入操作会使插入点及其后的迭代器和引用失效。
• std::deque 支持索引访问。在两端插入会使迭代器失效，但不会使引用失效；其存储并不连续，在中间插入会使迭代器和引用失效。
• std::list 和 std::forward_list 在插入和擦除时，会保留指向未受影响节点的迭代器和引用。节点分配和指针追踪带来的成本意味着应根据测量结果选择它们，而不是将它们作为默认选项。
• std::map 和 std::set 提供有序遍历和对数时间查找。除被擦除的元素外，插入不会使迭代器或引用失效。
• std::unordered_map 和 std::unordered_set 提供平均常数时间查找。重新哈希会使迭代器失效，但指向元素的引用和指针仍然有效；擦除只会使被擦除的元素失效。

reserve() 可避免预期中的 vector 重新分配，也可以减少 unordered_* 的重新哈希。对于根据文档规则会使迭代器失效的操作，它并不能让该迭代器保持有效。

插入与转移值 #

insert 接受元素或范围，而 emplace 根据参数直接在容器存储空间中构造元素：

#include <string>
#include <utility>
#include <vector>

std::vector<std::string> names;
std::string name = "Ada";

names.push_back(name);            // copies; name remains owned by the caller
names.push_back(std::move(name)); // moves; name stays valid but has unspecified value
names.emplace_back(3, 'x');       // constructs "xxx" in the vector

当对象已经存在时，使用 insert 或 push_back(std::move(value)) 可以明确显示所有权转移。只有在构造函数参数可用时，emplace 才能避免创建临时对象；它既不会在所有情况下都更快，也不能代替对元素构造函数的验证。当键已存在时，关联容器的 emplace 可能构造后再丢弃一个元素。try_emplace 可在这种键重复的情况下避免构造映射值，而 insert_or_assign 则明确表达替换策略。

对于基于节点的容器，extract 会生成节点句柄；该句柄拥有被移除的节点，直至节点被插入或销毁。它可以在不移动所含值的情况下转移兼容节点，但仍须满足分配器兼容性要求和容器文档所规定的前置条件。

迭代器与前置条件 #

算法会声明其所需的迭代器类别。输入迭代器只支持单趟遍历；前向迭代器支持多趟遍历；双向迭代器增加递减操作；随机访问迭代器增加算术和排序操作；连续迭代器还表示相邻存储。应传入算法所要求类别的迭代器，而不能假设来自一个容器的迭代器与另一个容器的迭代器行为相同。

调用算法或容器成员之前，应验证范围的前置条件：

auto first = values.begin();
auto last = values.end();
if (first != last) {
    values.erase(first); // `first` is valid and dereferenceable
}

end() 是哨兵，而不是元素。绝不能解引用它，也不能比较来自不同容器的迭代器，除非 API 明确允许。在修改期间保留迭代器之前，应阅读具体容器的失效规则表；基于范围的 for 循环和标准算法可以减少手动处理迭代器，但不会让这些规则暂停生效。