非标准容器 - 1.88.0 - Boost C++ 函数库

这个有用的、完全符合 STL 标准的稳定容器由 Joaquín M. López Muñoz 设计，是 vector 和 list 的混合体，提供了 vector 的大部分特性，除了元素连续性。

尽管 vector 非常方便，但它有一个限制，许多 C++ 新手程序员经常会遇到：当删除前面的元素或当向量扩展并需要将其内部存储迁移到更宽的内存区域时（即，当所需大小超过向量的容量时），指向 vector 元素的迭代器和引用会失效。我们说 vector 是不稳定的：相比之下，稳定容器是指那些只要元素不被删除，指向给定元素的引用和迭代器就仍然有效的容器：C++ 标准库中稳定容器的例子有 list 和标准关联容器（set、map 等）。

有时，稳定性是一个太珍贵的特性而不能没有，但是 vector 的一个特殊属性，元素连续性，使得为这个容器增加稳定性变得不可能。因此，如果我们牺牲元素连续性，一个稳定的设计能在多大程度上接近 vector 的行为（随机访问迭代器，摊销常数时间末尾插入/删除，最小内存开销等）？下图描述了一个可能的数据结构布局，可以作为稳定向量设计的基础

每个元素都存储在自己的单独节点中。所有节点都从一个连续的指针数组中引用，但每个节点也包含一个“向上”指针，指回相关的数组单元。这个向上指针是实现稳定性和随机可访问性的关键元素

迭代器指向节点而不是指针数组。这确保了稳定性，因为只有指针数组需要在插入或删除时进行移位或重新定位。随机访问操作可以通过使用指针数组作为方便的中间区域来实现。例如，如果迭代器 it 持有一个节点指针 it.p，我们想将其向前移动 n 个位置，我们只需执行

it.p = *(it.p->up+n);

也就是说，我们“向上”到指针数组，在那里加上 n，然后“向下”到结果节点。

通用属性。 stable_vector 满足容器、可逆容器和序列的所有要求，并提供向量中存在的所有可选操作。与向量一样，迭代器是随机访问的。stable_vector 不提供元素连续性；为了换取这种缺失，容器是稳定的，即，只要元素不被删除，对 stable_vector 元素的引用和迭代器就仍然有效，并且已被赋予 end() 返回值的迭代器始终有效，直到关联的 stable_vector 被销毁。

操作复杂度。 stable_vector 操作的大 O 复杂度与向量完全匹配。一般来说，在序列末尾插入/删除是常数时间，而在其他地方是线性时间。与向量不同，stable_vector 在内部不执行任何 value_type 析构、复制/移动构造/赋值操作，除了那些与插入新元素或删除存储元素完全对应的操作，这有时可以在性能方面补偿更多指针操作和每个元素额外分配的负担。

异常安全性。（根据 Abrahams 的术语）由于 stable_vector 在内部不复制/移动元素，因此某些操作比向量提供更强的异常安全保证

表 7.1. 异常安全性

操作	`vector<T>` 的异常安全性	`stable_vector<T>` 的异常安全性
插入	强保证，除非 `T` 的复制/移动构造/赋值抛出异常（基本保证）	强保证
删除	不抛出异常，除非 `T` 的复制/移动构造/赋值抛出异常（基本保证）	不抛出异常

内存开销。 C++ 标准没有规定内存消耗的要求，但实际上任何 vector 的实现都具有相同的内存使用行为：由具有 n 个 T 类型元素的 vector v 分配的内存是

m_v = c∙e,

其中 c 是 v.capacity()，e 是 sizeof(T)。如果用户已显式保留了所需的精确容量，则 c 可以低至 n；否则，对于增长的 vector，c 的平均值在典型的大小调整策略下在 1.25∙n 和 1.5∙n 之间振荡。对于 stable_vector，内存使用量为

m_sv = (c + 1)p + (n + 1)(e + p),

其中 p 是指针的大小。我们有 c + 1 和 n + 1 而不是 c 和 n，因为序列末尾需要一个虚拟节点。如果我们称 f 为容量与大小的比率 c/n，并假设 n 足够大，我们有

m_sv/m_v ≃ (fp + e + p)/fe.

因此，只有当 e > p 且容量与大小的比率超过给定阈值时，stable_vector 使用的内存才比 vector 少

m_sv < m_v <-> f > (e + p)/(e - p). (如果 e > p)

当 e > 5p 时，此阈值接近典型的 f 值低于 1.5；在 32 位架构中，当 e > 20 字节时。

总结。 stable_vector 是 vector 的直接替代品，它提供了引用和迭代器的稳定性，以换取缺失的元素连续性以及一些性能和内存开销。当元素对象移动成本很高时，如果执行许多中间插入或删除，或者如果调整大小非常频繁，则性能开销可能会转化为 stable_vector 的净性能增益。同样，如果元素很大，则在某些情况下，stable_vector 使用的内存实际上可能少于向量所需的内存。

注意：文本和解释取自 Joaquín 的博客

flat_(multi)map/set 关联容器

在 C++ 世界中，使用排序向量代替基于树的关联容器是一种众所周知的技术。Matt Austern 的经典文章为什么你不应该使用 set，以及你应该使用什么代替 (C++ Report 12:4, 2000 年 4 月) 具有启发意义

“红黑树不是组织数据的唯一方法，它允许对数时间查找。计算机科学的基本算法之一是二分查找，它通过连续地将范围分成两半来工作。二分查找是 log N，它不需要任何花哨的数据结构，只需要一个排序的元素集合。(...) 你可以使用任何方便的数据结构，只要它提供 STL 迭代器；通常最容易使用 C 数组或向量。”

“std::lower_bound 和 set::find 都花费与 log N 成正比的时间，但比例常数非常不同。使用 g++ (...) 在包含一百万个元素的排序 vector<double> 中执行一百万次查找需要 X 秒，而使用 set 则几乎需要两倍的时间 (...)。此外，set 使用的内存 (4800 万字节) 几乎是 vector (1680 万字节) 的三倍。”

“使用排序向量代替 set 可以为您提供更快的查找和更快的迭代，但代价是插入速度较慢。使用 set::insert 插入到 set 中的时间与 log N 成正比，但插入到排序向量中 (...) 的时间与 N 成正比。每当您在向量中插入内容时，vector::insert 都必须通过移动其后的所有元素来腾出空间。平均而言，如果您同样有可能在任何地方插入一个新元素，您将移动 N/2 个元素。”

“有时将所有这些捆绑到一个小型容器适配器中可能很方便。这个类不满足标准关联容器的要求，因为插入的复杂度是 O(N) 而不是 O(log N)，但除此之外，它几乎是 set 的直接替代品。”

继 Matt Austern 的指示之后，Andrei Alexandrescu 的 Modern C++ Design 展示了 AssocVector，这是在他的 Loki 库中设计的 std::map 直接替代品

“似乎我们最好使用排序向量。排序向量的缺点是线性时间插入和线性时间删除 (...)。作为交换，向量提供大约两倍的查找速度和更小的工作集 (...)。Loki 通过定义 AssocVector 类模板来节省手动维护排序向量的麻烦。AssocVector 是 std::map 的直接替代品（它支持相同的成员函数集），在 std::vector 之上实现。AssocVector 与 map 的不同之处在于其擦除函数的行为（AssocVector::erase 使对象中的所有迭代器无效）以及插入和擦除的复杂度保证（线性而不是常数）。”

Boost.Container flat_[multi]map/set 容器是基于有序向量的关联容器，遵循 Austern 和 Alexandrescu 的指导原则。这些有序向量容器也受益于 C++11 中添加的 move semantics（移动语义），大大加快了插入和擦除时间。平面关联容器具有以下属性

比标准关联容器更快的查找速度
比标准关联容器快得多的迭代速度。随机访问迭代器而不是双向迭代器。
对于小型对象，内存消耗更少（对于大型对象，如果使用 shrink_to_fit，则内存消耗也更少）
改进的缓存性能（数据存储在连续内存中）
非稳定迭代器（在插入和删除元素时，迭代器会失效）
无法存储不可复制和不可移动的值类型
比标准关联容器更弱的异常安全性（在擦除和插入时移动值时，复制/移动构造函数可能会抛出异常）
比标准关联容器更慢的插入和擦除速度（特别是对于不可移动的类型）

devector

devector 是标准向量和 deque 容器的混合体，最初由 Thaler Benedek 编写。它在前端和后端都提供廉价的（摊销常数时间）插入，同时还提供 vector 的常规功能，特别是连续的底层内存。

与 vector 不同，devector 在元素之前和之后都可以有空闲容量。这使得能够有效地实现修改 devector 前端的方法。一般来说，devector 的可用方法是 vector 方法的超集，具有相似的行为，除了一些迭代器失效保证有所不同。

boost 的 devector 的静态大小开销是每个容器一个额外的 size_t：通常 sizeof(devector) == 4*sizeof(T*)。

当元素要插入到容器的一个极端，并且在该极端没有额外元素的空间时，有不同的策略。一种简单的策略是重新分配一个更大的缓冲区，并将所有元素移动到新内存。然而，当元素主要在极端之一插入时（例如，在一个极端推送并在另一个极端弹出，如 LIFO 模式），这将导致无限制的内存浪费。

为了避免无限制的内存浪费，Boost.Container 的 devector 使用了不同的策略

如果元素插入在某个极端附近，并且该极端有可用空间，则执行插入，而无需任何额外的数据移动（仅移动插入点和极端之间的元素）。
如果元素插入在某个极端附近，并且该极端的可用空间已耗尽，则所有现有元素都将重新定位（移动）到内部内存缓冲区的中心。这在耗尽的极端腾出空间以插入更多元素，而无需分配新的缓冲区。
潜在地，重用内存缓冲区的最大可能重定位（移动）次数为 Olog(N)，但这将导致非摊销常数时间在极端位置插入。因此，必须限制重定位次数（“重定位限制”），并且如果容器的负载因子（定义为 size()/buffer_length）超过重定位限制，则将执行重新分配（分配新的内存缓冲区）（有关更多详细信息，请参阅 Lars Greger Nordland Hagen 的 “双端向量 - 它有用吗？” 文章）。
这种方法在合理的内存开销和性能之间提供了合理的平衡。

然而，这种策略也有一些缺点

在极端位置插入没有强异常保证，因为数据必须在现有缓冲区内移动。
由于上面解释的内存重定位与重新分配策略
- capacity() 不再能告诉容器可以容纳的最大元素数量，并且同时，也不能告诉在执行重新分配之前要执行的插入次数。根据插入发生在哪一端，可能会发生也可能不会发生重新分配（也许该端有可用容量）
与其删除 capacity() 成员或将其重命名为“minimum_capacity()”，不如更改定义以告知可以插入的最小元素数量而无需重新分配。这允许典型的模式，其中
- 如果调用 reserve(n)，则 capacity() >= n
- 如果 capacity() == n，则保证如果 size() <= n，则不会发生重新分配。
但是，size() <= capacity() 的常用容器不变量不成立。size() 可以大于 capacity()，因为元素始终可以插入到具有可用容量的极端位置，而无需重新分配。

slist

当标准模板库被设计出来时，它包含一个名为 slist 的单向链表。不幸的是，这个容器没有被标准化，并且作为许多标准库实现的扩展保留下来，直到 C++11 引入了 forward_list，它与最初的 SGI slist 有点不同。根据 SGI STL 文档

“slist 是一个单向链表：一个列表，其中每个元素都链接到下一个元素，但不链接到上一个元素。也就是说，它是一个序列，支持向前但不向后遍历，以及（摊销）常数时间的元素插入和删除。与列表一样，Slist 具有重要的属性，即插入和拼接不会使指向列表元素的迭代器无效，即使删除也只会使指向已删除元素的迭代器无效。迭代器的顺序可能会更改（也就是说，slist<T>::iterator 在列表操作之后可能具有与之前不同的前任或后继，），但迭代器本身不会失效或指向不同的元素，除非该失效或突变是显式的。”

“slist 和 list 之间的主要区别在于 list 的迭代器是双向迭代器，而 slist 的迭代器是前向迭代器。这意味着 slist 比 list 的通用性差；但是，通常情况下，双向迭代器是不必要的。您通常应该使用 slist，除非您实际上需要 list 的额外功能，因为单向链表比双向链表更小更快。”

“重要的性能说明：像每个其他序列一样，slist 定义了成员函数 insert 和 erase。但是，草率地使用这些成员函数可能会导致程序慢得惊人。问题是 insert 的第一个参数是迭代器 pos，它在新元素之前插入新元素。这意味着 insert 必须找到 pos 之前的迭代器；对于 list 来说，这是一个常数时间操作，因为 list 具有双向迭代器，但对于 slist 来说，它必须通过从头到 pos 遍历列表来找到该迭代器。换句话说：除了在 slist 的开头附近，insert 和 erase 在任何地方都是慢速操作。”

“Slist 提供了成员函数 insert_after 和 erase_after，它们是常数时间操作：您应该始终尽可能使用 insert_after 和 erase_after。如果您发现 insert_after 和 erase_after 不足以满足您的需求，并且您经常需要在列表的中间使用 insert 和 erase，那么您可能应该使用 list 而不是 slist。”

Boost.Container 使用 C++11 特性（如移动语义和就地插入）更新了经典的 slist 容器，并以与标准 C++ forward_list 略有不同的方式实现它。forward_list 没有 size() 方法，因此它的设计允许（或在实践中，鼓励）实现不跟踪每次插入/删除的列表大小，从而允许基于常数时间的 splice_after(iterator, forward_list &, iterator, iterator) 的列表合并。另一方面，slist 为那些不关心线性时间 splice_after(iterator, slist &, iterator, iterator) 的 size() 提供常数时间的 size()，并提供额外的 splice_after(iterator, slist &, iterator, iterator, size_type) 方法，当程序员已经知道大小时，可以加速 slist 合并。slist 和 forward_list 因此是互补的。




static_vector

        static_vector 是 vector 和 array 之间的混合体：像 vector 一样，它是一个具有连续存储的序列容器，其大小可以改变，以及 array 的静态分配、低开销和固定容量。static_vector 基于 Adam Wulkiewicz 和 Andrew Hundt 的高性能 varray 类。
static_vector 中元素的数量可以在固定容量范围内动态变化，因为元素存储在对象本身内，类似于数组。但是，对象在插入到 static_vector 时被初始化，这与 C 数组或 std::array 不同，后者必须在实例化时构造所有元素。static_vector 的行为使得在具有复杂对象生命周期要求的案例中使用静态分配的元素成为可能，否则这将不是一件容易的事。其他一些属性

随机访问元素
在末尾常数时间插入和删除元素
在线性时间在开头或中间插入和删除元素。


        static_vector 非常适合用作缓冲区、其他类的内部实现，或用于必须存储的元素数量有固定限制的用例。嵌入式和实时应用程序是 static_vector 可能有益的一个特殊情况，在这些应用程序中，分配可能不可用或不可接受。



small_vector

        small_vector 是一个类似向量的容器，针对包含少量元素的情况进行了优化。它包含一些预先分配的就地元素，这使得当实际元素数量低于该预先分配的阈值时，它可以避免使用动态存储分配。small_vector 的灵感来自 LLVM 的 SmallVector 容器。与 static_vector 不同，small_vector 的容量可以增长超过初始预先分配的容量。

        small_vector<T, N, Allocator> 可转换为 small_vector_base<T, Allocator>，这是一种独立于预先分配的元素计数的类型，允许不需要以 N 参数作为模板的客户端代码。small_vector 继承了 vector 的所有成员函数，因此它支持所有标准功能，如就地构造、有状态分配器等。