最快队列容器(C++)

Question

我使用队列和优先级队列，通过队列，我计划非常快地抽取大量数据。

因此，我希望我的Q和pq对加减法的反应。

使用向量、列表或deque作为底层容器的相对优点是什么？

更新：在撰写本文时，迈克·西摩和史蒂夫·汤森的答案都值得一读。谢谢你俩！

Answer 1

确定选择如何影响性能的唯一方法是在类似于预期用例的情况下测量性能。尽管如此，以下是一些观察结果：

对于std::queue

• std::deque通常是最好的选择；它支持在恒定时间内进行所有必要的操作，并以块的形式分配内存，因为grows.
• std::list也支持必要的操作，但由于内存分配的增加，它可能会慢一些；在特殊情况下，您可能可以通过从专用对象池中分配来获得良好的结果，但这并不完全是straightforward.
• std::vector，因为它没有pop_front()操作；这样的操作会很慢，因为它必须移动所有剩余的元素。

另一种可能更快但不太灵活的方法是在固定大小的数组(例如std::array或不调整大小的std::vector )上实现循环缓冲区。您需要通过报告错误或分配更大的缓冲区并复制所有数据来处理填充的情况。

对于std::priority_queue

• std::vector通常是最好的选择；它以指数方式增长(减少内存分配数)，并且是一种简单的数据结构，访问速度非常快--迭代器可以简单地实现为pointer.
• std::deque的包装器，因为它通常是线性增长的(需要更多的内存分配)，而且访问比vector.
• 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特性，以便一次可以放置多个元素而不进行任何锁定，这是最好的方法。

也有无锁集装箱或半无锁集装箱。

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