How do I sort efficiently a quadruple structs in C++?

Question

I have a struct with members x,y,z and w. How do I sort efficiently first by x, then by y, by z and finally by w in C++?

Hollyanne

As with all kinds of sorting, determining a method that is particularly efficient (as you request) depends on the ranges of the sorted values and how much is known about them in advance. E.g. four passes of bucket sort (from w to x) may be more efficient than comparison-sort based methods. – Dalessandro

Using tuple comparisons has the added advantage that its implementation might use platform-dependent optimizations in order and manner of comparisons. Of course, if your datatype or the nature of your data allows, you might be able to do much better than that, e.g. using SIMD instructions to compare all four in one operations, etc. – Agma

Answer 1

If you want to implement a lexicographical ordering, then the simplest way is to use std::tie to implement a less-than or greater-than comparison operator or functor, and then use std::sort on a collection of your structs.

struct Foo
{
  T x, y, z, w;
};

....    
#include <tuple> // for std::tie

bool operator<(const Foo& lhs, const Foo& rhs)
{
  // assumes there is a bool operator< for T
  return std::tie(lhs.x, lhs.y, lhs.z, lhs.w) < std::tie(rhs.x, rhs.y, rhs.z, rhs.w);
}

....

#include <algorithm> // for std::sort

std::vector<Foo> v = ....;
std::sort(v.begin(), v.end());

If there is not a natural ordering for Foo, it might be better to define comparison functors instead of implementing comparison operators. You can then pass these to sort:

bool cmp_1(const Foo& lhs, const Foo& rhs)
{
  return std::tie(lhs.x, lhs.y, lhs.z, lhs.w) < std::tie(rhs.x, rhs.y, rhs.z, rhs.w);
}

std::sort(v.begin(), v.end(), cmp_1);

If you do not have C++11 tuple support, you can implement this using std::tr1::tie (use header <tr1/tuple>) or using boost::tie from the boost.tuple library.

Strew

The simplest, yes, but is it as efficient as simple sequence of comparisons? – Fade

@Fade I would be surprised if it wasn't. – Strew

OP asked for efficient, not easy way :) – Fade

@Fade well, I am sure OP is all set up to profile the different solutions we've given them :-) – Strew

Is this better than what Tony D suggested? – Hollyanne

As juanchopanza said, the best way to be 100% sure is to implement and benchmark both solution and post the results here :-). Should not be a big deal to test that ! – Photometer

@Hollyanne It is easier to understand and maintain, and I would be very surprised if it was not as efficient. But beware: we are all telling you about how to compare the structs, if you are really so concerned about the ultimate performance, you might need to experiment with different sorting algorithms. – Strew

I have compared the performance of this implementation vs other implementations a year ago. The result was, that all implementations result in (almost) the same assembly code. See the following URL (only in German): nosid.org/cxx11-comparator-performance.html – Lamontlamontagne

Answer 2

You can turn a struct into a std::tuple using std::tie, and use the lexicographic comparison std::tuple::operator<. Here's an example using a lambda to std::sort

#include <algorithm>
#include <tuple> 
#include <vector>

struct S 
{
   // x, y, z, w can be 4 different types!
   int x, y, z, w;
};

std::vector<S> v;

std::sort(std::begin(v), std::end(v), [](S const& L, S const& R) {
    return std::tie(L.x, L.y, L.z, L.w) < std::tie(R.x, R.y, R.z, R.w);
});

This example supplies std:sort with a comparison operator on-the-fly. If you always want to use lexicographic comparison, you could write a non-member bool operator<(S const&, S const&) that would automatically be selected by std::sort, or by ordered associative containers like std::set and std::map.

Regarding efficiency, from an online reference:

All comparison operators are short-circuited; they do not access tuple elements beyond what is necessary to determine the result of the comparison.

If you have a C++11 environment, prefer std::tie over hand-written solutions given here. They are more error-prone and less readable.

Pinhole

Answer 3

If you roll your own comparison operator, then you can freely throw objects into std::maps or invoke std::sort. This implementation's designed to be simple so you can easily verify and modify it if needed. By only using operator< to compare x, y, z and w, it minimises the number of operators you may need to implement if those variables are not already comparible (e.g. if they're your own structs rather than ints, double, std::strings etc.).

bool operator<(const Q& lhs, const Q& rhs)
{
    if (lhs.x < rhs.x) return true;
    if (rhs.x < lhs.x) return false;
    if (lhs.y < rhs.y) return true;
    if (rhs.y < lhs.y) return false;
    if (lhs.z < rhs.z) return true;
    if (rhs.z < lhs.z) return false;
    if (lhs.w < rhs.w) return true;
    return false;
}

Sometimes types will define a comparison function that returns -1, 0 or 1 to indicate less-than, equal or greater-than, both as a way to support the implementation of <, <=, ==, !=, >= and > and also because sometimes doing a < then a != or > would repeat a lot of work (consider comparing long textual strings where only the last character differs). If x, y, z and w happen to be of such types and have a higher-performance compare function, you can possibly improve your overall performance with:

bool operator<(const Q& lhs, const Q& rhs)
{
    int c;
    return (c = lhs.x.compare(rhs.x) ? c :
           (c = lhs.y.compare(rhs.y) ? c :
           (c = lhs.z.compare(rhs.z) ? c :
           lhs.w < rhs.w;
}

Percolator

Is this better than what juanchopanza suggested? – Hollyanne

It's less elegant, but faster. – Fade

@Fade do you have numbers to back that claim up? – Strew

@Spook, no it's not faster at all. Compilers will inline the std::tie. – Pinhole

@Pinhole But they will (might) call std::tuple ctor twice for every comparison ( >= 8 assignments, I guess) and they would have to inline < operator for tuples as well. You have to trust, that your compiler will optimize things up, while if you write a set of comparisons, you are sure, that this will work quickly (though code is not as elegant). – Fade

@Fade For all but the slowest Debug builds out-there, std::tie and operator< will be inlined and there will be no overhead. This has been measured and tested by many people. WHy do you think std::tie is in the Standard Library? Surely not to give the C++ haters out there more ammunition to claim inefficiency ;-) – Pinhole

This means you can use < on objects of your structure whenever you like, and consequently use lots of Standard library containers and algorithms without telling them how to test for '<' each time - that might or might not suit you... depends on what your program's doing. juanchopanza's approach also defined an operator, whereas some other answers use a lambda to sort only (e.g. Enigma's). – Percolator

Answer 4

This solution has at most 4 comparisons per element-compare and does not require construction of other objects:

// using function as comp
std::sort (quadrupleVec.begin(), quadrupleVec.end(), [](const Quadruple& a, const Quadruple& b)
{
    if (a.x != b.x) 
        return a.x < b.x;

    if (a.y != b.y)
        return a.y < b.y;

    if (a.z != b.z)
        return a.z < b.z;

    return a.w < b.w;
});

Catima

Can you please compare also your approach with what the others already suggested? – Hollyanne

Nice one! Even less comparisons to make. +1 :) – Fade

If the first two != return false you will have 4 comparisons. If the first != returns false you will have 3 comparisons. If the first != returns true you will have 2 comparisons. – Catima

There is one problem with your solution: some types only support equivalence using < and not inequality using !=. So yes, it is more efficient, but is also imposes stronger assumptions. – Pinhole