stl 的多重映射如何插入尊重顺序？
我有一些带有整数索引的数据。我不断生成新数据，需要将其添加到我拥有的数据集合中，并按该索引排序，同时我希望能够轻松地转到数据的开头并迭代它。这听起来像 std::multimap 正是我所需要的。
但是，我还需要具有相同索引的数据按照插入的顺序保留，在这种情况下，这意味着当我迭代数据时，我会在稍后的数据之前获取较早的数据。
多图可以做到这一点吗？
我没有找到任何保证可以证明情况确实如此。在sgi手册中，我没有看到任何提及是否。我在 gcc 4.3.4 实现上进行了尝试，对于一些有限的测试用例来说似乎是正确的，但当然我想知道标准是否要求这样做，我可以依赖这个事实。
编辑：为了更清楚地响应某些答案，我希望数据首先按（非唯一）索引排序，然后按插入时间排序。我曾希望第二部分可以免费提供多重地图，但似乎事实并非如此。
I have some data which come with a integer index. I am continuous generating new data which needs to added to the collection of data I have, sorted by that index, at the same time I want to easily be able to go the start of the data and iterate through it. This sounds like std::multimap is just what I need.
However, I also need data with the same index to be kept in the order in which it was inserted, in this case meaning that when I iterate through the data I get to the earlier data before the later data.
Does multimap do this?
I haven't found any guarantees that this is the case. In the sgi manual, I didn't see any mention of whether. I tried it on gcc 4.3.4 implementation and it seemed to be true for some limited test cases, but of course I was wondering whether the standard demands this and I can rely on this fact.
Edit: To be clearer in response to some of the answers, I wanted the data sorted first by (non-unique) index and second by insertion time. I had hoped that maybe the second part came for free with multimap, but it seems like it doesn't.
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（7）
新标准（C++11）似乎改变了这一点：
不过，我很犹豫是否要使用它，因为在修改标准库以使其兼容 C++11 时，这似乎是一个很容易被忽视的细节，而且这种细节会默默地导致错误如果您的编译器库未能正确实现。
It seems the new standard (C++11) changed this:
I'm hesitating to use it though, as this seems like a detail easily overlooked when modifying the standard library to be C++11 compliant and it's the sort of detail that will silently cause errors if your compiler's library failed to implement properly.
除非我错过了什么，否则该标准不提供任何此类保证。
最明显的解决方法是包含序列号作为辅助密钥。例如，在您的类中包含一个静态 unsigned long，并且每次创建要插入多重映射中的对象时，将其当前值放入您的对象中，然后递增它。在对象的比较函数中，如果当前用作键的数据比较相等，则使用该计数器作为排序的决定因素。请注意，在这种情况下，每个键都是唯一的，因此您可以使用映射而不是多重映射。
Unless I've missed something, the standard doesn't provide any such guarantee.
The most obvious workaround would be to include a sequence number as a secondary key. For example, in your class include a static unsigned long, and each time you create an object to insert in the multimap, put its current value into your object, and increment it. In your object's comparison function, use that counter as the deciding factor for ordering if the data you're currently using as the key compares equal. Note that in this case, each key will be unique, so you can use a map instead of a multimap.
Boost multi_index 支持您想要的内容如果您不想采用
Boost multi_index supports what you are trying to do, if you don't want to take the workaround given by Jerry Coffin.
如果我没猜错的话 - 你需要按某个键排序的数据。每当你插入两个具有相同键的东西时，你需要按照插入的顺序检索它们。
如果是这种情况，那么您必须查看多重映射的实现。根据它如何处理使用相同密钥进行多次插入的情况，它可能有也可能没有这种保证。我想该标准没有提供这种保证，因为它会限制非常特殊情况的实现。
另一种方法是使用 Map（而不是 Multi）并创建复合键。该密钥由您选择的普通密钥和一个始终递增的计数器组成。相比之下，对于相同的键，插入编号使键唯一。通过这种方式，您可以强制使用唯一的键和相同的“正常”键上的顺序（我希望这是可以理解的）。
我想最后一种方法是最容易实现的。
选项：（不推荐）
有了这个保证，你总是可以选择自制的数据结构。我会选择一棵树（例如红黑树或 AVL），并用向量来保存插入的数据。在迭代时，您必须找到节点，转到向量并迭代其内容。每当你完成向量时，你就继续下一个节点。
If I got you right - you need the data sorted by some key. Whenever you insert 2 things with the same key, you need to retrieve them in the order of insertion.
If that's the case, then you have to take a look at the implementation of your multimap. Depending on how it handles the case of multiple insertions with the same key it may or may not have this guarantee. I guess the standard does not offer this kind of guarantee, since it would limit the implementation for a very special case.
Another approach is to go for a Map (not Multi) and create a compound key. The key consists of the normal key you choose and an alway increasing counter. On comparison, with equal keys, the insertion number makes the key unique. This way you force unique keys and the order on equal "normal" keys (I hope this was understandable).
I guess the last approach is the easiest to implement.
Option: (not preferable)
You can always go for a self-made datastructure with this guarantee. I'd go for a Tree (Red-Black or AVL for example) with a vector to hold the inserted data. On iteration you have to find the node, go to the vector and iterate on it's content. Whenever you finish with the vector, you continue with the next node.
不，不会。如果你想要这样，你应该使用像向量这样的“序列容器”。例如，您可以使用 std::pairs 加载向量？
No it won't. If you want that, you should use a "sequence container" like a vector. You can load a vector with std::pairs for example?
听起来多重地图就是你所需要的......
它将按照索引的顺序排列。如果随着您插入更多项目，索引随着时间的推移而增加，那么是的，由于索引的性质，“较早”的数据将首先出现。
否则，不行。您可以将两个多重映射保留到相同的数据。一个按索引顺序排列，另一个按插入时间顺序排列：
使您能够以两种方式迭代映射。
（编辑我读到这个意味着你有时想按索引迭代，有时按插入时间迭代，但如果你的意思是第一个索引然后是插入时间，请参阅上面的答案。）
It sounds like multimap is what you need...
It will be in the order of the index. If the index increases over time as you insert more items, then yes because of the nature of your index, the "earlier" data will come first.
Otherwise, no. You could keep two multimaps to the same data. One kept in order of index, the other in order of insertion time:
Giving you the ability to iterate the map both ways.
(Edit I'm reading this to mean you want to sometimes iterate by index or sometimes iterate by insertion time, but see the above answer if you mean first index then insertion time.)
属于同一键的元素按 lower_bound 和 upper_bound 在您检索信息时起作用，因此您不能保证您将按照元素的顺序访问（通过 equal_range）元素插入。
The elements that belongs to the same key is ordened by lower_bound and upper_bound functions when you retrieve the information, therefore you don't have the guarantee that you will access (by equal_range) the elements in the order that they were inserted.