C++11 sort collection of custom objects by several properties

Question

There is a collection of a custom struct elements:

struct MyStruct
{
    int id;
    std::string currencyCode;
    int month;
    int year;
    int amount;
};

This data will be displayed in some table that allows sorting by several columns (by clicking on table columns holding Ctrl button).

Sorting a collection of customer objects by one property is as simple as:

vector<MyStruct> values;

std::sort( values.begin( ), values.end( ), [ ]( const MyStruct& lhs, const MyStruct& rhs )
{
   return lhs.key < rhs.key;
});

or

struct MyStruct_x_Greater
{
    bool operator()( const MyStruct& lMyStruct, const MyStruct& rMyStruct ) const {
        return lMyStruct.x < rMyStruct.x;
    }
};

std::sort( values.begin(), values.end(), MyStruct_x_Greater() );

But how make sorting by several properties one by other (something like sql ORDER BY column1 DESC, column2 ASC)?

Answer 1

Just change the comparator. Suppose you want to order by year, then by month, then by amount, then:

std::sort( values.begin(), values.end(), [ ]( const MyStruct& lhs, const MyStruct& rhs )
{
   return std::tie(lhs.year, lhs.month, lhs.amount) <
          std::tie(rhs.year, rhs.month, rhs.amount);
});

std::tuple's operator< does a lexicographical comparison, so there's no need to roll your own (and risk getting it wrong). To do a descending order for an attribute, just swap lhs and rhs for that attribute.

Answer 2

Your need to choose the sort order at runtime differs from most similar questions (and a few knee-jerk answers you've received). I suggest you give each field an id number, and add an function to compare a field specified by id:

template <typename T>
int cmp(const T& lhs, const T& rhs)
{
    return lhs < rhs ? -1 : lhs == rhs ? 0 : 1;
}

struct MyStruct
{
    int id;   // 0
    std::string currencyCode;  // 1
    int month;  // 2
    int year;  // 3
    int amount;  // 4

    int cmp(int field_id, const MyStruct& rhs) const
    {
        switch (field_id)
        {
          case 0: return cmp(id, rhs.id);
          case 1: return cmp(currencyCode, rhs.currencyCode);
          case 2: return cmp(month, rhs.month);
          case 3: return cmp(year, rhs.year);
          case 4: return cmp(amount, rhs.amount);
          default: throw ...cases out of sync with code...;
        }
    }
};

// update this as your column heading are clicked...
std::vector<int> sort_field_ids = ...;

std::sort(begin(values), end(values),
    [&](const MyStruct& lhs, const MyStruct& rhs)
    {
        for (auto fid : sort_field_ids)
        {
            int cmp = lhs.cmp(fid, rhs);
            if (cmp) return cmp == -1;
        }
        // fall back on something stable and unique
        return lhs.id < rhs.id;
    });

To support descending sorts, maintain an extra flag (e.g. std::vector<std::pair<int, bool>> sort_field_ids) then return (cmp == -1) ^ descending; (where fid,descending are extracted from your pair, or refer to them as .first / .second if you prefer).

Better yet, find a graphics library with a decent grid/table widget that does the sorting internally.

Answer 3

Solving this by assigning IDs to the fields has several drawbacks:

• Cases may not be covered (as indicated by the throw)
• Sorting in reverse order requires an extra flag
• It's not obvious from the code which ID stands for which field
• It's not easily extensible (you always have to update your ID mappings)

---

Alternatively, you could define "comparators", that return -1, 0 or 1, depending on whether the first argument is smaller than, equal to or greater than the second, respectively. These comparators can then be combined and reversed quite generically, and used as a sorting predicate.

Given a set of these comparators for the fields of your struct, you may compose them like this:

Comparator byYearReverseAndMonth = compose(reverse(byYear), byMonth);
std::sort(values.begin(), values.end(), with(byYearReverseAndMonth));

Edit in response to the comment:

Of course it is not necessary to define each combination of comparators and reverse comparators at compile time. Instead, one can collect the desired comparators for the next sort at runtime, for example, in a vector<Comparator>. The comparator instances could, for example, be associated with the columns of a table:

vector<Comparator> comparators;
for (each selected column) {
    comparators.push_pack(comparatorFor(column));
}

These comparators can then be composed into a single one, with a simple loop over all comparators:

Comparator composedComparator = comparators[0];
for (int i=1; i<comparators.size(); ++i) {
    composedComparator = compose(comparator, comparators[i]);
}

sort(v.begin(),v.end(),with(composedComparator));

A sketch of what this may look like:

#include <algorithm>
#include <functional>
#include <iostream>
#include <vector>

struct MyStruct
{
    int id;
    std::string currencyCode;
    int month;
    int year;
    int amount;
};

typedef std::function<int(const MyStruct& s0, const MyStruct& s1)> Comparator;
typedef std::function<bool(const MyStruct& s0, const MyStruct& s1)> Predicate;

template <typename T>
std::function<int(const T&, const T&)> compose(
    std::function<int(const T&, const T&)> c0,
    std::function<int(const T&, const T&)> c1)
{
    return[c0, c1](const T& t0, const T& t1) -> int
    {
        int r0 = c0(t0, t1);
        if (r0 != 0)
        {
            return r0;
        }
        return c1(t0, t1);
    };
}

template <typename T>
std::function<int(const T&, const T&)> reverse(
    std::function<int(const T&, const T&)> c)
{
    return[c](const T& t0, const T& t1) -> int
    {
        return -c(t0, t1);
    };
}

template <typename T>
std::function<bool(const T&, const T&)> with(
    std::function<int(const T&, const T&)> comparator)
{
    return[comparator](const T& t0, const T& t1) 
    {
        return comparator(t0, t1) < 0;
    };
}


void print(std::vector<MyStruct>& values)
{
    for (auto it = values.begin(); it != values.end(); ++it)
    {
        std::cout << (*it).month << "-"
            << (*it).year << " id "
            << (*it).id << std::endl;
    }
}

int main(int argc, char** argv)
{
    std::vector<MyStruct> values;

    MyStruct m;
    m.year = 1981; m.month = 1; m.id = 4;  values.push_back(m);
    m.year = 1980; m.month = 2; m.id = 5;  values.push_back(m);
    m.year = 1980; m.month = 4; m.id = 2;  values.push_back(m);
    m.year = 1980; m.month = 3; m.id = 3;  values.push_back(m);
    m.year = 1980; m.month = 4; m.id = 1;  values.push_back(m);

    std::cout << "Before sorting" << std::endl;
    print(values);

    Comparator byMonth = [](const MyStruct& s0, const MyStruct& s1)
    {
        if (s0.month < s1.month) return -1;
        if (s0.month > s1.month) return  1;
        return 0;
    };
    Comparator byYear = [](const MyStruct& s0, const MyStruct& s1)
    {
        if (s0.year < s1.year) return -1;
        if (s0.year > s1.year) return  1;
        return 0;
    };
    Comparator byId = [](const MyStruct& s0, const MyStruct& s1)
    {
        if (s0.id < s1.id) return -1;
        if (s0.id > s1.id) return  1;
        return 0;
    };

    Comparator byYearAndMonth = compose(byYear, byMonth);
    std::sort(values.begin(), values.end(), with(byYearAndMonth));

    std::cout << "After sorting by year and month:" << std::endl;
    print(values);


    Comparator byYearReverseAndMonth = compose(reverse(byYear), byMonth);
    std::sort(values.begin(), values.end(), with(byYearReverseAndMonth));

    std::cout << "After sorting by year reverse and month:" << std::endl;
    print(values);


    Comparator byYearAndMonthAndId = compose(byYearAndMonth, byId);
    std::sort(values.begin(), values.end(), with(byYearAndMonthAndId));

    std::cout << "After sorting by year and month and id:" << std::endl;
    print(values);

    return 0;
}

_{(Apologies for potential faux pas, I'm a C++ newbie)}

Answer 4

Use next key only if values of current key are equal:

[ ]( const MyStruct& lhs, const MyStruct& rhs )
{
    if(lhs.key1 != rhs.key1) 
        return lhs.key1 < rhs.key1;

    if(lhs.key2 != rhs.key2) 
        return lhs.key2 < rhs.key2;

    ...    

    return lhs.keyN < rhs.keyN;
}

In this example, entries will be ordered accroding key1, than, key2 and so on up to keyN.