如何按照插入順序從地圖中檢索元素？

Question

我有一個地圖存儲<int, char *>。現在我想按照它們插入的順序檢索元素。代替std::map返回按鍵排序的元素。它甚至有可能嗎？

Answer 1

如果您不關心基於int（IOW，您只需要插入順序，並且您不關心正常密鑰訪問）的訂單，只需將其更改爲vector<pair<int, char*>>，按照定義，插入順序（假設您只在最後插入）。

如果你想同時有兩個索引，你需要，好吧，Boost.MultiIndex或類似的東西。但是，您可能需要保留一個單獨的變量，只會向上計數（將會是一個穩定的計數器），因爲只有在您從未從地圖中刪除任何東西時，纔可以使用.size()+1作爲新的「插入時間鍵」。

Answer 2

幾個選項（比那些鮑爾泰克建議等）：

• 如果仍要基於密鑰的訪問，你可以使用地圖，使用包含所有密鑰的載體一起，在廣告訂單。不過，如果您稍後想要刪除元素，這會變得效率低下。

• 你可以在你的值中建立一個鏈表結構：而不是char *的值，它們是一個char *的結構，以及之前和下一個插入的鍵**;一個單獨的變量存儲列表的頭部和尾部。你需要自己做記賬，但它可以讓你有效地插入和刪除。這或多或少是boost.multiindex會做的。

**這將是很好的存儲映射迭代器，但這會導致循環定義問題。

Answer 3

現在我想檢索他們已經插入的順序的元素。 [...]它甚至有可能嗎？

不，不是std::map。 std::map將元素對插入已經排序的樹結構中（並且在插入操作之後，std :: map無法知道每個條目何時添加）。

您可以通過多種方式解決這個問題：

1. 使用std::vector<std::pair<int,char*>>。這會起作用，但不能提供地圖所做的自動排序。

2. 使用升壓東西（@BartekBanachewicz建議Boost.MultiIndex的）

3. 使用兩個容器，並保持同步：一個帶有順序插入（例如std::vector）和一個與索引由鍵（例如std::map）。

4. 自己使用/寫入自定義容器，以便支持這兩種類型的索引（按鍵和插入順序）。除非你有非常明確的要求，並且使用了很多，否則你可能不需要這樣做。