c++ - std::multiset 是否保证插入顺序？

Question

我有一个std::multiset存储class A. 我已经operator<为这个类提供了我自己的实现。我的问题是，如果我在这个多重集中插入​​两个等效对象，它们的顺序是否得到保证？例如，首先我将一个对象a1插入到集合中，然后将一个等效对象a2插入到该集合中。当我遍历集合时，我可以期待a1之前出现吗？a2如果没有，有什么方法可以使用 multiset 来实现吗？

Answer 1

在 C++03 中，您不能保证insert并erase保留相对排序。然而，这在 C++0x 中有所改变：

n3092, §23.2.4/4：如果关联容器对于每个键最多包含一个元素，则它支持唯一键。否则，它支持等效键。set 和 map 类支持唯一键；multiset 和 multimap 类支持等效键。对于多重集和多重映射，插入和擦除保留等效元素的相对顺序。 _{强调我的。}

这在此缺陷报告中进行了讨论。这个页面是关于这个问题的评论的集合，它写得很好，也很充实。（我非常推荐在之前的“概述”链接中阅读这篇文章。）

在该评论页面中，您将找到当前实现的比较，因此您可以检查您打算使用的实现是否符合您的期望。

我想不出一种方法来强迫你想要的顺序从我的脑海中消失。：/

Answer 2

考虑到a1anda2在您的示例中比较相等，以及实际存储在andstd::multiset的副本中的内容，我真的不知道您怎么知道哪个是哪个。a1a2

如果您能分辨出区别，那可能class A一开始就设计得不好。所以std::multiset不保证这样的事情。

Answer 3

std::multimap 不保证这一点。如果您可以operator<通过函数来​​表达您使用整数，例如int A::orderingInt()，您可以使用

std::multiset<MyCustom> myset;

和

class MyCustom : public std::vector<A> {}

有重载

bool operator<(const MyCustom& a, const MyCustom& b) {
   // theoretically empty MyCustom should not occure
   return a[0].orderingInt() < b[0].orderingInt();
}

当然现在添加和迭代会有所不同：

A a;
myset[a.orderingInt()].push_back(a);

// groups with "small" elements first
for(std::multiset<MyCustom>::iterator it=myset.begin(); it!=myset.end(); it++) {
    // those elements are "equal"
    for(std::vector<A>::iterator jt=it->begin(); jt->end(); jt++) { 
         // use A& a = *jt;
    }
}