C++ implementation of ORDER BY on struct

Question

i searched a lot here and on other sites as well but i have not found something satisfying.

what i need is quite simple task - substantially to construct ORDER BY operator in c++. this means i have struct with a number of various data type members and i need a comparator for it with members and orderings configurable. here is my pseudocode idea:

comparator.add(&MyStruct::member1, std::less);
comparator.add(&MyStruct::member2, std::greater);
std::sort(my_vector.begin(), my_vector.end(), comparator);

and i get data sorted by member1 and if it is equal member2 decides, and so on.

i am not too good in stl and templates, but i can read and decipher some code and found this as very appropriate solution: https://stackoverflow.com/a/11167563

unfortunately in my work i have to use c++ builder with faulty 32bit compiler that refuses to compile this correct code. it does support almost nothing from c++11, it has boost 1.39 available.

does someone have any solution that could work for me with my resources available? thank you in advance

EDIT:

i got very specialised solutions with hard-written comparison operators which i am aware of and which do not work here too good. i missed this in my question. my struct has at least 15 members and as i wrote, i need to often change individual sort directions for members/columns (asc, desc). too, i need to often change set of sorted members, just like in order by operator in sql, for example. also i cannot use something like stable_sort as i am just writing comparator for something like OnCompare event of some class.

Answer 1

It's not too difficult. First, consider the "canonical" ordering relationship:

struct Compare
{
    bool operator()( C const& lhs, C const& rhs ) const
    {
        return lhs.a < rhs.a
            || ( !(rhs.a < lhs.a) && lsh.b < rhs.b )
            || ( !(rhs.a < lhs.a) && !(rhs.b < lhs.b) && lhs.c < rhs .c )
            || ...
    }
};

Obviously, no one would actually write something like this, but it corresponds exactly to the formal definition of what is needed.

Of course, if we can imagine the data members as an array, we could rewrite this as a loop, taking advantage of the previously established !(rhs[i-1] < lsh[i-1] in each case:

struct Compare
{
    bool operator()( C const& lhs, C const& rhs ) const
    {
        int i = 0;
        while ( i != N && !(lhs[i] < rhs[i]) && !(rhs[i] < lhs[i]) ) {
            ++ i;
        }
        return i != N && lhs[i] < rhs[i];
    }
};

Or, if all of the elements are fully ordered, so that == is also defined on them, and we can assume that it corresponds to the equivalence relationship established by the weak partial ordering:

struct Compare
{
    bool operator()( C const& lhs, C const& rhs ) const
    {
        int i = 0;
        while ( i != N && !(lhs[i] == rhs[i]) ) {
            ++ i;
        }
        return i != N && lhs[i] < rhs[i];
    }
};

All that remains is to somehow translate this into something that can process an arbitrary ordering of elements of arbitrary types. There's an old saying that the solution to every problem is an additional level of indirection, and it applies here.

First, we need some means of handling the different types of each element. Polymorphism seems appropriate (although templates could be made to work if the order in which the elements were evaluated were fixed at compile time):

struct CompareOneElementOfC
{
    virtual bool isLessThan( C const& lhs, C const& rhs) const = 0;
    virtual bool isEqual( C const& lhs, C const& rhs) const = 0;
};

template <typename T, T C::*ptr>
struct ConcreteCompareOneElementOfC : public CompareOneElementOfC
{
    virtual bool isLessThan( C const& lhs, C const& rhs) const
    {
        return lhs.*ptr < rhs.*ptr;
    }
    virtual bool isEqual( C const& lhs, C const& rhs) const
    {
        return lhs.*ptr == rhs.*ptr;
    }
};

Depending on the types of the elements, you may need to hand write specific concrete instances. And if any of the elements doesn't support total ordering, you will have to omit the isEqual, and modify the following code accordingly.

Having got this far, we need exactly one static instance of each concrete Compare:

ConcreteCompareOneElementOfC<int, &C::a> const c1;
ConcreteCompareOneElementOfC<double, &C::b> const c2;
//  ...

Finally, put the addresses of these instances in a table:

CompareOneElementOfC const* const cmp[] = { &c1, &c2 ... };

You can have different tables for different orderings. If there are only a few, define static tables for each, and be done with it. If the orderings can be arbitrary, create the table on the fly before each sort, in the desired order.

Finally:

class Compare
{
    CompareOneElementOfC const* const* begin;
    CompareOneElementOfC const* const* end;
public:
    template< size_t N >
    Compare( CompareOneElementOfC const* const (&cmp)[N] )
        : begin( cmp )
        , end( cmp + N )
    {
    }
    bool
    operator()( C const& lhs, C const& rhs ) const
    {
        auto current = begin;
        while ( current != end && (*current)->isEqual( lhs, rhs ) ) {
            ++ current;
        }
        return current != end && (*current)->isLessThan( lhs, rhs );
    }
}

(Please note that I haven't actually tested this code, so there are probably typos and other errors. Still, the basic idea should be there.)

Answer 2

I think just overloading operator < will work for you.

struct Struct {
    int member1;
    int member2;

    bool operator<(const Struct& rhs) const {
        if (member1 != rhs.member1)
            return member1 < rhs.member1
        else
            return member2 > rhs.member2
    }
};

This way whenever any 2 instances of Struct are compared, they will be compared by the comparison function defined in operator <.

So a simple std::sort(vec.begin(), vec.end()) will just work!

EDIT:

Otherwise you can always define a functor which can be used to compare each element. This is just a class with an overloaded operator () which is used for comparison.

class ComparisonClass {
public:
    bool operator()(const Struct& lhs, const Struct& rhs) {
        if (lhs.member1 != rhs.member1)
            return lhs.member1 < rhs.member1
        else
            return lhs.member2 > rhs.member2
    }
};

You can additionally define some member values of the ComparisonClass which define the order of comparisons.

Using it would be calling it like so std::sort(vec.begin(), vec.end(), ComparisonClass());

EDIT2:

Slightly more elaborate code -

class ComparisonClass {
public:
    bool operator()(const Struct& lhs, const Struct& rhs) {
        for(int i=0; i<m_comparisonOrder.size(); i++) {
            int pos = m_comparisonOrder[i];
            if (lhs[pos] != rhs[pos]) {
                if (m_comparisonType[pos])
                    return lhs[pos] < rhs[pos];
                else
                    return lhs[pos] > rhs[pos];
            }
        }
    }

    std::vector<int> m_comparisonOrder.
    std::vector<bool> m_comparisonType;
};

Here I'm assuming that Struct has an operator [] which returns the appropriate member variable.