Orden Lexicográfico en C++

Cuando queremos ordenar un contenedor elementos en C++, como un std::vector, la forma más fácil es hacer una llamada como la siguiente:

std::sort(std::begin(v), std::end(v)); // Ordena el contenedor v

Sin embargo, esto requiere que el operador < esté definido para los elementos de v. Aún si estuviera definido, podemos querer ordenar los elementos de v bajo otro criterio. En estos casos, podemos usar

std::sort(std::begin(v), std::end(v), Sorter);

Donde Sorter es un function object (o functor, como les gusta decirles a los programadores de C++) que implementa la siguiente función

class Sorter
{
	bool operator () (T const& t1, T const& t2)
	{
		// implementación
	}
};

Una forma bastante común de comprar elementos es el orden lexicográfico¹, en donde comparamos como sigue:

1. Se comparan los primeros atributos de cada elemento. Si son distintos, el elemento con menor atributo será el menor.
2. Si los atributos del paso anterior son iguales, se comparan los segundos atributos de los elementos.
3. Si los segundos atributos son iguales, se comparan los terceros y así sucesivamente hasta encontrar elementos distintos o llegar a que los elementos son iguales.

Un ejemplo es la comparación entre fechas, donde comparamos primero por año, después por mes y finalmente por día. Así, una posible implementación para las fechas sería la siguiente:

class Sorter
{
	bool operator () (Fecha const& f1, Fecha const& f2)
	{
		if (f1.año != f2.año)
			return f1.año < f2.año;
		if (f1.mes != f2.mes)
			return f1.mes < f2.mes;
		return f1.dia < f2.dia;
	}
};

Para suerte nuestra, los objetos std::tuple y std::tie implementan el orden lexicográfico en su operador <, lo que podemos usar a nuestro favor para mejorar la mantenibilidad de nuestra implementación anterior.

class Sorter
{
	bool operator () (Fecha const& f1, Fecha const& f2)
	{
		return std::make_tie(f1.año, f1.mes, f1.dia)
		       < std::make_tie(f2.año, f2.mes, f2.dia);
	}
};

Todavía tenemos espacio para mejoras usando lambdas para evitar la repetición de código:

class Sorter
{
	bool operator () (Fecha const& f1, Fecha const& f2)
	{
		auto members = [](Fecha const& f)
		{
			return std::make_tie(f.año, f.mes, f.dia);
		};
		return members(f1) < members(f2);
	}
};

Aunque puede parecer que es más código que la versión anterior, el hecho de tener los atributos a comparar en un lugar centralizado hace más fácil la mantención de esta función y evita errores. Un detalle a tener en cuenta es que usaremos std::tie en los casos que podamos obtener los atributos por referencia y std::tuple cuando los obtenemos por copia.