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?
views:
173answers:
3Taking 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.
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. :/
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;
}
}