logo标签列表

STL的multimap如何在插入时遵守排序规则？

c++multimap
23

我有一些数据，带有整数索引。我在持续生成新的数据并将其按照该索引添加到我拥有的数据集中，同时我想轻松地回到数据的起点并遍历它。听起来像是std::multimap正是我所需要的。

然而，我还需要保留具有相同索引的数据以插入顺序排序。在这种情况下，当我遍历数据时，我会先看到早期的数据，然后才是后面的数据。

multimap能做到这一点吗？

我没有找到这种情况的任何保证。在sgi手册中，我没有看到任何提及这一点的内容。我在gcc 4.3.4实现上进行了一些有限的测试，似乎对某些测试用例是正确的，但是我想知道标准是否要求这一点，我可以依赖这个事实。

编辑: 为了回应一些答案更加清晰，我希望首先按（非唯一）索引进行排序，其次是按插入时间排序。我曾希望第二部分与multimap一起自动完成，但似乎并不是。

7个回答
46

看起来新标准(C++11)改变了这一点：

键值对的顺序与插入的顺序相同，且不会更改，即使它们的键相当。[cppreference]

虽然如此，我还在犹豫是否使用它，因为这似乎是一个细节，容易被忽视，并且如果编译器的库未正确实现，这种细节将悄无声息地导致错误。

4
好的，不过你可以在实现中查看它，并非不能检查。 - Matthieu M.
8

除非我漏掉了什么，标准并不提供任何这样的保证。

最明显的解决方法是将序列号作为次要关键字进行包含。例如，在您的类中包含一个静态无符号长整型，并且每次创建一个要插入到multimap中的对象时，将其当前值放入您的对象中并递增它。在您对象的比较函数中，如果您当前使用的数据相等，则使用该计数器作为决定因素进行排序。请注意，在这种情况下，每个键都将是唯一的，因此您可以使用map而不是multimap。

4
有没有示例？ - Hermes
3
如果我理解正确的话，你需要按某个键对数据进行排序。每当您插入两个具有相同键的项目时，您需要以插入顺序检索它们。
如果是这种情况，那么您必须查看multimap的实现方式。根据它如何处理多次插入具有相同键的情况，它可能会或可能不会拥有此保证。我猜想标准没有提供这种保证，因为它会限制非常特殊的情况的实现。
另一种方法是使用Map（而不是Multi）并创建一个复合键。该键由您选择的普通键和始终递增的计数器组成。在比较时，当键相等时，插入号使键唯一。这样，您可以强制使用唯一键和相等的“正常”键的顺序（我希望这是可理解的）。
我想最后一种方法是最容易实现的。
选项：（不建议）
您始终可以选择具有此保证的自制数据结构。我会选择带有向量以保存插入的数据的树（例如红黑树或AVL）。在迭代时，您必须找到节点，转到向量并迭代其内容。每当您完成向量时，您就会继续下一个节点。
1

听起来multimap是你需要的...

然而，我还需要保持具有相同索引的数据按照插入顺序排序，这意味着当我遍历数据时，我会先得到早期数据，然后才是后期数据。

它将按照索引顺序排列。如果随着插入更多项，索引随时间增加，则是的，由于索引的性质，“早期”数据将首先出现。

否则，不行。您可以将两个multimap保留到相同的数据。一个按索引顺序排序，另一个按插入时间排序：

std::multimap<index, T*> orderedByIndex;
std::multimap<time, T*> orderedByInsertionTime;

给予您能够双向迭代映射的能力。
（编辑：我理解为您有时想按索引迭代，有时想按插入时间迭代，但如果您是指先按索引再按插入时间，请参见上面的答案。）
1
不会的。如果你想要那样做，你应该使用一个“序列容器”比如vector。你可以用std::pairs来加载一个vector。
1

当你检索信息时，属于相同关键字的元素将通过lower_bound和upper_bound函数排序，因此你不能保证通过equal_range访问到的元素是按照插入顺序排列的。

网页内容由stack overflow 提供, 点击上面的
可以查看英文原文，
原文链接