Standard library sort and user defined types

Question

If I want to sort a vector of a UDT by one of two types of variables it holds, is it possible for the standard library sort to do this or do I need to write my own sort function.

For example if you had

struct MyType{
 int a;
 int b;
};

vector<MyType> moo;

// do stuff that pushes data back into moo

sort(moo.begin(), moo.end()) // but sort it by lowest to highest for a, not b

So is this possible using the stdlib sort? Thanks.

Answer 1

It is possible to use standard function if your type implements "bool operator < (...) const" and a copy constructor (compiler-generated or custom).

struct MyType {
    int a;
    int b;
    bool operator < (const MyType& other) const {
        ... // a meaningful implementation for your type
    }
    // Copy constructor (unless it's a POD type).
    MyType(const MyType &other)
        : a(other.a), b(other.b) { }
    // Some other form of construction apart from copy constructor.
    MyType()
        : a(0), b(0) { }
};

Alternatively, you can pass an ordering function (or a functor) as a third argument to sort() instead of implementing operator "<".

bool type_is_less(const MyType& t1, const MyType& t2) { ... }
...
std::sort(c.begin(), c.end(), type_is_less);

This is useful in the following situations:

1. you don't want to implement operator "<" for whatever reason,
2. you need to sort a container of built-in or pointer types for which you can't overload operators.

Answer 2

There's three ways to do this:

You could overload operator< for your class:

bool operator<(const MyType& lhs, const MyType& rhs) {return lhs.a<rhs.a;}

This has the disadvantage that, if you ever want to sort them according to b, you're out of luck.

You could also specialize std::less for your type. That makes std::sort working (and other things, like using the type as a key in a map) without hijacking operator< for this meaning. It does, however, still hijack a general-purpose comparison syntax for a, while you might, at other places in your code, compare your type according to b.

Or you could write your own comparator like this:

struct compare_by_a {
  bool operator()(const MyType& lhs, const MyType& rhs) const
  {return lhs.a<rhs.a;}
};

(Note: The const after the operator isn't strictly necessary. I still consider it good style, though.) This leaves the general-purpose means of comparison undefined; so if some code wants to use them without you being aware, the compile emits an eror and makes you aware of it. You can use this or other comparators selectively and explicitly where ever you need comparison.