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++?

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.

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.

Answer 3

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