Does std::multiset guarantee insertion order?

2019-01-24 05:26发布

I have a std::multiset which stores elements of class A. I have provided my own implementation of operator< for this class. My question is if I insert two equivalent objects into this multiset is their order guaranteed? For example, first I insert a object a1 into the set and then I insert an equivalent object a2 into this set. Can I expect the a1 to come before a2 when I iterate through the set? If no, is there any way to achieve this using multiset?

3条回答
Root(大扎)
2楼-- · 2019-01-24 05:41

In C++03 you are not guaranteed that insert and erase preserve relative ordering. However, this is changed in C++0x:

n3092, §23.2.4/4: An associative container supports unique keys if it may contain at most one element for each key. Otherwise, it supports equivalent keys. The set and map classes support unique keys; the multiset and multimap classes support equivalent keys. For multiset and multimap, insert and erase preserve the relative ordering of equivalent elements. Emphasis mine.

This is discussed in this defect report. This page is the collection of comments on the issue, it's well-written and quite fleshed-out. (I very much recommend reading this one over the previous "overview" link.)

From that comment page you'll find a comparison of current implementations, so you can check if the implementations you intend to use follow what you expect.

I can't think of a way to force the ordering you want off the top of my head. :/

查看更多
聊天终结者
3楼-- · 2019-01-24 05:47

Taking into account that a1 and a2 would compare equal in your example, and what is actually stored in the std::multiset are copies of a1 and a2, I don't really know how would you know which is which.

If you can tell the difference, maybe class A was not well designed in the first place. So std::multiset does not guarantee such a thing.

混吃等死
4楼-- · 2019-01-24 05:48

std::multimap does not guarante this. If you can express your operator< using an integer via a function e.g. int A::orderingInt(), you could use a

std::multiset<MyCustom> myset;

with

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

with overloaded

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

Of course adding and iteration would be different now:

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;
    }
}
查看更多
登录 后发表回答