c++ - 如何按插入顺序从地图中检索元素？

Question

我有一张地图，其中存储<int, char *>. 现在我想按插入的顺序检索元素。std::map而是返回按键排序的元素。甚至可能吗？

Answer 1

如果您不关心基于的顺序int（IOW 您只需要插入顺序并且您不关心正常的密钥访问），只需将其更改为 a vector<pair<int, char*>>，根据定义按插入顺序排序（假设您只在末尾插入）。

如果你想同时拥有两个索引，你需要，嗯，Boost.MultiIndex或者类似的东西。不过，您可能需要保留一个只会向上计数的单独变量（将是一个稳定的计数器），因为.size()+1只有当您从未从地图中删除任何内容时，您才能将其用作新的“插入时间键”。

Answer 2

现在我想按插入的顺序检索元素。[...] 有可能吗？

不，不与std::map. std::map将元素对插入到已经排序的树结构中（并且在插入操作之后，std::map 无法知道何时添加了每个条目）。

您可以通过多种方式解决此问题：

1. 使用std::vector<std::pair<int,char*>>. 这将起作用，但不提供地图所做的自动排序。

2. 使用 Boost 的东西（@BartekBanachewicz 建议使用 Boost.MultiIndex）

3. 使用两个容器并使它们保持同步：一个带有顺序插入（例如std::vector），另一个带有键索引（例如std::map）。

4. 自己使用/编写自定义容器，以便支持两种类型的索引（按键和插入顺序）。除非您有非常具体的要求并且经常使用它，否则您可能不需要这样做。

Answer 3

几个选项（Bartek 建议的选项除外）：

• 如果您仍然想要基于键的访问，您可以使用映射以及包含所有键的向量，按插入顺序排列。但是，如果您想稍后删除元素，这将变得低效。

• 您可以将链表结构构建到您的值中：而不是值是 char*s，它们是 char* 的结构以及之前和下一个插入的键**；一个单独的变量存储列表的头部和尾部。您需要自己进行簿记，但它可以让您有效地插入和删除。boost.multiindex 或多或少会做什么。

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