The std::sort algorithm has the signature
template <typename I>
void sort(I a, I b);
template <typename I, typename P>
void sort(I a, I b, P p);
where I implements RandomAccessIterator, and for the predicated version, P implements StrictOrdering. We can use this algorithm simply as
vector<X> v;
//... fill v
sort(v.begin(), v.end());
where the ordering predicate is defaulted to std::less<X>, which in turn would rely on the existence of an operator< for X.
If the type, X, did not innately have an operator<, one can be provided:
inline bool operator<(const X &a, const X &b) {
...
}
As an alternative, we may use the predicated version of sort and provide a predicate object that implements a strict ordering in an operator
bool operator()(const X &, const X &).
This predicate is used to compare objects during the sort to determine their relative order. std::less causes the objects to be sorted in ascending order. To sort in descending order, we would need to explicitly give a different predicate on the sort, namely a std::greater object:
vector<X> v;
...
sort(v.begin(), v.end(), std::greater<X>());
which relies on there existing on an operator> for the type X.
As a convenience, we can provide a function that will sort an entire container, written in terms of the standard iterator-oriented function and a predicate:
template <typename C>
void sort(C &container) {
std::sort(container.begin(), container.end());
}
template <typename C, typename P>
void sort(C &container, P p) {
std::sort(container.begin(), container.end(), p);
}
These can be used more succinctly to sort an entire container:
vector<X> v;
...
sort(v); // ascending
sort(v, greater<X>()); // descending
Note that this is just a convenience - we can apply all the techniques from here on to the "raw" std::sort algorithm if we need a more specific iterator range. Since the majority of the time we are sorting an entire container, this convenience function comes in handy.
Regardless of which version of sort we use, if we wanted to provide several sorting options for the type, X, we can implement predicates for each special case. For example, assume the following person class:
class person {
public:
string first_name;
string last_name;
};
Suppose we wish to sort on first name on one occasion, then last name on another. We can only have one operator<, so we would have to construct the two predicates:
class by_first_name {
public:
bool operator()(const person &a, const person &b) {
return a.first_name < b.first_name;
}
};
class by_last_name {
public:
bool operator()(const person &a, const person &b) {
return a.last_name < b.last_name;
}
};
and use them like so:
vector<person> people;
sort(people, by_first_name());
sort(people, by_last_name());
We could generalize the concept of accessing members in a predicate like the following:
template <typename T, typename M, typename P = std::less<M> >
class by_member_t {
public:
typedef M (T::*type);
type member;
P p;
by_member_t(type init) : member(init) { }
by_member_t(type init, P init_p) :
member(init),
p(init_p)
{ }
bool operator()(const T &a, const T &b) {
return p((a.*member), (b.*member));
}
};
template <typename T, typename M, typename P>
inline by_member_t<T, M, P> by_member(M (T::*member), P predicate) {
return by_member_t<T, M, P>(member, predicate);
}
template <typename T, typename M>
inline by_member_t<T, M> by_member(M (T::*member)) {
return by_member_t<T, M, std::less<M> >(member);
}
and use this generalization like this
sort(people, by_member(&person::first_name));
sort(people, by_member(&person::last_name));
sort(people, by_member(&person::first_name, std::greater<string>());
For more complicated scenarios, it may still be preferable to provide a dedicated predicate class, such as the case where we wish to sort ascending by last name and first name within last:
class by_last_then_first {
public:
bool operator()(const person &a, const person &b) {
return a.last_name < b.last_name ||
(a.last_name == b.last_name &&
a.first_name < b.first_name);
}
};
vector<person> people;
...
sort(people, by_last_then_first());
Classes are often written using private members and public accessors. If this is the case, our predicates cannot be written in terms of direct member access, but rather through the accessors. Consider the alteration of the person class:
class person {
private:
string first_name;
string last_name;
public:
string get_first() const { return first_name; }
string get_last() const { return last_name; }
};
This spells trouble for the by_member generalization formulated earlier. The solution is to provide a by_member variant that works on member functions instead of members.
template <typename T, typename M, typename P = std::less<M> >
class by_member_function {
public:
typedef M (T::*function)();
function f;
P p;
by_member_function(function init_f, P init_p) :
f(init_f), p(init_p) { }
by_member_function(function init_f) : f(init_f) { }
bool operator()(const T &a, const T &b) {
return p((a.*f)(), (b.*f)());
}
};
template <typename T, typename M>
by_member_function<T, M> by_member(M (T::*f)()) {
return by_member_function<T, M>(f);
}
template <typename T, typename M, typename P>
by_member_function<T, M, P> by_member(M (T::*f)(), P p) {
return by_member_function<T, M, P>(f, p);
}
This allows us to write
sort(people, by_member(&person::get_first));
sort(people, by_member(&person::get_last, std::greater<string>()));
Note that this keeps the notation still fairly readable but allows us greater generality.
After we learn the basics of using a generic algorithm such as sort, it is natural and useful to "push the limits" on its usage. Most of the C++ standard library is written to be extensible either through inheritance or most often through parameterization. The parameterization of iterator types, transform functions, and predicates make algorithms flexible and sometimes quite succinct in their every-day usage, especially with a little help from convenience functions and aptly named classes.