最快的队列容器（C++）

Question

我正在使用队列和优先队列，计划快速地处理大量数据。

因此，我希望我的队列和优先队列能够对添加和删除操作进行响应。

使用向量(vector)、列表(list)或双端队列(deque)作为底层容器有什么相对优点呢？

更新： 在撰写本文时，Mike Seymour和Steve Townsend的回答都值得一读。谢谢两位！

- Richard

Answer 1

确保了解选择如何影响性能的唯一方法是在与预期使用情况类似的情况下进行测量。 话虽如此，以下是一些观察结果：

对于std :: queue： - std::deque通常是最佳选择； 它支持所有必要的操作，并随着增长以块状方式分配内存。 - std::list也支持必要的操作，但由于存在更多的内存分配，可能速度较慢； 在特殊情况下，您可以通过从专用对象池中分配来获得良好的结果，但这不完全简单。 - std::vector不能用作它没有pop_front()操作； 这样的操作将很慢，因为它必须移动所有剩余的元素。

一种潜在的更快但不太灵活的替代方案是，在固定大小的数组上实现循环缓冲区（例如std :: array或您不重新调整大小的std :: vector ）。 您需要处理它填满的情况，可以通过报告错误或分配更大的缓冲区并复制所有数据来处理。

对于std::priority_queue： - std::vector通常是最佳选择； 它呈指数增长（减少内存分配的数量），是一个简单的数据结构，非常快速 - 迭代器可以简单地实现为一个包装器，围绕指针。 - std::deque可能会更慢，因为它通常是线性增长的（需要更多的内存分配），而且访问比向量更加复杂。 - std::list不能用作它不提供随机访问。

总之：默认通常是最佳选择，但如果速度真的很重要，那么就测量替代方案。

- Mike Seymour

Answer 2

对于基本队列，我会使用std::queue。它默认是deque的包装器。如果这对您没有用，请使用更专门的内容。

std::priority_queue也存在（默认情况下是在vector上），但由于增加了语义，因此取决于您特定的访问模式的性能观察结果，可能更有可能需要自己编写。

vector具有存储特性，非常不适合从数据集前面进行删除操作。每次pop_front都需要大量重排。对于简单队列，请避免使用。

list可能对于任何高频队列来说都太昂贵，因为按照约定它必须提供您不需要的函数。它可能是用作优先队列的候选项，但我的直觉总是相信STL。

- Steve Townsend

---

我不明白你的第一行是什么意思，Steve。在我的设计中，我必须同时使用队列和优先队列。问题是我应该使用什么底层容器呢？队列默认使用deque。我不确定优先队列是否有默认值，但我目前正在使用vector。 - Richard

@Richard：vector不能用于queue，因为它不提供pop_front()。对于只从容器的后面推入和弹出的priority_queue来说，它是一个很好的选择（也是默认选择）。 - Mike Seymour

@Richard - 就像STL的使用建议一样，我怀疑你不能同时为队列和优先队列使用相同的底层存储来获得最佳结果。这样清楚了吗？ - Steve Townsend

我非常同意，@SteveTownsend。在同一个问题中涉及两种数据结构可能是不太好的风格。 - Richard

你是对的，@SteveTownsend。基于向量的优先队列在添加优先级大于队列中已有元素的元素时似乎非常缓慢。通过识别这些元素并将它们推入FIFO队列，可以使一个算法的速度提高37%。 - Richard

@Richard - 很好。在真实世界的使用模式下进行测量是决定要“修复”什么的最佳方式。 - Steve Townsend

Answer 3

vector 把栈实现为快速插入在末尾，而快速删除也在末尾。如果你想要一个FIFO队列，则使用vector 实现将是错误的选择。 deque 或 list 都提供了常数时间的两端插入。当您想要快速从中间移动元素并且迭代器无论如何都保持有效时，list 对于LRU缓存很好用。当插入和删除都在末尾时，通常会使用deque。

主要需要询问的是您的集合是否被多个线程访问。我认为它们是多线程访问的，因此你的主要目标之一是减少锁定。这可以通过至少拥有一个multi_push和multi_get功能来实现，这样您就可以同时放置多个元素而无需任何锁定。

还有一些无锁容器或半无锁容器可供选择。

只要您的操作都是常数时间，您会发现您的锁定策略比集合本身的任何性能更重要。

- CashCow