C++ boost - 是否有一個容器像直接訪問密鑰一樣工作？

Question

我很想知道一個類似隊列的容器，但它具有密鑰訪問權限，就像地圖一樣。我的目標很簡單：我想要一個FIFO隊列，但是，如果我插入一個元素並且具有給定鍵的元素已經在隊列中，我希望它將的新元素替換爲已經在隊列中的元素。例如，按插入時間排序的地圖可能會起作用。

如果沒有這樣的容器，你認爲它可以通過使用隊列和地圖來實現嗎？

Answer 1

Boost multi-index提供這種容器。

要自己實現它，我可能會去尋找一個map，它的值由一個鏈表節點和一個有效載荷組成。列表節點可以是手動滾動的，或者可以是Boost intrusive。

請注意，queue適配器的主要目的是隱藏序列的大部分界面，但是您想混淆它隱藏的細節。所以我認爲你應該瞄準重現queue的接口（稍微修改push的變化語義），而不是實際使用它。

Answer 2

我看到使用隊列和可選地圖進行此操作的簡單方法。

爲您的元素定義某種==運算符。

然後，只要有一個隊列，並且每次要插入它時都搜索元素。

您可以通過將元素位置映射到元素而不是每次搜索隊列來優化此操作。

Answer 3

很顯然，您只需使用類似隊列的容器即可完成，但您必須在每次插入時花費O(n)時間來確定元素是否已存在。如果基於std::vector之類的東西來實現您的隊列，則可以使用二分法搜索並基本上將您的插入速度提高至O(log n)（在內存重新分配完成後，仍然需要O(n)操作）。

如果這沒問題，只要堅持下去。帶有額外容器的變體可能會提升性能，但它也可能容易出錯，如果第一個解決方案足夠，就使用它。

---

在您可能要兩次存儲你的元素在不同的容器中的第二個方案 - 原隊列，像一張地圖（或有時的HashMap效果會比較好）。地圖僅用於確定元素是否已經存在於容器中 - 如果是，則必須在隊列中更新它。

基本上爲我們提供了O(1)的HashMap中查找複雜性（在現實世界中，這可能是因爲碰撞變得更醜 - 包含HashMap是不是確定元素存在確實不錯）和O(1)插入時間的情況下，當沒有更新需要和O(n)需要更新案例的插入時間。

根據實際更新操作的百分比，實際插入性能可能會從O(1)到O(n)不等，但如果更新數足夠小，此方案肯定會優於第一個。

不過，你必須同時在兩個容器中插入你的元素，如果元素被刪除，應該做同樣的事情，我會考慮兩次「我真的需要提高性能嗎？」。