3

Suppose a class has multiple members relevant to the objects' order, e.g., A { T1 x; T2 y; };. The standard implementation of operator< I know is

bool A::operator<(const A& a) { return x < a.x || (x == a.x && y < a.y); }

But that looks horribly inefficient to me, especially when T1 is std::vector. (It's even inefficient to read and maintain when there are more members.)

Is there a "standard" C++-way of comparing things efficiently? Or does everyone go her own way like so:

enum Cmp = {LESS,EQUAL,GREATER} Cmp A::CompareTo(const A& a) { const Cmp c1 = x.CompareTo(a.x); if (c1 != EQUAL) return c1; const Cmp c2 = y.CompareTo(a.y); return c2; }

And for std::vector one would perhaps use std::mismatch to implement such a CompareTo?

(I'm sure that's not a new question, but operator< is a bad search term.)

Improve this question
10
  • Have you actually measured to determine that it is inefficient? Commented Nov 13, 2014 at 21:43
  • 2
    The best thing you can do is compare the fields that are most likely to vary first. You may have to do some profiling and analysis to determine this for complex data sets. Also for fields that may have more expensive comparisons (e.g. strings or other objects), prefer to compare them last. Profiling will help identify bottlenecks here as well. Of course, ordering constraints may limit your options. However, be sure your operator < is actually a relevant bottleneck before you go optimizing it; the best way to implement it is the way that is clearest and easily maintainable as possible. Commented Nov 13, 2014 at 21:43
  • @TimoGeusch: Reading all 10000 elements of both vectors twice, because they are equal? Sure that's inefficient. Commented Nov 13, 2014 at 21:48
  • @JasonC I don't think that's a solution. (1) There may be an order to that class which operator< should respect. (2) The "standard" way to implement operator< isn't even very maintainable, I think, compared to the second solution. (You disagree?) In general I of course agree to first profile and then optimize. Commented Nov 13, 2014 at 22:04
  • @chs Why do you think the first is the "standard" way? The standard way, if some exists, is using ties (see my answer), at least since 2011. Commented Nov 13, 2014 at 22:06

1 Answer 1

Reset to default
6

If your type has two (or more) members, which should be compared lexicographically, you typically already have an order in your mind in which the members should be compared (i.e. their "priority", for example first the "last name" then the "first name" for sorting persons in an address list).

  • If you have such a fixed order, you have to check them in this order (the other members aren't of any interest if the first are not equal, so you first need to compare the first member).

  • If you don't need a specific order, then choose some efficient order: put those members first which are fast to compare, and put the slow ones at the end, e.g. the vectors.

Then, after you found the "efficient" order of your members (here, let's say x and y), to lexicographically compare two objects, use a tuple constructed with std::tie, which is easily extendable to more than two members. And please overload the operator as a non-member.

bool operator<(const A& a, const A& b) { return std::tie(a.x, a.y) < std::tie(b.x, b.y); }

If you're stuck with a pre-C++11 compiler (or one that doesn't support tuples), you can use boost's equivalent.

Improve this answer
Sign up to request clarification or add additional context in comments.

4 Comments

Ties are very clean. I think this answer could benefit if you elaborate more on how their usage, compared to the OP's example, is related to "efficiency", though, since that was the root of the question (as I read it anyways).
I was taking about the efficiency before. The ties are just a more maintainable version of OP's first example, as he also complained about its maintainability.
That looks very nice (concerning readability)! Didn't know that. I played around with it a bit and it seems like is no penalty (no additional copies) over what I called the "standard" way above.
Exactly; it's zero overhead and much more maintainable, that's why it's strongly recommended since C++11 when tuples were introduced.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.