When we want to sort an element container in C++, like an std::vector, the simplest way is to make a call like this:
std::sort(std::begin(v), std::end(v)); // Sorts container v
However, this requires that the < operator is defined for the elements of v. Even if it were defined, we may want to sort the elements of v by a different criterion. In those cases, we could use
std::sort(std::begin(v), std::end(v), Sorter);
Where Sorter is a function object (or functor, as C++ programmers like to call them) that implements the following function
class Sorter
{
bool operator () (T const& t1, T const& t2)
{
// implementation
}
};
A very common way to compare elements is by lexicographical order[1], which works as follows:
- We compare the first attribute of each element, if they are different, the element with the lower attribute will go first in the order.
- If the attributes in the previous step are equal, we compare the second attribute of each element.
- If the second attribute are equal, we the compare the third attribute and so on, until we find an attribute in which the elements are different or finally found out that the elements are equal.
A good example is when we compare dates, as we first compare by year, then by month and last by day. Then, a possible implementation for dates would be as follows:
class Sorter
{
bool operator () (Date const& d1, Date const& d2)
{
if (d1.year != d2.year)
return d1.year < d2.year;
if (d1.month != d2.month)
return d1.month < d2.month;
return d1.day < d2.day;
}
};
Luckily for us, the std::tuple and std::tie objects implement lexicographical order in their< operator, so we can take advantage of this to improve the maintainability of the previous implementation.
class Sorter
{
bool operator () (Date const& d1, Date const& d2)
{
return std::make_tie(d1.year, d1.month, d1.day)
< std::make_tie(d2.year, d2.month, d2.day);
}
};
We still have room for improvement by using lambdas to avoid code duplication:
class Sorter
{
bool operator () (Date const& d1, Date const& d2)
{
auto members = [](Date const& f)
{
return std::make_tie(f.year, f.month, f.day);
};
return members(d1) < members(d2);
}
};
Even though it appears that we wrote more code that the previous version, the fact that we have the attributes to compare in a single and centralized place makes this implementation more maintainable and less error-prone. A last detail to remember is that we will use std::tie when we can get the attributes by reference and std::tie when we get them by copy.