STL set not sorted as expected

Question

I have a class which contains members A, B, and C, and I want objects of this class stored in a set, where the ABC triplet is known to be unique, and should be the set key. However, the set ordering does not end up as expected.

My comparison functor is:

class MyClassLess { public: bool operator() (const MyClass& t1, const MyClass& t2) const { if(t1.getA() < t2.getA()) return true; if(t1.getB() < t2.getB()) return true; return t1.getC() < t2.getC(); } }; typedef set<MyClass, MyClassLess> SetMyClass;

I expected elements in the set to be sorted first by A, and then by B, and finally by C. However, if I iterate through the set from begin to end, the sort order turns out to be:

B
C
A

In other words, I get a group of members which all have a specific value of B, and within that group I see all values of C, and for each value of C I then get all values of A.

Any idea what's going on here?

Stop using a computer. Take out a pen and paper, and work out in detail whether your "ordering" makes sense. — Kerrek SB
– Kerrek SB, Commented Oct 4, 2013 at 8:36

sbi · Accepted Answer · 2013-10-04 08:42:36Z

Your comparison function is wrong. Here's a version that should work:

class MyClassLess { public: bool operator()(const MyClass& t1, const MyClass& t2) const { if(t1.getA() < t2.getA()) return true; if(t1.getA() > t2.getA()) return false; if(t1.getB() < t2.getB()) return true; if(t1.getB() > t2.getB()) return false; return t1.getC() < t2.getC(); } };

You algorithm needs to return false the moment either A or B of the left side are smaller than the corresponding member on the right side.

Perhaps std::tie(t1.getA(), t1.getB(), t1.getC()) < std::tie(t2.getA(), t2.getB(), t2.getC())?
OK, done :-) I still hope that the real message is that it's important to understand the maths before one starts to write code...
@Kerrek: Done, too. You answer's message, though, is to know the right std lib feature and forget about the math. (Not that I would look down on that. If you use std lib algorithms rather than writing your own, you can't put bugs into them.)

Kerrek SB · Accepted Answer · 2013-10-04 10:35:04Z

If you just want a correct implementation of a comparison of a tuple of values, just use the comparison of standard-library tuples. You can create tuple of references using std::tie, so your comparator is simply:

#include <tuple> // ... bool operator() (const MyClass& t1, const MyClass& t2) const { return std::tie(t1.getA(), t1.getB(), t1.getC()) < std::tie(t2.getA(), t2.getB(), t2.getC()); }

However, you must still make sure what it actually means to compare a tuple of values. (Tip: Think "dictionary".)

Collectives™ on Stack Overflow

STL set not sorted as expected

2 Answers 2

3 Comments

Comments

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

3 Comments

Comments

Related