Sorting a vector of custom objects

Question

How does one go about sorting a vector containing custom (i.e. user defined) objects.
Probably, standard STL algorithm sort along with a predicate (a function or a function object) which would operate on one of the fields (as a key for sorting) in the custom object should be used.
Am I on the right track?

Answer 1

You are on the right track. std::sort will use operator< as comparison function by default. So in order to sort your objects, you will either have to overload bool operator<( const T&, const T& ) or provide a functor that does the comparison, much like this:

 struct C {
    int i;
    static bool before( const C& c1, const C& c2 ) { return c1.i < c2.i; }
 };

 bool operator<( const C& c1, const C& c2 ) { return c1.i > c2.i; }

 std::vector<C> values;

 std::sort( values.begin(), values.end() ); // uses operator<
 std::sort( values.begin(), values.end(), C::before );

The advantage of the usage of a functor is that you can use a function with access to the class' private members.

Answer 2

You could use functor as third argument of std::sort, or you could define operator< in your class.

struct X {
    int x;
    bool operator<( const X& val ) const { 
        return x < val.x; 
    }
};

struct Xgreater
{
    bool operator()( const X& lx, const X& rx ) const {
        return lx.x < rx.x;
    }
};

int main () {
    std::vector<X> my_vec;

    // use X::operator< by default
    std::sort( my_vec.begin(), my_vec.end() );

    // use functor
    std::sort( my_vec.begin(), my_vec.end(), Xgreater() );
}

Answer 3

typedef struct Freqamp{
    double freq;
    double amp;
}FREQAMP;

bool struct_cmp_by_freq(FREQAMP a, FREQAMP b)
{
    return a.freq < b.freq;
}

main()
{
    vector <FREQAMP> temp;
    FREQAMP freqAMP;

    freqAMP.freq = 330;
    freqAMP.amp = 117.56;
    temp.push_back(freqAMP);

    freqAMP.freq = 450;
    freqAMP.amp = 99.56;
    temp.push_back(freqAMP);

    freqAMP.freq = 110;
    freqAMP.amp = 106.56;
    temp.push_back(freqAMP);

    sort(temp.begin(),temp.end(), struct_cmp_by_freq);
}

if compare is false, it will do "swap".

Answer 4

Sorting such a vector or any other applicable (mutable input iterator) range of custom objects of type X can be achieved using various methods, especially including the use of standard library algorithms like

• sort,
• stable_sort,
• partial_sort or
• partial_sort_copy.

Since most of the techniques, to obtain relative ordering of X elements, have already been posted, I'll start by some notes on "why" and "when" to use the various approaches.

The "best" approach will depend on different factors:

1. Is sorting ranges of X objects a common or a rare task (will such ranges be sorted a mutiple different places in the program or by library users)?
2. Is the required sorting "natural" (expected) or are there multiple ways the type could be compared to itself?
3. Is performance an issue or should sorting ranges of X objects be foolproof?

If sorting ranges of X is a common task and the achieved sorting is to be expected (i.e. X just wraps a single fundamental value) then on would probably go for overloading operator< since it enables sorting without any fuzz (like correctly passing proper comparators) and repeatedly yields expected results.

If sorting is a common task or likely to be required in different contexts, but there are multiple criteria which can be used to sort X objects, I'd go for Functors (overloaded operator() functions of custom classes) or function pointers (i.e. one functor/function for lexical ordering and another one for natural ordering).

If sorting ranges of type X is uncommon or unlikely in other contexts I tend to use lambdas instead of cluttering any namespace with more functions or types.

This is especially true if the sorting is not "clear" or "natural" in some way. You can easily get the logic behind the ordering when looking at a lambda that is applied in-place whereas operator< is opague at first sight and you'd have to look the definition up to know what ordering logic will be applied.

Note however, that a single operator< definition is a single point of failure whereas multiple lambas are multiple points of failure and require a more caution.

If the definition of operator< isn't available where the sorting is done / the sort template is compiled, the compiler might be forced to make a function call when comparing objects, instead of inlining the ordering logic which might be a severe drawback (at least when link time optimization/code generation is not applied).

Ways to achieve comparability of class X in order to use standard library sorting algorithms

Let std::vector<X> vec_X; and std::vector<Y> vec_Y;

1. Overload T::operator<(T) or operator<(T, T) and use standard library templates that do not expect a comparison function.

Either overload member operator<:

struct X {
  int i{}; 
  bool operator<(X const &r) const { return i < r.i; } 
};
// ...
std::sort(vec_X.begin(), vec_X.end());

or free operator<:

struct Y {
  int j{}; 
};
bool operator<(Y const &l, Y const &r) { return l.j < r.j; }
// ...
std::sort(vec_Y.begin(), vec_Y.end());

2. Use a function pointer with a custom comparison function as sorting function parameter.

struct X {
  int i{};  
};
bool X_less(X const &l, X const &r) { return l.i < r.i; }
// ...
std::sort(vec_X.begin(), vec_X.end(), &X_less);

3. Create a bool operator()(T, T) overload for a custom type which can be passed as comparison functor.

struct X {
  int i{};  
  int j{};
};
struct less_X_i
{
    bool operator()(X const &l, X const &r) const { return l.i < r.i; }
};
struct less_X_j
{
    bool operator()(X const &l, X const &r) const { return l.j < r.j; }
};
// sort by i
std::sort(vec_X.begin(), vec_X.end(), less_X_i{});
// or sort by j
std::sort(vec_X.begin(), vec_X.end(), less_X_j{});

Those function object definitions can be written a little more generic using C++11 and templates:

struct less_i
{ 
    template<class T, class U>
    bool operator()(T&& l, U&& r) const { return std::forward<T>(l).i < std::forward<U>(r).i; }
};

which can be used to sort any type with member i supporting <.

4. Pass an anonymus closure (lambda) as comparison parameter to the sorting functions.

struct X {
  int i{}, j{};
};
std::sort(vec_X.begin(), vec_X.end(), [](X const &l, X const &r) { return l.i < r.i; });

Where C++14 enables a even more generic lambda expression:

std::sort(a.begin(), a.end(), [](auto && l, auto && r) { return l.i < r.i; });

which could be wrapped in a macro

#define COMPARATOR(code) [](auto && l, auto && r) -> bool { return code ; }

making ordinary comparator creation quite smooth:

// sort by i
std::sort(v.begin(), v.end(), COMPARATOR(l.i < r.i));
// sort by j
std::sort(v.begin(), v.end(), COMPARATOR(l.j < r.j));

Answer 5

In your class, you may overload the "<" operator.

class MyClass
{
  bool operator <(const MyClass& rhs)
  {
    return this->key < rhs.key;
  }
}

Answer 6

In the interest of coverage. I put forward an implementation using lambda expressions.

C++11

#include <vector>
#include <algorithm>

using namespace std;

vector< MyStruct > values;

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

C++14

#include <vector>
#include <algorithm>

using namespace std;

vector< MyStruct > values;

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