1

Given a std::vector of Custom objects, I want to sort this list according to multiple queries (where I first sort on value1 and then on value2) so:

bool customSort(const Custom &a, const Custom &b)
{
    return value1 < b.value1 && a.value2 < b.value2;
}

std::vector<Custom> elements;
std::sort(elements.begin(), elements.end(), customSort);

Unfortunately, this doesn't work (as it will happen that customSort(a,b) and customSort(b,a) equal true) and I thus have to sort like this (in reverse order): 

bool customSortValue1(const Custom &a, const Custom &b)
{
    return value1 < b.value1;
}

bool customSortValue2(const Custom &a, const Custom &b)
{
    return value2 < b.value2;
}


std::vector<Custom> elements;
// note that I first sort by customSortValue2 and than customSortValue1
std::sort(elements.begin(), elements.end(), customSortValue2);
std::sort(elements.begin(), elements.end(), customSortValue1);

Which works, but is obviously less efficient as I have to traverse the entire vector n times with n being equal to the number of sorting queries I want to do.

Is there some advanced logic trick that might still make this possible or is sorting on multiple properties within a single comparison operator inherintly impossible?

Djemon
  • 105
  • 8
  • Possible duplicate of [Operator< and strict weak ordering](http://stackoverflow.com/questions/979759/operator-and-strict-weak-ordering) – LogicStuff Oct 15 '16 at 12:25
  • 1
    It won't even necessarily work, since `std::sort` is non-stable. You'd need `std::stable_sort` otherwise your first sort is potentially useless. – Lightness Races in Orbit Oct 15 '16 at 12:32
  • Anyway, what you're doing certainly is not "inherently" impossible; it's done all the time. You just need to write your comparator correctly. ComicSansMS has got it, despite their answer not really explaining why. – Lightness Races in Orbit Oct 15 '16 at 12:33
  • Interesting, had no idea about `std::stable_sort`, thank you! – Djemon Oct 15 '16 at 12:41
  • 1
    The `std::tie` route is generally the best solution, but the duplicate suggested by `LogicStuff` is worth reading. `a1 < b1 && a2 < b2` is simply incorrect. Consider how you compare `15` and `23`. You don't say to yourself "if one is less than two **and** five is less than three then 15 is less than 23", right? (The answer would be "false", no?) You only proceed to the second step if `a1 == b1`. That's usually written as `a1 < b1 || (!(b1 < a1) && a2 < b2)`, in order to avoid using more than one comparison operator (in case it is being replaced by a functor). – rici Oct 15 '16 at 15:38

1 Answers1

5

If you just want lexicographic ordering, std::tuple will help you out:

bool customSort(const Custom &a, const Custom &b)
{
    return std::tie(a.value1, a.value2) < std::tie(b.value1, b.value2);
}
ComicSansMS
  • 51,484
  • 14
  • 155
  • 166