views:

173

answers:

3

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  A: 

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.

Gorpik
I think my example was not clear enough. Lets say I have class person which has various attributes such as age, name etc. Now lets a I have many person objects and want to create multiset of persons sorted on age. I believe this is a genuine requirement. My question is if the two persons have same age is their order guaranteed as the input order?
Naveen
The predicate supplied to the multiset only requires that there be a partial ordering. If `a1 < a2` and `a2 < a1` both evaluate to false, that does not indicate that `a1 == a2` would evaluate to true. The objects `a1` and `a2` are equivalent but are not necessarily equal.
Matthew T. Staebler
@Naveen: As GMan has explained in his answer, this is guaranteed only from C++0x forward (I did not know they had introduced this guarantee, by the way; since this standard is not yet published, currently it is not guaranteed).
Gorpik
@Aeth: Yes, you are right. But usually (emphasis on "usually") it is not a good idea to have a class where all operators <, > and == return false for two valid objects. Sooner or later, this will lead to unexpected behaviour when somebody tries to use your class in a way you did not expect.
Gorpik
@Gorpik: I concur whole-heartedly with what you are saying about the comparison and equality operators. The OP has not stated, though, whether the greater-than and equality operators have even been defined for his types. For his example with people and their ages, I would not even use a less-than operator. It seems as though the operator method was defined solely for use with the multiset. I would prefer to define a different method such as `is_younger` and use that as the predicate for the multiset. That way there is less confusion about the meaning of the method.
Matthew T. Staebler
@Aeth: Indeed, using a predicate is the right thing here. In this case, I agree with anything else you said.
Gorpik
+9  A: 

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. :/

GMan
Not using multiset either. `std::map<A, std::vector<A> >` would be my best bet at the moment...
Matthieu M.
@Matt: Yea, it's too bad to get the behavior you'd have to basically do multiset by hand :/
GMan
A: 

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;
    }
}
Danvil