最快队列容器（C++）

Question

我正在使用队列和优先级队列，通过这些队列我计划很快地抽取大量数据。

因此，我希望我的q和pq能够对加法和减法做出响应。

使用vector，list或deque作为基础容器的相对优点是什么？

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

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无法使用，因为它不提供随机访问。

总结 - 默认值通常是最好的选择，但如果速度真的很重要，那么测量替代方案。

Answer 2

我会使用std::queue作为您的基本队列，这是（至少默认）在deque上的包装。如果这不适合你，请做更特别的事情。

std::priority_queue也存在（默认情况下超过vector），但添加的语义使它更有可能必须在此处展开​​自己，具体取决于针对特定访问模式观察到的perf。

vector具有存储特性，使其非常不适合从数据集的前面移除。每当你做了大量的洗牌工作，你需要做的事情是pop_front。对于一个简单的队列，避免这一点。

list对于任何高命中的队列来说可能太贵了，因为通过契约它必须提供你不需要的功能。它可以作为优先队列的候选人，但我的直觉总是相信STL。

Answer 3

vector会实现一个堆栈，因为您的快速插入是在最后，快速删除也是在最后。如果你想要一个FIFO队列，vector将是错误的实现使用。

deque或list都提供在任一端的恒定时间插入。 list对于想要将元素从中间快速移出并且希望迭代器保持有效的位置的LRU缓存很有用，无论您将它们移动了多少。通常在插入和删除结束时使用deque。

我需要问你的收藏主要是他们是否被多个线程访问。我认为他们是，在这种情况下，您的主要目标之一是减少锁定。如果你至少有一个multi_push和multi_get特性，这样做可以最好地完成，这样你就可以一次放入多个元素而没有任何锁定。

也有无锁容器或半无锁容器。

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