Lexicographical Order in C++

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 functoras 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¹, which works as follows:

1. We compare the first attribute of each element, if they are different, the element with the lower attribute will go first in the order.
2. If the attributes in the previous step are equal, we compare the second attribute of each element.
3. 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 implmentation.

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 lambas 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 implementatio 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.