如何按插入顺序从映射中检索元素？

Question

我有一个存储<int, char *>的映射表。现在我想按照它们插入的顺序检索元素。但是std :: map返回按键排序的元素。这是否可能？

- rahul.deshmukhpatil

Answer 1

如果你不关心基于int的顺序（也就是说，你只需要插入顺序，而不关心常规键访问），那么将其更改为一个vector<pair<int, char *>>即可，按照定义它是按插入顺序排序的（假设你只在末尾插入）。

如果您想同时拥有两个索引，则需要使用Boost.MultiIndex或类似工具。但你可能需要保持单独的变量，它只会向上计数（成为稳定计数器），因为如果您从map中删除了任何内容，您可以仅在您从未从map中删除任何内容时使用.size()+1 作为新的“插入时间键”。

- Bartek Banachewicz

Answer 2

现在我想按照它们被插入的顺序检索元素。...这可能吗？ 不，使用std :: map不行。 std :: map将元素对插入到已排序的树结构中（插入操作后，std :: map无法知道每个条目何时添加）。 您可以通过多种方式解决此问题： 1.使用std :: vector >。这将起作用，但不提供地图自动排序。 2.使用Boost工具（@BartekBanachewicz建议使用Boost.MultiIndex） 3.使用两个容器并使它们保持同步：一个顺序插入（例如std :: vector），一个按键索引（例如std :: map）。 4.使用/编写自定义容器，以便支持两种类型的索引（按键和插入顺序）。除非您有非常特定的要求并且经常使用此功能，否则您可能不需要这样做。

- utnapistim

Answer 3

除了Bartek提出的建议之外，还有几个选项：

• 如果您仍然想要基于键值的访问，可以使用一个映射（map），以及一个按插入顺序包含所有键的向量（vector）。但如果后续需要删除元素，则效率会变低。

• 您可以将链接列表结构构建到值中：值不再是char*，而是由char*和先前插入的和后续插入的键组成的结构体；另外一个变量存储列表的头和尾。您需要自己进行簿记，但它可以提供高效的插入和删除。这或多或少是boost.multiindex所做的。

**最好存储映射迭代器，但这会导致循环定义问题。

- Sneftel