最快隊列容器（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特性，這樣做可以最好地完成，這樣你就可以一次放入多個元素而沒有任何鎖定。

也有無鎖容器或半無鎖容器。

只要您的操作都是恆定時間的，您可能會發現您的鎖定策略比集合本身中的任何性能更重要。