在 C++26 时代选择合适的容器¶
标题：How to Choose the Right Container in C++26 and Beyond
日期：2025/10/30
作者：Alan Talbot
链接：https://www.youtube.com/watch?v=TtbYGico7bI
注意：此为 AI 翻译生成 的中文转录稿，详细说明请参阅仓库中的 README 文件。
备注：介绍标准库的 hive 和 inplace vector 等等。我觉得 hive 这种应该作为第三方库更好吧。
所以，我们今天要讨论如何在 C++26 中选择正确的容器。但我的幻灯片空间快不够了。喂？啊，好的。我可能会停下来回答几个问题，但我有很多内容要讲。最后肯定会留出更多时间。如果我们没时间回答你的问题，直接来找我就行。我今天一整天都在。
我们要谈论 C++。如果我说“当前的 C++”，我指的是 C++23。我知道，很遗憾，不是每个人都用上了 23，但它是最新的标准。如果我谈论“即将到来的 C++”，那将是 C++26，因为我们基本上可以确定这些内容会进入 26。具体来说，我们要讨论的是标准库容器。
我编程很长时间了，使用 C++ 有 35 年，在 C++ 委员会待了 20 年。但为什么？为什么要谈论容器？我的意思是，每个人都知道容器，每个人都使用容器。它们被讨论过，被写成文章过。为什么它们至今仍有趣？
对我来说，它们的趣味在于性能。如果你用得不对，它们的性能可能会非常糟糕。但如果你用对了，它们的性能会非常出色。事实上，我们之所以有这么多不同的容器，就是因为它们各自有不同的性能剖面（performance profile）。这几乎是我们拥有不同容器的唯一原因。如果你只用 vector，其实可以做很多事，但功能相当有限。我的意思是，有些事 vector 做不了，但主要还是性能问题。所以你必须理解容器的性能是如何工作的。
你可能会认为这是常识，但我发现其实不然。它的普及程度比你想象的要低。事实上，那些本应更懂行的人也不知道某些事情，比如，哦，我不知道，比如我。我最近学到了一些东西，我们稍后会讨论到，一些我本该知道但我却不知道的东西。而它实际上会对我当时正在做的项目产生影响。
标准库，标准库的设计，它的 API，正如坐在这里的 John 昨天非常雄辩地谈到的那样——我还没看他的演讲，坐上时间机器回到昨天去看看吧——它的设计给了我们一些关于如何使用标准库的提示，或者在某些情况下，不仅仅是提示，而是强制性的规定。不幸的是，这些在某些情况下是具有误导性的，我们将讨论原因。
性能，什么是性能？¶
我将很快地过一遍这部分，因为它已经被讨论过了。Matt Roper 周二做了一个很棒的演讲，同样，使用时间机器，然后马上回来这里。他的演讲详细地涵盖了这方面很多内容，非常棒，特别是关于分配和释放。
但事实是，正如我们可能知道的，访问主内存可能比访问内层缓存慢 100 倍以上。计算速度增长了很多，但内存速度却没有。因此，现代系统通过使用非常大的缓存来弥补这一点。而现代内存——这是我从 Fedor Pikus 去年的 C++ Now 演讲中学到的，我肯定念不对他的名字——现代内存用延迟（latency）换取带宽（bandwidth）。他们希望更快地传输更多数据。为了做到这一点，他们实际上比早期的芯片增加了延迟。
所以，如果你破坏了你的缓存（cache）——抱歉，是 cache，对吧？我在英格兰。是 cache 吗？哦，好的。我之前看的某个人把它叫做 cache，还说“哦，我真应该叫它 cache，但我们叫它 cache”。好的。我以为这是英国人的说法。如果你破坏了它，你的程序就会运行得很慢。引用局部性（locality of reference） 至关重要，比以往任何时候都重要。所以你可能以为，哦，这些问题正在消失，因为硬件太神奇了，确实如此。但不，情况实际上在变得更糟。你需要“高效率密度（high efficiency density）”才能高效。我的朋友 Howard 给了我这句话，我认为这是一种很好的表达方式。
这意味着大小很重要。大的就慢。你需要在主内存中获取的东西越多，事情就变得越慢。如果它能装进内层缓存，事情就会进行得非常快。这意味着对于小数据，计算往往占主导地位。但对于大数据，最终内存访问将主导你的程序。
顺序很重要。假设你按行存储一个数组，即行主序（row major order）。如果你按列主序（column major order）访问它，你会遭受 10 倍的性能损失，因为需要不断地去访问内存。但预取（prefetch）可以帮助你，因为你有固定的步幅。如果你是随机访问，预取就无能为力了。这会给你带来另外 10 倍的性能损失。所以相比于访问连续内存，你会有 100 倍的性能损失。
而且，分析内存成本非常困难。你的性能分析器（profiler）说，“哦，你在这段函数里花了很多时间”，但它实际上并没有告诉你你是在花时间计算还是在等待数据。
我们知道容器是用来装东西的。有些东西不是容器，比如字符串。它们装东西，但技术上讲不是容器。我们将专注于影响性能的行为，即宏观层面。而不是如何构建优秀容器的细节。这不是一个关于那方面的教程。你的库实现会有所不同。这些描述都是为了阐明观点而进行的简化。我们也不会谈论一些非常重要的事情，比如，自定义分配器（custom allocators），对吧？你可以用自定义分配器做各种惊人的性能优化。这里有多少人写过自定义分配器？举手。不多，对吧？我没有写过。你看，我的手没举起来。所以我谈论的是你开箱即用的东西。
连续序列容器¶
我们从连续序列容器开始。所有东西都在一个内存块里。你拥有最佳的迭代性能，最佳的引用局部性。但有一个问题，我们稍后会谈到。
所以我们得花点时间在这里谈谈 array 和 C 语言数组。我们知道这些是什么，对吧？每个人都知道。它们是本地的（local-only）、固定大小的，因此显然容量也是固定的。我认为这些是聚合体（aggregates），而不是容器。std::array 在标准的容器章节里，但它其实不是一个容器。它是一个带有一些容器便利特性的聚合体。所以我们不讨论这些。别误会，std::array 很棒，你应该使用它。但它的内存问题并不复杂。
std::vector¶
我们当然从 vector 开始。vector 是首选容器。每个人都这么说。我们昨天从 John 那里也听到了，Alex 和 Bjarne 都这么说。对吧？vector 把所有东西都放在一个单一的块里。如果有空间，它的插入是 O(1) 的。否则，你必须获取一个新块，把所有东西移过去。删除元素或调用 clear 并不会释放你的内存块。这很重要，记住这一点。内存块当然会在 vector 被销毁时释放。或者你可以调用 shrink_to_fit，如果 vector 是空的，它就会释放内存。
为了形象地说明这一点，我喜欢把它想象成一个救生艇。我们的元素们在游泳，希望能进入救生艇。它们都想去船头。元素们一个个来了。现在发生了什么？哦哦。我们需要一艘更大的船。问题来了。我们得搞一艘更大的船。然后我们得等着所有人都移过去。最后，呼。好了。然后我们终于可以扔掉旧船了。
所以当你空间用完时，你需要大量可用的空间，对吧？我写的这些幻灯片是基于 50% 或 1.5 的增长因子，这是微软使用的。其他一些库使用 100%，即 2.0。问题是一样的，只是数字略有不同。你需要很多空间，因为你需要新旧两个块共存。所以理论上，在完美的世界里，如果你用 50% 的增长率，你不能让一个 vector 增长到超过内存的五分之三；如果用 100%，则是三分之二。但在实践中，永远不会是那样的，对吧？因为还有其他事情在发生，你有内存碎片。你不会正好达到那些数字。你无法用一个 vector 填满内存。除非你在程序开始时就知道它需要多大，然后一次性预留所有空间。如果你有很多 vector，这通常不现实。
当然，增长是昂贵的，因为你必须移动、复制，而对于大尺寸，移动和复制（或主要是复制）将占主导地位。别指望移动语义（move）能在这里救你。似乎有一段时间，有种想法是，“哦，我们有移动语义，所以没问题。” 你放进 vector 的大多数东西，在移动和复制之间的性能差异并不大。我的意思是，即使是像 std::string，对吧？string 有资源，它有移动行为，这很棒。假设你有一个 vector<string>，里面存着你组织里所有人的姓氏。有多少个姓氏会长于 15 个字符？对吧？移动和复制会是一样的，因为 string 有一个 15 个字符的短字符串缓冲区（SSO）。你总是在复制那部分。
你可以通过 reserve 来避免一些抖动（thrashing）。让我们看看这个。这是 vector 的基本内存图。我相信这里的每个人都知道。非常简单，一个轻量级对象，只有三个指针。
但我们是怎么到这一步的？好吧，我们从空开始。很好。我们放进一个元素。我们有一个长度为 1 的块。乘以 1.5，嗯，你不能增长少于 1，所以我们会增长到 2。再乘以 1.5，再放一个元素，我们增长到 3。现在，3 乘以 1.5 是 4.5，但它会向下取整。所以，又一次分配。这些都是分配、释放，超级慢。最后，到 5 的时候，你多了一个空位。所以，在你开始处理更大的尺寸之前，你一直在抖动。
我们能做些什么呢？我们可以预先 reserve(8)。现在我们可以直接填满它，对吧？没有了那些抖动。
但尽管这有帮助，根据你的情况，这并不是真正的问题。因为 vector 的增长方式，它会形成所谓的容量历史（capacity history）。我想这个词也是从 Howard 那里听来的。一段时间后，容量将是完成任务所需的最大值。假设你用了一堆 vector，往里面放东西，又拿出来。它们会倾向于增长到合适的尺寸，然后就保持在那里。好的？所以你可能事先不知道这个尺寸是多少，所以你不一定能预先保留。毕竟，如果你预留了太多，那也有其自身的成本和问题。
所以，如果你 clear 一个 vector，容量历史被保留了，对吧？因为它不会释放内存块。但如果你销毁 vector，内存块就消失了。
那么，如果你的 vector 在一个循环里呢？ 遵循良好的编程实践，你会把声明放在使用它的地方。也许你甚至会声明它并把它传递给一个函数。我是说，把它作为右值（R value）传递给一个函数，谁知道呢。关键是 vector 的作用域在你的循环里。你将会在每次循环中创建所有这些内存，删除它，创建它，删除它。而且，根据你预留得有多好，你每次都必须重新爬上那些对数级的台阶，才能达到所需的大小。
所以，如果你在程序的各处都这样做，或者很多不同的函数都在这样做，并且有很多 vector 同时存在，情况会因为内存碎片而变得更糟。毕竟，vector 的增长会产生碎片，对吧？它变得越来越大，你必须不断地删除，留下这些空洞。而且在代码中发现这种情况也更难。顺便说一句，Matt Roper 周二的演讲就谈到了这个问题。
我不经意间就在写一个模拟器时这么做了。那个模拟器用了一堆临时 vector 来存放东西。我发现当步数增加 10 倍时，运行时间增加了 100 倍。糟糕。出问题了。我做了性能分析，时间都花在了 vector 的分配上，但我做的每件事都是对的。我 reserve 了，我小心地移动东西。到底发生了什么？我想我们能看到问题所在，对吧？我用所有这些 vector 的创建、删除和增长，把堆给弄得一团糟。
那么，解决方案是什么？如果是一个非常简单的情况，你可以把 vector 提到循环外面。但大多数你遇到的情况没那么简单。你也不想把 vector 一层层地传下去，仅仅为了获得这种行为。那不是很好的设计。
更好的方法是：回收利用（recycling）。对吧？把死掉的 vector 放进一个容器里，这个容器会持有它们直到你再次需要它们。一个回收箱。
我用了这个技术，运行时间从 7 小时 15 分钟降到了半个多小时。我的客户对此非常满意。这是改变游戏规则的，对吧？是的。而且实现起来非常简单。
这是一个极其简化的例子，但它能运行并且有效。你可以在各处使用这个类。我是说，显然，它应该是个模板什么的。我这里只用了 int。
// 伪代码示例
class RecycledVector {
std::vector<int> data;
static std::vector<std::vector<int>> recycling_bin;
public:
RecycledVector() {
if (!recycling_bin.empty()) {
data = std::move(recycling_bin.back());
recycling_bin.pop_back();
} else {
data.reserve(INTELLIGENT_SIZE); // 做一些智能的预留
}
}
~RecycledVector() {
data.clear();
recycling_bin.push_back(std::move(data));
}
// ... 其他 vector 接口 ...
};
如果没有东西在回收箱里，我们就做一些智能的预留，如果可以的话。然后我们就开始工作了。当我们用完后——这里有个指针，我就不费事了。你可以看到这里的析构函数。当我们用完后，我们 clear 这个 vector，然后把它扔进回收站。我们把它 move 进一个静态的 vector<vector<...>> 回收站。然后，当另一个实例出现并被构造时，回收箱里有东西，我们就把它 move 回我们的本地实例。
效果很好，非常简单。只是别忘了每周把你的回收箱拿到街边倒掉。因为，显然，你持有着内存。如果你用完了，你不会放手。
std::vector (bool)¶
现在我们来到 vector<bool>。是的，据我所知，这是标准库最著名的失误。它存在了很久很久，并且从那时起就一直引起某些反响。我想谈论这个的原因之一是，你知道，我认识的每个人，或者说我与之谈论 C++ 的每个人，都知道这个，对吧？但这并不一定广为人知。我认为谈论它很重要。
有一篇论文，这事是在 C++ 委员会的邮件列表上出现的。有个人发表了一篇论文，他们在做某种算法的分析。他们比较了几种语言。他们需要一个布尔字节的向量。好的。他们在几种语言里都这么做了。他们用了 vector<bool>，期望得到一个布尔值的向量。他们怎么会这么想呢？猜猜性能比较结果如何？猜猜 C++ 表现如何？对。非常糟糕。因为，这和 C++ 本身无关。对吧。你也不能怪作者们，对吧？任何一个心智正常的人怎么会想到，在世界上所有的类型中，唯独 bool 会做完全不同的事情？
所以，vector<bool> 的问题是什么？它不是一个序列容器，因为它技术上讲不是一个容器。它不满足要求。它也无法满足要求，因为，其一，你不能有一个指向比特（bit）的引用。
当然，它也不是一个 vector of bools，正如我所说的，这至少有点误导。请注意，一个比特集（bitset）是非常有用的数据结构。一个合适的比特集可以为你节省空间和时间。问题不在于比特集。vector<bool> 只是一个不那么好的比特集。这是因为大多数库没有专门的算法。现在，有一个例外。我听说 Lib C++ 有，可能是 Howard 的功劳。但大多数没有。我相信我不需要解释，单独访问比特是一个巨大的性能劣化。而且，它不适合 vector。它被硬塞进了 vector，而不是作为自己的类被正确实现。
所以你该怎么做？嗯，标准库有一个 bitset，而且它的名字，令人惊讶地，叫 std::bitset。但它是一个静态比特集。如果你想要一个动态的，Boost 有一个叫 dynamic_bitset。如果你真的想要一个布尔字节的向量，你可以这样做：
std::vector<uint8_t> my_bools;
// 或者
std::vector<char> my_bools;
用 8 或任何你想放那里的东西。就是别用 bool。因为你可能永远也得不到你想要的。
inplace_vector (C++26)¶
好了，让我们来看点好消息，一些更有趣的东西。inplace_vector，一个即将到来的新成员。我说的“即将到来”，指的是 C++26。它提供了一个 本地的（local） 连续序列容器。我想我之前没提过，我说的“本地”，意思是不是在堆（heap）上。我指的是在栈（stack）上，嵌入在一个对象里，在全局内存里，在寄存器里，但不是动态分配的。所以它就像 Boost 的 static_vector，如果有人熟悉的话。
元素被嵌入在容器对象内部，它也有一个大小（size）。容量在编译时是固定的。在其他方面，它试图尽可能地像一个 vector。因为它不分配内存，我们谈论的所有这些问题都不是问题。如果你能使用一个固定容量的容器，它的性能可以有戏剧性的提升。你甚至可以选择当超过容量时会发生什么。你可以抛出异常，可以返回一个空指针，或者你可以让程序崩溃。或者未定义行为（UB）。它会做什么来着？是灯光亮起，龙飞出来烧掉键盘。我喜欢那张幻灯片。我真希望我有那张。或者，是的，总之，给你的老板发邮件，告诉他你辞职了，诸如此类。所以你可以选择。
因为我想给每样东西都配上图，所以很明显它会是什么样子。你有一个大小，你的元素来了。你有一个固定的容量 5，试图放进第 6 个，然后你就会得到……随便什么。所以 inplace_vector 很棒。即将登陆你身边的编译器。
clump (提案)¶
这是一个提案。它目前还只是一个提案，而且暂时不活跃。但尽管名字有点老土，这实际上就是 Boost 的 small_vector。它是一个小缓冲区优化（SBO）的 vector。这也是我们非常想要的东西。我们会在最后讨论 sequence 的时候再回到这个话题。它提供了 vector、inplace_vector、clump 以及其他行为。我们会再回来的。这是一个提案。
块式容器¶
好了，我们来谈谈块式容器。我的意思是，从某种意义上说，它们都是块式的，都有块。但我们现在谈论的是可能有一个以上块的容器。这些容器提供了很好的迭代性能，因为迭代器大部分时间只是在迭代连续内存。它确实需要一个分支来判断是否到达了末尾。但我有点超出我的舒适区了，我不是硬件专家，但分支预测应该会很好，因为它总是不成立，直到最后才成立。所以迭代得很好。如果你的块足够大，引用局部性也非常好。
std::deque¶
我们从 deque 开始。deque 是 double ended queue（双端队列）的缩写。事实上，有些人称它为 DEQ。deque 将元素保存在动态分配的块中。但 deque 的有趣之处远不止它是一个双端队列，我们稍后会看到原因。
这些块由 deque 内部称为map的东西管理。如果你真的去看代码，这会很困惑，因为它不是一个 std::map。它甚至根本不是一个关联数组。它只是一个指向块的指针的 vector 或者说数组。它的管理方式因实现而异。事实上，我讨论 deque 的一个主题就是，所有这些的设计都是实现定义的，而不同实现在 deque 的做法上差异巨大。我们稍后会回到这一点。
如果有空间，插入是 O(1) 的。如果没有空间，你会得到一个新块，但没有元素被移动。所以这非常好。删除一个块中的所有元素可能会也可能不会释放它，这取决于你的实现。
但 deque 真正棒的地方在于它提供了细粒度的线性内存增长。对吧？你可以用它填满内存。vector 因为是指数增长，你做不到，我们已经看到了。但对于 deque，因为块的大小相同并且不会变得很大，你可以把内存填得满满的。效果很好。在我看来，这比它是一个双端队列重要得多。而且增长不会导致碎片，因为如果你只是持续增长，没有任何东西会被释放。
不幸的是，你无法控制块的大小，这是一个拖累，因为如果你确实想填满内存，你会希望能够调整它。记住这一点，你希望能够调整它。而且有些库的块大小小得离谱。我们马上就会看到这会如何影响你的生活，或者我的生活。
尽管如此，这是使用 deque 的一个非常好的理由，因为标准库里没有其他东西有这些特性。你唯一能用的其他东西是像 list 这样的，它能以完美的精度填满内存，但由于我们稍后将讨论的原因，它非常慢。deque 有随机访问，迭代快，引用局部性好。有什么不喜欢的呢？
我们快速看一下这可能是如何实现的。同样，这是一个简化的图示。我显然遗漏了一些东西，因为没有东西挂在 map 的开头和结尾，但你知道，你懂的。所以我们有一个元素，两个，三个。现在发生了什么？我把多余的箭头去掉了，因为那样会太乱。你应该在想象中认为它们还在那里。我们再从前面添加。我们为前面得到一个新块，然后开始从它的后面添加。我们想从后面添加，我们为后面得到一个新块，然后开始从它的前面添加。这基本上就是 deque 所做的。很酷，是吧？
但不幸的是，又到了我们的第一个误导插曲。对于小尺寸，deque 是糟糕的，对吧？你可以看到原因。它有这个大的 map 结构。如果块的大小合理，它们可能会很大。你知道，如果你有一个只有 10 个元素的列表，而块的默认大小是 256 个元素。我的意思是，这里面全是开销。引用局部性和迭代是好的，但它们不如像 vector 这样的东西好。
另一方面，vector 没有任何前端操作。现在你可以用 insert 在 vector 的前端放东西，但它没有 push_front 和 pop_front 的事实暗示着也许你不应该这么做。对吧？这是 Alex 传递的信息。你不应该那么做。那是坏，坏，坏，坏的。别那么做。好的？事实上，我们将会看到，queue 坚持要求你有这些。所以你甚至不能用 queue 和 vector。
但对于小尺寸，vector 在内层缓存里。如果你有一个……我测试过这个，链接在最后，所有东西的链接都在最后，包括我的一次演讲，我在那里给出了一些数据。如果你在 vector 的前端推入东西，对于小的 vector，我说的小，比如，甚至 100。它的速度比 deque 快得多，当然也比 list 快得多。所以，不做这些事情是没有道理的。vector 前端推入的理论复杂度是 O(N) 并不意味着它慢。对吧？除非，当然，你的 vector 里有十亿个元素，那种情况下，是的，它慢。
好的？所以，发生了什么？我在模拟器里需要记录大量的小记录。模拟器的工作就是生成数据并保存它，然后根据数据吐出一大堆报告。好的？这需要不减慢模拟速度地完成。这些日志总是从后面增长。对吧？它们需要能被快速迭代。用户可以控制插入计算机的内存量以及模拟运行多长时间。这不取决于我。所以我必须准备好用这些东西填满内存，否则用户会不高兴。
所以我应该如何存储这些日志？vector 超级快，但我们已经看到，它的增长需求使得 vector 不可行。list 会很好地填满内存，但我们将看到，它非常慢。但 deque 似乎不符合这个模式，对吧？我的意思是，我们不需要一个双端队列来做这个。
所以我应该用什么？别一下子都说出来。对，deque。它插入快，它有你需要的一切。我就是这么用的。不是因为我不在乎，我从没在前端插入过。我只关心能很好地填满内存。它工作得还不错。
但我不知道 deque 的一件事，特别是微软的 deque。所以，这是一个惊喜。我最近才学到这个。微软的 deque 是一个非常奇怪的实现。我不是在挑剔微软，我是从他们的一位很棒的员工写的一篇文章中得到的这个信息，并发表了。那是一篇微软的文章。
对于我的情况，我的块大小是 1。好的？所以我不再有一个 deque 了。对吧？我有一个基于节点的容器。事实上，我得到的是一个指向节点的指针数组。但它也可能是一个链表。基本性能剖面是一样的。
所以我做了一个小测试。果然，我用一些小东西填满了一个 deque。然后我用同样的小东西填满了一个 vector<vector<...>>。快了四倍多。我昨晚看幻灯片时意识到我实际上没检查迭代。我本该检查的。因为我打赌迭代性能的差异也会非常戏剧性，因为引用局部性的问题。我总有一天会检查的。但我没做。但我打赌对于 deque 来说，迭代也会慢很多。我试了 list，果然，它只比 deque 慢一点点。它们很接近，在同一个数量级上。
所以，检查你的 deque。信任但要验证（Trust but verify）。
因为这篇来自微软的精彩文章，你可以检查三个最常见的库实现。因为他给出了一个完整的图表，说明了它们做什么以及如何做的。
（观众提问互动）
观众 A：这可能听起来是个奇怪的问题，但……你有没有想过自己实现一个deque？
演讲者：问题是，我有没有考虑过自己实现deque？我没有。因为我认为deque是……你知道，我没有深入研究。我没考虑到deque可能是个问题。现在，我可能会。是的？但我也可能……对于这个特定的情况，我实际上可能会用这个技术，一个vector<vector<...>>，这很相似。而且我可以控制……我可以调整它，而我不能调整deque。……所以我可能会，但我也可能用我已经有的部件，比如vector。
观众 B：这似乎是一个非常奇怪的实现选择。那篇文章告诉你为什么了吗？或者你联系了 STL（Stephan T. Lavavej）问他在想什么吗？
演讲者：我不认为是 STL。我想这比他要早。文章的作者是……我们最后会看到。你可能知道我说的是谁，我忘了他的名字，但他很棒。……但我怀疑这比他要早。文章的基调实际上是，这真的很糟糕。我想他们会修复它。但截至我用的最新版 2022，它还没被修复。
观众 C：这似乎证明了deque并未被广泛使用。对。因为肯定会有人发现这个。所以我希望我今天能解决这个问题。用deque，它很棒。去向微软抱怨。也许我会去向 STL 抱怨。
演讲者：……他本人说这是个香蕉问题。就像，“我知道怎么拼写 banana，但我不知道什么时候停下来”。那是 STL 的笑话。是的，他是个非常棒的人。
观众 D：在你继续之前，我能问一个关于deque的问题吗？你提到你不能真正控制块的大小。即使你加了某种自定义分配器，你仍然不能控制块的大小吗？所以deque的规范里完全没有任何地方允许你控制块的大小吗？
演讲者：对。deque不让你控制块的大小。那是实现定义的。……但别完全绝望。我们稍后会讨论一个容器，它让你能控制一些东西。不幸的是，它不是deque。……也许我们会有deque 2.0。因为它应该可以，对吧？我认为你应该能控制你希望控制的东西，比如块大小和你期望的块数量。
std::hive (C++26)¶
另一个 C++26 中的新容器。它叫 hive。以前叫 colony。请不要问我这些名字从哪里来，或者这些名字在何种意义上与它的功能相关。我不知道。啊，Guy 知道。我们有时间的话，我想听听。等我们讲完再提醒我。
仍然有一个 colony 项目。标准化的 hive 与原始的 colony 有些分歧。但它是一种更通用的数据结构的特定实现，这种数据结构已经存在很长时间了，有时被称为桶数组（bucket array）或对象池（object pool）。
它是一个块式容器。参考实现——还没有任何库实现它，但参考或示例实现没有用索引指向块。它用了一个块的双向链表。如果块满了，你会得到一个更大的新块，参考实现的扩展因子是 2.0。所以，块可以有用户定义的最小和最大尺寸，这很好。你得到了一些控制权。
它的独特之处在于，我的意思是，其中一件，我猜主要是，它的独特之处在于，当元素被删除时，对于它们留下的空洞不做任何处理。它被保留在原地，被记住，并被重用。所以，我们将看看这是如何工作的。
hive 因此提供了一系列在标准库中独一无二的特性。你有O(1) 的插入到未指定位置，因为，如你所见，hive 是无序的并且不支持随机访问。所以，除非需要创建新块，插入是 O(1) 的。O(1) 的任意位置删除。一个实现可能会丢弃一个空块，也可能不会。但如果它这么做，当然，当你做删除时，会花费更多成本。但是，对删除释放的空间的重用，稳定性，这里的主要问题之一是你的元素总是稳定的，但你有快速的迭代和相当好的引用局部性。
库里没有其他容器能同时做到所有这些事。它非常适合那些需要这些特性的用例：需要稳定性，有高变动性（volatility），并且需要快速迭代。而且不关心顺序。它只是一堆东西。比如游戏。它最初来自游戏行业，这个特定的 colony 项目。但这种数据结构已经被许多行业使用很长时间了。我不能告诉你它们都是哪些，但有几个例子是粒子模拟，这有点像一个有更多坏人的游戏。据我所知，我既不是游戏玩家也不是粒子模拟专家。还有金融数据操纵，他们总是需要东西快。所以它是一个通用容器。我说这个是因为我觉得有一段时间，我一直认为，哦，这是给游戏的。这不只是给游戏的。
我们有这个参考实现，我将给你一些快速的细节，因为它有点有趣。它是一个侵入式的块的双向链表，但块当然持有元素，但它们内部也维护一个空闲列表（free list）。它们这么做的原因是为了让空闲列表可以被索引而不是用指针，这样如果你的块大小不是太大，你就不需要用 8 字节做指针。我的意思是，你可以用 2 字节做索引，节省空间。
它们还维护一个叫做 跳跃字段（skip field） 的东西，跳跃字段的存在是为了让迭代器有 O(1) 的行为，无论迭代器需要跳过多少个空洞。这非常聪明。你会看到这是怎么做的。如果你用一个比特串来表示缺失的元素，延迟是任意的，因为你必须数一些比特，你不知道会有多少。这个用了一个不同的方案，所以你总是知道要跳到哪里，并且总是 O(1) 的。我相信，是的，我非常确定另一件事是比特解决方案需要一个分支，而这个解决方案在迭代器里不需要分支，不是为了做跳跃。在某个点，你还是得注意到你到了容器的末尾。
但让我们看看它。同样，我认为图画总是胜过千言万语。它开始是空的，就像所有容器一样。我们得到一个元素。我们有一个跳跃字段。我们加一些元素。它们会加更多元素。得到另一个块。好了。现在，我们看看如果我们擦除会发生什么。我们擦除一个元素。好的。那个元素进入了空闲列表，这是一个有点复杂的结构，你有一个有空闲元素的块的链表，然后在块内部，你有一个用索引编码的空闲元素的链表。你的跳跃字段显示 1，跳 1。好的。我们再删一个。好了。看，我们在往我们的块链表里加东西。现在我们要往我们的内部链表里加，注意现在它说 2，所以我们可以朝任一方向迭代并知道要跳多远。这还有更多内容，你会听到我经常这么说，我不会深入细节，但所有这些的作者，我有三个链接，一个论文链接，和两个来自作者的 YouTube 视频，如果你想了解更多，它们很棒。
好了。现在我们加更多元素。嗯，我们从空闲列表的头部开始。砰。对吧？然后砰，砰，砰。明白了吗？很酷。
（观众提问互动）
观众 E：抱歉，我不太明白那个跳跃字段。那不是每个元素都有的，是吗？你有一个很长的块。
演讲者：抱歉，我没太听清。
观众 E：我不太明白那个跳跃字段。
演讲者：啊，跳跃字段。所以，如果迭代器正在前进。是的。它说，好的，我在这里。是的。现在我要 ++ 迭代器。是的。它说加 2。等等。那么它会检查什么，来判断是否需要跳跃吗？
演讲者：嗯，这些其实是 0，我本该把它们写进去的。它总是加上这个数字。对。没有分支。每个元素都有一个字段。对。我只画了那些有趣的，但这个是 0。我明白了。所以它加 0。跳跃字段实际上是块的数量。我应该说，是的。是的。好的，酷。我跟上你了。谢谢。确切地说，它将前进1 + 这个数字。所以1 + 0是 1。1 + 2是……对。我应该修改幻灯片。
观众 F：当删除一个块时，如果你需要更新相邻条目的跳跃字段，这怎么能是常数时间的？
演讲者：你是说如果块是空的并且被删除了？
观众 F：不，不。抱歉。如果你有一个元素，你删除了那个元素，并且它被空元素包围，那么你也必须更新那些元素的跳跃字段，对吧？
演讲者：是的。我没展示那个。那非常聪明。这中间的数字，如果这里长度大于 2，它们不是无关的。它们会像数到这个数字一样。它用那个来做 O(1) 的删除。
观众 F：谢谢。
演讲者：问题是，为什么删除是 O(1) 的？答案是，读论文/看视频。因为它非常有趣，非常聪明，并且描述得非常好。我不是教这个的合适人选。
观众 G：当你插入东西时，它们是就地插入的吗？它们在迭代时是什么顺序？
演讲者：当你迭代它们时，它们是什么顺序？看起来它们是随机顺序的。随机顺序。好的。顺序不被维持。是的。这不是一个有序容器。它在某种意义上是一个序列，但我猜，没有维持的顺序。
基于节点的序列容器¶
list 和 forward_list。我们可能现在已经理解了，对吧？每个元素都在自己的内存分配中。所以你的块大小是 1。这对于小元素来说开销非常高。迭代性能差，对吧？因为它随机访问内存中的随机位置。这是最坏的情况，因为引用局部性很糟糕。
但 list 还是有些用处的。这里一个小提示，如果你来自 C++ 以外的地方，名字有点混淆。list 是双向链表。forward_list 是我以前学的那种链表，或者你喜欢叫它单向链表。只是名字是这样。
你得到O(1) 的任意位置插入和删除，保证。你得到维持的顺序。你得到完美的稳定性，没有任何东西会移动。你得到大部分 O(1) 的拼接（splicing）。为什么你不能一直得到 O(1) 的拼接？我写这张幻灯片时花了一分钟才想起来。因为容器必须维护一个大小字段，因为 size() 函数在标准库中对所有容器都被指定为 O(1)。对于链表，拥有 O(1) 大小的唯一方法就是维护它。所以如果你拼接进一个任意的……指向某个任意列表块的两个指针，你必须数它。那是 O(N)。但如果你只拼接进一个东西，那是 O(1)。
完美的稳定性代价高昂。但是，你知道，对于大的……如果你有巨大的东西或者根本不能被移动的东西，那么它是一个很好的解决方案。东西不会移动。你可以在原地就地构造（emplace construct）它们。它们永远，永远不会移动，直到被析构。如果你需要……如果你需要把它们移动到另一个列表，你可以拼接。所以它确实提供了肯定有用的功能。只是别想，“哦，我可以在头尾推入，所以这会是一个快速的方法”。不一定，我们已经看到了。
这是计算机科学 101，对吧？你有前驱后继指针，头尾指针，大小字段，对吧？我不会在这里停留，除非有人举手说，“不，不，不，解释一下”。哦，有人举手了。只是，我假设没有大小字段。哦，forward_list。我们马上就要讲到了。对。是的。这是 list。forward_list 非常像 list，但只有一个指针，并且没有 size() 函数，因为没有大小字段。这就是问题或者评论，forward_list 中没有大小字段。这是真的。原因是 forward_list 的设计目标就在那里。那段引用来自标准中 forward_list 的顶部部分。这应该等同于一个手写的 C 风格单向链表，直接引自标准。好的？它长这样。没有大小字段，一个指针。砰。砰。好的？所以如果因为某种原因你需要这个，你有了。很难想象这个有很多用处，但还是有一些的。
（观众互动）
观众 H：它不符合 SDL 的约定，因为它的名字……
演讲者：是的。他说它不符合 STL 的约定，因为所有修改函数的名称都是..._after，因为……是的。是的。它不……如果你插入……如果你有 A, B, C，你在 B 处插入 X，你会得到 A, B, X, C，而对于list，你会得到 A, X, B, C，因为，你知道，它不能……它将不得不回到开头，否则插入会是 O(N) 的。
容器适配器¶
现在我们来谈谈一些非常有趣的东西。容器适配器。我不确定我是否用过这些。它们一直在那里。我只是有点忽略它们。容器适配器。这些东西其实很酷。它们是容器的包装器，它们提供了一个特定的……我想用什么词？门面（facade）。谢谢。我刚才有点卡壳。它们为容器提供了一个特定的门面，它们很棒。
你必须记住几件事。首先，它们拥有自己的容器。它们不引用你的。这意味着把东西放进去……处理你的容器会变得有点棘手，我们稍后会看到。但通过移动进去，你可以得到一些你想要的行为。它们也有特定的要求。它们会在容器上调用某些东西，如果那些东西不存在，它们就不能工作。我们将看到……我们已经看到了这个问题。我们稍后会回到它。
我们有 stack（栈），queue（队列），和 priority_queue（优先队列）。
stack可以与vector、list和deque一起工作。酷。默认是deque。queue可以与list和deque一起工作，但不能是vector。我们已经看到这个了。默认是deque。priority_queue可以与vector和deque一起工作。priority_queue不能与list工作，因为它内部维护一个堆（heap）。
到这里，你可能在想，等等。queue。你很可能想要一个小小的队列，装一些小东西比如指针，只有几个，并且希望它工作得非常快，对吧？哦，我们知道我们想要哪个容器了。我们想要哪个容器？vector。糟糕。抱歉。你用不了。此时你的怒火应该正在升腾。
我想我们得回到另一个误导插曲。vector 没有前端操作，所以你不能在它上面用 queue。而 deque 和 list 如果你真正想要的是一个小而快的队列，都是糟糕的选择。你也用不了 inplace_vector，那本来会非常好，因为那样，我是说，可以有一些非常棒的应用。但不，抱歉。
另一件事，你可能注意到了 stack 默认是 deque。为什么呢？我是说，同样，你想用 deque 的唯一原因就是如果你要有一个巨大的栈，并且你担心填满内存之类的事情。否则，你为什么不想要一个 vector？那肯定更好。我是说，而且，人们用默认值。我是说，你不会就这么写吗？std::stack<T> my_stack;。这给了你一个 deque 和它背后所有的机制、分配之类的。你甚至可能没意识到发生了什么。是的。
不知道为什么，但它可能应该默认是 vector，但这已经是很久以前的事了，大概从 98 年开始就是这样了。
关联容器¶
我们将快速过一遍关联容器，因为它们没有提供太多可谈论的东西，但从根本上说，它们是基于节点的容器，所以基本的内存行为和 list 这样的东西是一样的。但我假设每个人都熟悉这个。我们有 map 和 set。map 存储键和值，set 只存储键。我们有 multi 版本和唯一版本。我们有有序和无序的。
无序的，正如 John 昨天指出的，就是其他人所说的哈希表（hash table）。如果你想知道为什么它不叫哈希表，去看他昨天演讲的视频。他描述得很好。我不会深入。而且，它们都是基于节点的，包括哈希表，无序的那些。对于使用哈希表的人来说，这可能是个惊喜，它是基于节点的，但标准库对容器施加的要求使得它必须是基于节点的。因为无效化（invalidation）的要求。所以，我们稍后会看到它长什么样。好的。map 和 set 是同一个东西。如果你看过代码，它们是同样的代码。只是，你知道，你有一个键，或者你有一个键值对。有序版本是搜索树。无序版本是哈希表。
我不认为这增加了太多。哦，所有这些都支持拼接、重新键控（rekeying）和其他节点操作。这是自 C++17 以来的。我今天不打算深入，但我再次链接了我的一次演讲，我在那里描述了这些以及你能做的事情。所以，这算是新的。C++17 相当新。你可能没意识到。这很酷。
（观众提问互动）
观众 I（在线）：std::list的移动构造函数不是noexcept，这似乎是个问题。这是个问题吗？如果是，你对使用list有什么建议吗？
演讲者：……微软的实现没有noexcept。是的。这背后有很多故事。那不是我今天有时间讨论的话题，我得回去……在某个时候我确实知道那个问题的答案，但我可能得回去和几个人谈谈才能给出一个合适的答案。所以，给我发个邮件什么的，我会……这里讨论太长了，我不确定我能脱口而出。移动构造函数应该是noexcept的。
好了，我们说到哪了？set。这里真正的问题是，你想要一个有序的数字列表？你用 set，对吧？嗯，记住，你为了 set 的便利性，正在承受所有这些难以置信的性能劣化。不过，先等等这个想法，因为我们马上会讲到一些非常好的消息。但如果你用 set，你用的是一个基于节点的容器。所以，如果你只是有一些本地的小东西，填满一个 vector，排序，然后二分查找，会快得多。
set 大概长这样。同样，这不是一个关于如何写 set 的教程，只是给你一个概念。你有几个指针，我直接跳到 map 的图。你会注意到它完全一样，只是多了一些东西，因为它们实际上就是一样的。
map 很好。它给你有序性和 log(N) 的插入和查找。它创建了一个字典。如果你不关心性能，当然，用它。但是等等。
快速说一下，unordered_map，我想我们已经讲过了。哈希表确实可以提供比搜索树好得多的性能，因为查找大约是 O(1)，假设你的哈希函数好并且没有太多冲突。然而，这是一个关键点。标准库的哈希容器是出了名的差。原因是，我们不喜欢改变 C++。所以 API 或 ABI，意味着当技术水平发展了，而你无法在不改变 API 或 ABI 的情况下改进某样东西时，它就不会被改变。所以，老实说，你可能会试试这些，但如果你对哈希表了解很多，你可能有一个更好的。标准库里的那些不是最好的，但它们在那里。它们大概长这样。重点是，那里是链表，双向链表，而不是其他更高效的结构，因为有不使指针等无效的要求。
flat_map 和 flat_set (C++23)¶
现在，好消息来了。我看到这些东西时甚至没注意。然后当我开始研究它们时，我意识到这些家伙太棒了。这些是 flat 系列。它们是 C++23 的新成员，它们包装了一个或两个顺序容器，连续容器，比如 deque 或 vector。它们为你提供了 map 和 set 的行为，所以你不用自己做。你不用填一个 vector，然后排序，然后搜索。它们为你做。
这些家伙，它们可以和 vector、deque 和 inplace_vector 一起工作。它们默认使用 vector，就像它们应该的那样。我认为它们绝对会很棒。你需要知道关于它们的几件事。但对于很多用途，这些将优于传统的 map 和 set。它们都在，所有四个，如你所见 (flat_map, flat_set, flat_multimap, flat_multiset)。
那么，有什么陷阱呢？你可能想预加载和预保留容器。你可以这么做。直接把它们移进去。好的？因为记住，适配器维护它们自己的副本。所以，你必须移进那个副本。好的？这很容易做。但如果你想稍后 reserve 或调用 shrink_to_fit 之类的呢？那就不那么明显了。它长这样：
auto container = std::move(my_flat_set).extract();
container.reserve(new_capacity);
my_flat_set.replace(std::move(container));
所以，你必须提取容器。我这里有个指针。啊，有了。你必须提取容器。注意 extract 是一个右值限定的函数。你必须在一个右值上调用它。所以，你必须在你的 set 上调用 move，然后调用 extract。然后你可以对容器做任何你想做的事，然后你可以用一个叫做 replace 的函数把它移回去。
所以，当我第一次意识到必须这么做时，我有点紧张。这感觉就像，好的，我往窗外一看，看到院子里全是僵尸，然后有东西敲门，我走过去把门打开了。对吧？不是个好主意。所以我和一个我很看重的库维护者谈了，他说，没问题。replace 会恢复不变量（invariants）。你调用 replace 后就活过来了。所以，据我所知，这不是 UB 或任何太可怕的事情，你也可以用 map 这么做，你也可以用 shrink_to_fit 这么做。我只是，是的。好了。我爱这些东西。用它们。
又一个例子¶
好了，还有一个例子。我以前在一家数字地图公司工作，我从他们的 GIS 数据库中提取产品，那是一个复杂的数据库，我们在数据库里做的所有那些连接，或者说他们做的，在我去的时候，都超级慢。他们的运行需要三个星期。是的。连续三个星期的计算机时间来运行。
所以我意识到把所有这些都转储到内存中，然后在内存中把所有关系做成指针会快得多，它就是运行得快很多。所以我用了 map，你知道，键是表的主键，值是，你知道，我创建的任何行对象，包含我需要的任何东西，它工作得很好，我把时间从三周降到了八小时，这，你知道，有点改变游戏规则。
我把内存填得非常满。我知道这一点，因为我最初是在一台 32 位计算机上工作的，我必须告诉 Windows，我想要 3GB，而不是 2GB，作为我的进程空间。你必须用某种魔法方式来做，否则它只会给你 2GB。我们必须那么做才能处理最大的地块，而最大的地块是德克萨斯州。好的。因为，记住，这是一个道路数据库。阿拉斯加比德克萨斯大两倍多，但阿拉斯加的道路很少。它工作得很好，把内存填得很好。
但我好奇下次如果……我是说，我好奇我是否留下了一些性能空间，我好奇下次我是否应该用一种稍微不同的方式来做。因为我有一个非常受控的环境，你可以问数据库表有多大。那是 O(1) 的，它知道。而且没有任何东西在改变。我是说，这是一个读取程序。它读取数据并用它制造东西。一旦它们在内存中，它就再也不会碰这些东西。所以，我好奇使用预留到确切大小并适当分配以很好地填满内存的 vector，是否会带来更好的性能。我不知道，但它肯定会占用少得多的空间，而且更小，对吧，大的慢，小的快。这会很有趣。
当然，现在我们可以用 flat_set 和 flat_map。那我应该用什么？flat_set 还是 flat_map？对于这样的东西，快速测验一下。没人？唉。好吧，这可能要看情况，但……如果我有两个 vector，也就是 flat_map 用的，它们相对于彼此的引用局部性很差。它们在内存中是任意放置的。所以，如果它们巨大，可能没关系。我会从每个里面读一堆页。可能没什么区别。但如果它们小，如果你有一个相对小的 map，也许就把它做成一个 set。毕竟，你可以把键放在对象里的某个地方，并用它作为你排序的依据。那样你就只有一个容器，一次……你知道，一次从主内存的读取。值得思考。
（观众互动）
观众 J：缓存里的键更少。
演讲者：是的。那是权衡。那就是为什么，那就是为什么你喜欢分开的……说得好。这是一个权衡。但是，如果它无论如何都能装下，比如如果整个东西都能装进缓存，那你用set更好。所以，这关乎大小。
sequence 提案¶
好了，我们到了最后一章。我要谈谈 sequence，这是一个大约一年前委员会审议过的一个提案。我只是想让你们知道，我是一个绝对独立、客观的第三方报道者。
所以，sequence，我讨厌这么说。我不想这么说。我真的不想这么说。你可以把它看作是 vector 2.0。哦，我说出来了。我讨厌 vector 这个名字，因为 John 昨天讲的所有原因。我也不一定希望人们认为这必须像 vector。但是，它有点像 vector 2.0。
它有四种内存处理模式。
local：我们已经谈过这个词的意思了。这就像inplace_vector。事实上，它完全就像inplace_vector。它是inplace_vector的一个直接替代品。variable：你也可以把它想成vector模式。我永远不会在纸上这么叫它。这就像vector。它是vector的一个直接替代品。fixed：像local，只是在堆上分配。所以，固定大小，但在堆上分配。我认为这在很多方面都很有用。特别是它减小了……我们稍后会看到，它把对象本身的大小减小到一个指针。buffered：也就是小缓冲区优化（SBO），就像clump或boost::small_vector。
让我们快速看一下这些。同样，还是那些图。这就像 inplace_vector，不应该有惊喜。那是 local。这是 fixed。注意，完全一样的东西，只是在堆上，从 sequence 对象出来一个指针。这个应该看起来很熟悉，它和 vector 的幻灯片是一样的。
我们还有 buffered。在这种情况下，我们在缓冲区里。三个元素，缓冲区大小为四。有一个标志，我们有这个额外的字段来告诉它是否在缓冲区里。或者我们有一个像 vector 的块，像 vector 的指针，标志说动态。
因为这些，sequence 包容了 vector 和 inplace_vector。是的，时机不幸。如果我能坐上我的 DeLorean 回到几年前，这样我们就不必做 inplace_vector 了，那会很好。但别误会，我们有 inplace_vector 真的很棒。我真的很高兴它在那里。
而 clump，我没怎么谈它的原因是因为它和我们这里谈的 sequence 完全一样。如果这个提案通过了，我们就不需要 clump。如果没通过，那么 clump 在改个更有希望的名字之后，我希望我们能真的做出来，因为我们确实需要这种行为，小缓冲区。
它没有
vector<bool>特化。 （一些掌声）谢谢。谢谢。事实上，如果你说sequence<bool>，你会得到一个bool的序列。多么奇怪。它有另一个东西，你可以调整大小类型（size type）。这很好。现在，这可以自动完成。实际上，我看到的
inplace_vector是自动做这个的。但我认为让用户能够做这个很好，因为你可能想要你的大小……假设你只会放，你知道，31 个东西进去，你想要用一个 1 字节的大小，对吧？但如果你关心的是最大速度呢？那你可能真的想要你的大小字段是一个字（word）。而只有你，你知道，不同的计算机有不同的字长。所以，用户可以指定大小字段类型。两种有增长的模式，也就是
vector模式和buffered模式，你可以控制增长。你可以线性增长，按用户指定的大小，或者指数增长，按用户指定的因子。所以你可以控制它，你可以调整它。我加了另一个，vector。这是为了以防库的vector有些东西不能被单独的指数增长精确模拟。我是说，我不知道这是否存在，我不知道这是否必要。但如果我们把它留着，它让供应商可以精确复制vector的行为，这样vector就可以用sequence来定义。同样，新的和不同的是，有三种元素定位模式而不是一种。
front，像vector。back，像标准库里没有但可能很有用的东西。和middle，像deque，一个真正的双端队列。让我们看看它们。所以，
front，好的，没什么惊喜，对吧？那是vector。back，朝这边长。是的。middle，我们从中间开始，然后我们往两边走，但是当我们开始删除和添加，删除，添加，删除。现在，当我再加一个时发生了什么？它移动了。事实上，Jonathan Wakeley 给我介绍了这个，他称之为一个 shifty vector（会移动的向量），我认为这是个极好的名字。
（观众互动）
观众 K：我有一个关于这种移动模式的问题。为什么环绕（wrapping）不是更可取的选择，因为那样你就不必移动已经存在的东西了？就像你，如果你回到那张幻灯片，你有中间模式并且它填满了，如果你现在在末尾再加一个，为什么你不能把它放在块的开头，做成一个像……像一个环形缓冲区（circular buffer）？
演讲者：因为它……因为它是一个有序序列，就像vector一样。那会……
观众 K：但是如果你已经有两个大小字段，比如缓冲区的已用部分的开始和结束，那么你也可以……如果已用部分在缓冲区的末尾，而你还想追加，你可以环绕过去，开始指向第一个已用元素，然后结束……有一个更小的索引值，但逻辑上在后面。
演讲者：好的，但你将如何迭代它？
观众 K：从开始，然后向前，向前，向前。当你到末尾时，你环绕，直到你到达结束。
演讲者：是的。所以问题在于，元素不再是互相连续的，而这是一个……这个容器的一个不变量是元素总是连续的，就像vector一样。它们不能被分成两块。
观众 K：好的，如果这是一个要求，是的。
演讲者：是的，它只是……是的。总之，但那对于某些事情可能有用，但不是这个容器，因为那会违反我们追求的性能类型。如果它有那种行为，迭代肯定不会那么快。
所以，总之，委员会提出的一个反对意见是这太复杂了。可怜的程序员们将无法处理这个。对此我说，胡说。首先，C++ 程序员很聪明。他们当然能处理这个。其次，如果你能操作一台 70 年代的音响，你就能操作这个。好的。（幻灯片展示了一台有很多旋钮的复古音响）。
哦。所以，这个，我不该用他们的笔记本电脑，你的笔记本电脑，因为 sequence 的字体，我用了……我用了正确的字体，像 Marantz 的字体。所以，哦，好吧，我以后会记住。如果你在我的笔记本电脑上运行，它会显示正确的字体。
其他特性¶
front和back访问函数。整个 API 总是可用的。好的。无论任何这些设置如何。是的。谢谢。固定的容量，你可能会说，好的，那用于
local模式，fixed模式和buffered模式。buffered模式，它描述了缓冲区的大小。那vector模式呢？variable模式。我在variable模式下。它描述了初始分配的大小，初始块。所以，是初始容量。这真的很酷，因为这是一个常见的模式，声明一个vector，立即reserve它，然后去用它。对吧？问题在于它不是惰性的（lazy）。你总是有那个分配。如果你从没在vector里放任何东西呢？对吧？这意味着你不用记得去做那件事，而且它是惰性的。你实际上不会得到那个分配，直到你在vector里放东西。你可以用任何模式
reserve，这很好。那让你可以在需要时强制fixed模式分配，就像variable模式一样。但你总是会得到固定的容量大小，而不是你传给reserve的。如果你试图reserve大于它能做的，它会抛出异常。有一个
free()成员函数。我最近才知道人们实际上一直在要求这个。它只是做了clear()然后shrink_to_fit()，所以它实际上释放了块。有一个
isDynamic()成员函数。这告诉你你是在堆上还是在缓冲区里。对于其他模式它不是特别有用，因为它是常数。对它们来说总是一样的。特别地，这不是你用来判断你实际上是否有分配的方法。对于fixed，它总会说true。
好了，快点，因为我们快没时间了，但动机。这里有多样性是现有容器没有的。更重要的是，有灵活性是现有容器没有的。而且你可以调整。所以你可以写你的代码，用这个东西，用某种方式设置它，运行它，看发生了什么，调整它，运行它，看发生了什么。你不需要改变你的代码或妥协你的代码来做那个，因为你不是在稍微不同的 API 和东西之间切换。你只是用一个东西，通过这些调整做同样的事。
它也有一些我们无法对 vector 做的改进，因为前面提到的原因，因为我们不改变已经存在的东西，有很好的理由。比如前端操作。它在所有模式下都有前端操作。当然。确切地说。因为它有误导性。而且，更重要的是，你想要……你想要能在这个上面用 queue。你可以。它和 queue 工作得很好。middle 模式对 queue 来说很棒。它工作得很好，因为它有前端操作。
如果你想在一个 deque 上用 queue，请便。但如果你想让它跑得非常快，或者你想让它本地化，用 sequence。关于 deque 有一个有趣的讽刺，就是那个 map，那个，你知道，实际上是指向块的指针列表的东西，通常被实现为一个双端队列。所以 deque 是用 deque 实现的。你可以用 middle 模式的 sequence，那会很完美。flat_map 和它一起工作。我们知道，我们知道 inplace_vector 和带 SBO 的 vector 有用处。人们一直在呼吁它们。有提案。事实上，我们有了 inplace_vector。现在，我意识到这既是支持也是反对这个提案的论据，但那是另一个故事了。
我有一堆相关演讲的链接，关于 hive，关于 deque，关于 clump，关于 sequence。
这就是我建议你如何为 C++ 及以后选择和使用正确容器的方式。谢谢。
谢谢。谢谢。