[#regular] = 常规容器 :idprefix: regular_ Boost.Unordered 的闭寻址容器（ `boost::unordered++_++set` 、 `boost::unordered++_++map` 、 `boost::unordered++_++multiset` 与 `boost::unordered++_++multimap` ）完全符合 C{plus}{plus} 无序关联容器的标准规范。因此，对于熟悉 `std::unordered++_++set` 、 `std::unordered++_++map` 等用法的用户，可直接将其替换为Boost.Unordered 中的同名容器。开放寻址容器（ `boost::unordered++_++node++_++set` 、 `boost::unordered++_++node++_++map` 、 `boost::unordered++_++flat++_++set` 和 `boost::unordered++_++flat++_++map` ）的接口与之高度相似，但存在一些细微差异，详见专门的 xref:compliance.adoc#compliance_open_addressing_containers[标准符合性章节] 。 对于没有哈希容器经验但熟悉常规关联容器（ `std::set` 、 `std::map` 、 `std::multiset` 和 `std::multimap` ）的读者，Boost.Unordered 容器的使用方式与之类似： 但由于元素不按顺序存储，以下代码的输出结果： 可能以任意顺序输出。例如，结果可能为： 其他差异列于 xref:regular.adoc#comparison[与关联容器的对比] 章节中。 迭代器失效 标准未明确规定除 `rehash` 和 `reserve` 之外的成员函数如何影响桶数量，但 `insert` 操作仅当导致容器负载超过最大允许值时才会使迭代器失效。在大多数实现中，这意味着 `insert` 仅在此种情况下才会改变桶的数量。迭代器可能因调用 `insert` 、 `rehash` 或 `reserve` 而失效。 对于基于节点的容器（ `boost::unordered++_[++multi++]++set` 、 `boost::unordered++_[++multi++]++map` 、 `boost::unordered++_++node++_++set` 、 `boost::unordered++_++node++_++map` ），其指针和引用永远不会失效。但对于 `boost::unordered++_++flat++_++set` 和 `boost::unordered++_++flat++_++map` ，在发生重哈希时指针和引用将会失效：这是因为这些容器将元素直接存储在桶中，当分配新的桶数组时，必须通过移动构造来转移元素。 与为 `vector` 使用 `reserve` 类似，在插入大量元素之前调用 `reserve` 是一个好主意。这样可以避免代价高昂的重哈希操作，并且让你能够存储迭代器，确信它们不会被失效。如果你要向容器 `x` 插入 `n` 个元素，可以先调用： ``` x.reserve(n); ``` `reserve(n)` 为至少 `n` 个元素预留空间，分配足够数量的桶， 以确保不超过最大负载因子。由于最大负载因子定义为元素数量除以可用桶的总数，该函数在逻辑上等价于：\n```cppx.rehash(std::ceil(n / x.max_load_factor()))```\n有关 `rehash` 函数的更多详细信息，请参阅 xref:reference/unordered_map.adoc#unordered_map_rehash[参考文档]。 :idprefix: comparison_ 与关联容器的对比 关联容器 无序关联容器 通过排序关系 `Compare` 进行 参数化 由函数对象`哈希对象`和等价关系`谓词对象`参数化。 键可通过成员函数`key_comp()`获取的`键比较对象`进行比较，值可通过成员函数`value_comp()`获取的`值比较对象`进行比较。 键可通过成员函数`hash_function()`获取的`哈希对象`进行哈希计算，并通过成员函数`key_eq()`获取的`键相等比较对象`检查是否相等。不存在用于值比较或值哈希的函数对象。 构造函数包含用于比较对象的可选额外参数。 构造函数包含可选的额外参数，用于指定初始最小哈希桶数量、哈希函数以及相等性判断对象。 若`!对象(k1, k2) && !对象(k2, k1)`，则键`k1`、`k2`视为等价。 若`谓词对象(k1, k2)成立`，则键`k1`、`k2`视为等价。 成员函数`lower_bound(k)`和`upper_bound(k)` 无对应接口。由于元素无序，`lower_bound `和 `upper_bound `无实际意义。 若键k不存在于容器中，equal_range(k)会在k 应插入的位置返回一个空区间。 equal_range(k) 若键k不存在于容器中，则返回容器末尾的区间。该函数无法返回定位区间，因为k可被插入到多个位置。 闭散列容器：使用 bucket (k) 可确定键 k 待插入的哈希桶。需注意，插入操作可能触发容器重新哈希，元素最终会被存入其他哈希桶。 `迭代器`、`常迭代器`的迭代类别为双向迭代器。 `迭代器`、`常迭代器`的迭代类别至少为前向迭代器。 指向容器元素的迭代器、指针和引用永远不会失效。 xref:regular.adoc#regular_iterator_invalidation [调用 insert 或 rehash 可能会导致迭代器失效]。 基于节点的容器：指向容器元素的指针和引用永远不会失效。\n扁平容器：发生重新哈希时，指向容器元素的指针和引用将会失效。 迭代器按照比较对象定义的顺序遍历容器。 迭代器以任意顺序遍历容器，该顺序会随元素插入发生变化，但等价元素始终保持相邻。 无对应接口 闭散列容器：本地迭代器可用于遍历各个哈希桶。（本地迭代器与迭代器的顺序无需存在对应关系。） 可使用`==`, `!=`, `<`, `\\<=`, `>`, `>=`运算符进行比较。 可使用`==` 和`!=`运算符进行比较。 使用提示迭代器插入元素时，实现允许忽略该提示。 --- 操作 关联容器 无序关联容器 空容器的构造 常数级 O(_n_)，其中 _n_ 是最小桶数。 由_N_元素的区间构造容器 O(_N log N_)，如果区间已按 `value_comp()` 排序则为 O(_N_) "平均时间复杂度 O(_N_)，最坏时间复杂度 O(_N^2^_)" 插入单个元素 对数级 平均情况为常数时间，最坏情况为线性时间 带提示插入单个元素 若在提示位置后直接插入t个元素，则为均摊常数时间；否则为对数时间 平均情况为常数时间，最坏情况为线性时间（即与普通插入操作一致）。 插入_N_元素的区间 _N_ log(`size()` + _N_) 平均时间复杂度 O(_N_)，最坏时间复杂度O (_N_ * `size()`) 按键`k`移除 O(log(`size()`) + `count(k)`) 平均情况：O(`count(k)`)，最坏情况：O(`size()`) 通过迭代器移除单个元素 均摊常数时间 平均情况：O (1)，最坏情况：O(`size()`) 移除 _N_元素的区间 O(log(`size()`) + _N_) 平均情况：O(_N_)，最坏情况： O(`size()`) 清空容器 O(`size()`) 查找 计数 `equal_range(k)` `lower_bound`,`upper_bound` n/a