原文

你好,亲爱的读者!我认为你对c++中的数据结构的性能和使用有很多假设。这篇博客就是我，在摧毁你的世界。

为了充分阅读本文，如果你需要，我建议快速复习一下链表、双端队列、散列表、二叉树、B树和堆。

废话少说，开始毁灭吧!

插入和获取数据

看看下面的程序:

std::vector<std::uint64_t> v;
for(std::uint64_t i = 0; i < 10'000'000; ++i)
{v.push_back(i);
}

你可能会想“这太低效了!”

你认为如果:

• 我们使用std::deque而不是std::vector?
• std::list而不是std::vector?
• std::set?
• std:: unordered_set?

让我们测试一下性能吧!

在Xeon E5-2630 v3上，运行Windows 10，使用VS 2019:

• std::vector:163277
• std::deque: 695,575 us - 4X+慢
• std::list: 1,123,685 us - 9X+较慢
• std::set: 3,043,661 us - 18X+慢
• std::unordered_set: 4,979,332 us - 30X+慢

不过，有一种方法可以让程序运行得更快:

std::vector<std::uint64_t> v;
v.reserve(10'000'000);
for(std::uint64_t i = 0; i < 10'000'000; ++i)
{v.push_back(i);
}

这个实现运行在53185 us (3X+快)。如果你很好奇，保留（reserve ）使得std::unordered_set会把它降到2,545,083 us，使std::unordered_set比std::set快。

在c++中只有一个上帝，它的名字是vector。

为什么?为什么?为什么! !

std::vector的常见分配策略是总是重新分配现有使用量的两倍，快速减少分配的数量(渐近线为O(log n))。对于10M条目，这意味着我们可能做不到25个分配(2^24 = 16,77216)。

即使我们必须在每次重新分配时复制所有内容，数据在内存中是连续的，使复制速度超快(尽管插入新条目，也超快)。如果我们使用push_front, vector就会很糟糕，因为我们必须在每次插入时移动。

std::deque将有10M/size的块分配。std::list每个条目可能至少有一个分配，std::set和std::unordered_set也是如此。std::unordered_set有双重惩罚:需要调整数组的大小 + 分配节点。如果我们保留（reserve ）std::unordered_set，我们就可以战胜std::set。

在此之上，std::vector只需要存储条目，deque需要在每个块之间创建链，在每个条目之间创建列表，set也是如此。unordered_set需要计算每个条目的哈希值，创建节点，并链接到该节点。

你可以使用一个特别的分配器来缓解这些问题，但是你永远无法超越std::vector的原始能力。

如果你对STL容器的基准测试感兴趣，可以参阅更深入的文章

理想的情况

最好记住你的电脑是什么样的(我说的电脑是指硬件+操作系统):

• 连续内存区域可以从缓存中受益，然后是页局部性
• 如果可能的话，一次又一次地敲击同一个记忆区域(持续的记忆会有所帮助)
• 尽可能少的间接
• 尽可能少的分支

对象的大小

应该将对象本身存储在集合中，还是将对象的指针存储在集合中?在我们的示例中，我们使用了一个64位整数(8字节)，随着对象的大小增长，可能会出现性能问题。虽然选择一个不会随着增长而移动对象的容器(例如deque或链表)听起来可能比较有益，但你也可以考虑存储一个指向对象的指针(使用std::unique_ptr)。

什么是最有效的将取决于你确切的用例。

插入

要在内存结构中插入数据，你在开头看到的代码示例非常有效。追加到已存在的内存区域，即刚才写入的区域。页面在内存中是热的，地址在TLB中，缓存可以最优地完成它的工作。

你想要，尽可能地，回到这个例子。这就是为什么插入未排序的数据并对其排序通常比插入已排序的数据更好。

查找

这是理想的入口查找。你可能不喜欢它，但这是最佳性能的样子:

std::vector<std::uint64_t> v;
// stuff
// assuming size_t idx is where your entry is
auto x = v[idx];

到连续存储区域的一个间接方法。如果你最近在邻近的索引中查找一个条目，它就在缓存中。你会尽可能地让自己处于那种情况。

问题是，经常需要搜索条目，因此不知道直接索引。你可能知道线性搜索对于元素数量较少的条目更快(例如在这篇博文中解释的)。

删除

如果你想经常删除元素，vector不是你的好选择，就像在前面插入元素一样，这意味着移动元素。当你想要删除条目时，你可以通过放置一个墓碑（tombstone ）而不是条目来缓解这种情况，但如果你有很多插入和删除操作，这就不适合使用vector。

销毁

你是否应该关心容器的破坏速度?比你想象的更频繁。

例如，为了正确地销毁链表，你必须检查每个节点，并释放它。所以，在调用析构函数的基础上，你必须进行O(n)重分配。另一方面，vector只需要分配一个连续内存区域，因此速度非常快（你仍然需要调用每个项的析构函数）。

如果容器的寿命相对较短(例如，在函数运行期间创建)，那么销毁速度就非常重要。你可以通过延长它们的生命周期(重用相同的容器)或完全使用不同的容器来减轻这种情况。

如果销毁占用了大量时间，你可能需要优化集合中元素的销毁。如果它们有一个重要的析构函数，你可能想看看使用内存竞技场（memory arena）是否有益。

延伸阅读：
内存竞技场（memory arena）就是一个大的、连续的内存块，只分配一次，然后通过分发较小的内存块来手动管理内存。

所有这些的要点通常是在你知道如何使用内存时提高性能。例如，你可能只分配和释放固定大小的块，在这种情况下，你可以编写非常高效的回收算法。通常在使用内存竞技场时，你还可以在使用完后立即释放整个竞技场，而不需要为每个小块单独调用库自由函数。当你有许多小块内存时，这可以显著减少开销。

在使用c++时，需要注意的是，如果你从一个竞技场分配对象，并且想要快速地重新分配整个竞技场，你应该考虑是否需要调用析构函数。如果是这样，这将需要在竞技场内的所有对象上手动调用它们。沿着这些路线，如果你可以只放置POD类型在你的竞技场，你将能够减少分配/回收开销到最小。

简而言之

在做任何事情之前，问自己“我可以不使用一个未排序的vector?”

现在我们解决了这个问题，让我们深入到非平凡的东西，因为，正如你可以猜到的，std::vector并不总是合适的解。

改善向量

你能做的最快的分配是使用堆栈，因为它只需要一个指令，移动堆栈指针。这就是为什么当你知道你的容器有多少条目时，你应该使用std::array而不是std::vector(或者你可以使用C数组，如果你是那种在磁带播放器上听老式嘻哈音乐的人，没有任何评判)。

一旦向量的大小超过堆栈大小的很大比例，或者当你希望移动向量时，这种方法就不那么吸引人了，因为这会妨碍有效的移动语义。

对于这个，你会说，“但是!我不知道我的向量在编译时应该有多大!”

大多数时候，你不会。但是，如果你知道在大多数时候你的向量不会超过特定的大小，那么你可以使用小向量优化。

小向量优化是将对象预先分配给一定数量的对象，并在超过该值时切换到动态内存分配。boost和folly都提供了一个实现(在QuasarDB中，我们使用Boost的实现)。

哈希表

C++ 哈希表实现

哈希表可能是仅次于数组的第二有用的数据结构。它们通过适当的哈希函数提供O(1)查找。C++附带了std::unordered_map和std::unordered_set。如果查找是在关键路径中，那么使用好的散列函数可以极大地受益于散列映射。

也就是说，如果哈希表真的在性能路径中，那么你很快就会发现std::unordered_map不是很好。

这是因为该标准的编写方式使得实现是一个链表数组。这意味着，尽管查找的复杂性是O(1)，但你需要执行多次内存访问(和间接访问)来访问你的条目。当哈希表查找在关键路径时，这可能会导致显著的减速。

这篇精彩的演讲将解释如何构建更好的哈希表。这篇文章展示了现有散列表实现的一个基准。

记住一件重要的事。目前，高效的哈希表实现通常将对象存储在数组中，以节省一个间接操作并提高缓存效率。随着对象的大小增加，将其存储在节点中变得更加有效，从而加快数组的重新排列。据此衡量和决定。

在QuasarDB，我们目前使用:

• tbb::concurrent_hash_map，当需要并发读写时
• 其他情况下为robin_hood::unordered_map
• std::unordered_map在尚未更新的遗留代码中

有效利用哈希表

哈希表最初不是C++标准的一部分，因为它们有一定数量的注意事项。如果你不知道它们，O(1)查找可以变成O(n)查找。

哈希函数的重要性

你的哈希（hash）函数需要快速并提供很大的离散度。碰撞对于散列映射来说是不好的，因为它们强制对每个碰撞进行额外的比较。因此，你希望确保不同的条目具有不同的散列。对于整型，哈希函数很简单。对于字符串，Murmurhash或 Farmhash是很好的。

但是，对于组合类型，有一个问题。

让我们看看这个结构

struct my_struct
{std::string a;std::string b;
};

假设你使用了一个很好的哈希函数，例如farmhash。你可以这样构建一个自定义哈希函数:

template <>
std::hash<my_struct>
{size_t operator()(const my_struct & v) const noexcept{return farmhash::hash(v.a) ^ farmhash::hash(v.b);}
};

你用异或来最大化熵，但有个问题。异或是可交换的，这意味着操作的顺序不会改变结果。此外，如果两个哈希值相等，则该值将为零，从而放大冲突。

换句话说，my_struct{"a", "b"}和my_struct{"b", "a"}将产生相同的哈希值，造成冲突，减慢查找速度。

这就是为什么应该正确地构造哈希函数。例如，可以使用boost::hash_combine()。在QuasarDB中，我们有一个等价的函数，使用constexpr:

template <class Integer>
constexpr std::size_t hash_combine(std::size_t seed, Integer v) noexcept
{return seed ^ ((static_cast<std::size_t>(v) + std::size_t{0x9e3779b9}) + (seed << std::size_t{6}) + (seed >> std::size_t{2}));
}

对于字符串和blob，我们使用farmhash，并为任何其他类型使用自定义hash函数。

储备!
哈希表是一个桶数组，插入新条目，调整这个数组的大小。这就是为什么强烈建议将哈希映射保留到你期望它能够容纳的最大桶数（假设你的哈希函数能够做到这一点:一个桶 = 一个条目）。这样，你就不必在插入新条目时支付重新分配的费用。

什么时候确实需要对数据进行排序

有序还是无序?

有序数据是大量数据处理的必要条件。我总是惊讶于有多少软件工程问题最终归结为排序问题。

需要对数据进行排序的示例:删除集合中的重复数据、数据分析标准(例如，低于/高于…的数据)、基于阈值对数据进行分区，等等。

如果你需要对容器中的数据进行排序，那么尽早确定这一点非常重要，因为排序数据将限制你对数据结构的选择。同样，我们倾向于高估我们对有序数据的需求。当需要对数据进行排序时，对其进行排序可能比一直保持其排序更有效。

我的建议是:

• 确保临时排序并不适合你的情况
• 如果这还不够，那么对于你的用例来说，堆可能是一种很好的数据结构
• 对于单一性问题，考虑一个哈希表
• 该死的!看起来你确实需要一个排序的数据容器

std::map，平均执行者

在c++ 11之前，唯一可用的“官方”关联容器是std::map，它是有序的。如果需要对数据进行排序，可以使用std::map或std::set。但是，只有在有序数据足以解决问题(性能或其他)时，才应该使用它们。

这些容器实现为二叉树，因此在每次插入时都需要分配一个节点，并且具有非常不友好的缓存查找。

公平地说，std::map有一个稳固的优势:它在所有方面都表现不错。它没有std::unordered_map所具有的警告。对于std::multimap，你可以拥有具有类似键的条目，这非常有用。由于C++ 17，你还可以提取节点，将它们附加到另一个std::map，从而可以构建临时映射并合并它们。

那么，你应该使用std::map吗?

是的，如果:

• 代码不是性能关键的，你需要一个排序的容器
• 你不希望依赖于第三方库

如果是其他情况，请继续阅读。

排序向量

我最喜欢的结构是排序向量。Boost有flat_map和flat_set(以及flat_multimap和flat_multiset)。

一个排序的向量是如何工作的?与将项目存储在二叉树的节点上不同(与映射不同)，这些项目存储在一个向量中，并根据预定义的标准进行排序。查找是使用复杂度为O(log n)的二进制搜索来执行的。

理论上，排序向量和二叉树的速度一样快，实际上可能更快，因为:

• 内存是连续的，这使得结构对缓存非常友好。
• 销毁容器几乎没有任何开销(与需要删除每个节点的映射相反)
• 你可以在一个向量中插入n个元素，然后对这个向量排序，而不是做n个排序的插入
• 你可以给出插入提示，例如，当你知道你从一个排序源插入时，它从O(log n)插入移动到O(1)
• 你可以预先分配你的排序向量

换句话说，排序后的向量可以将你带回我们在顶部描述的理想插入用例。

根据我的经验，一个有序的向量只是压缩了一棵二叉树。大多数时候……

问题是什么?

问题是，如果你不能插入(几乎)有序的数据，并且不能缓冲插入，那么每次插入都将迫使你移动现有的条目，从而导致糟糕的插入性能。

但不用担心，因为我们可以做得更好。

B树

二叉树的问题是一个元素与树下的另外两个元素相连接。这意味着每个条目对应一个节点: 每次插入一个分配，糟糕的局域性。如果使用B-Tree而不是二叉树，则每个节点可以有几个子节点，从而最小化开销，并使数据结构对缓存更加友好。

谷歌的Abseil有一个很好的兼容c++ 17的B-Tree实现。

在QuasarDB，我们是排序向量的忠实粉丝，并广泛地使用它们。我们目前没有使用B-Tree，因为我们还没有遇到过用已排序的向量或未排序的数据结构都无法解决的情况。

我们没有谈论过的结构

在这篇文章的开头，我们似乎已经摧毁了std::list和std::deque。不要被这个基准愚弄了，这些结构非常有用。

展示他们应得的爱

当你在编程方面有了更多的经验后，你可能会和本文一样认为链表是无用的。

他们不是。一旦你理解了链表隐藏的强大功能，它就是一种非常有用的数据结构: 除了指向已删除元素的迭代器外，链表永远不会使迭代器失效。

因此，你可以安全地使用迭代器作为现有对象的代理，例如，链表成为LRU缓存的一个很好的数据结构(通常实现为哈希映射+链表)。相信我，随着软件项目的发展，这个项目至少有一个缓存的概率收敛为1。

list是一个双链表，这意味着每个元素都指向它的前身和继承者。如果只需要在单个方向遍历列表，可以使用std::list。

什么时候使用deque?

我们在基准测试中看到，vector在末尾插入时的性能优于deque。而你认为deque是最适合这种情况的!

不完全是。当你需要在容器的末尾和开头插入(或删除)时，deque非常有用。另外，当只在开始和结束插入时，deque不会使迭代器失效。

尽管deque为访问提供了O(1)渐近性能，但大约比std::vector低两倍，因为每次访问都需要两个指针解引用，而不是一个。

但是记住，在任何事情上都很难打败vector。这是C++的标准普尔500指数。

你可以从中推断出指导方针

那么结论是什么呢?

• 默认为std::vector，如果你能在编译时知道大小，使用std::array
• 如果真的需要对数据进行排序，可以使用排序向量或 B-Tree
• 如果需要快速查找，可以使用哈希表，但要避开哈希函数和std::unordered_map的限制

作为额外的奖励，这是我们在 QuasarDB 使用的决策图。它是不完整的(它不可能是)，因为它不包括非常特殊的情况，你可能想要链表，deque，前缀树，等等。

目标是用正确的问题帮助你走在正确的方向上。

像往常一样:猜想，测量，推断，决定!

就在最近，我花了很多时间尝试并击败(我自己的)基于节点向量(vector of nodes)的ustrings实现。其中节点是hash + uniq_ptr…包括一些众所周知的C库，它们是最快的解决方案。那真是个惊喜。
其余的在这里:https://github.com/dbj-data/dbj-bench/tree/master/source/benches/string_pool_comparing