¿Qué significa comparar dos colecciones de objetos para determinar cuál es la más pequeña?
Incluso si la comparación es natural para algunos tipos, comparar tipos compuestos que los contienen puede ser más complicado. Por ejemplo, los números reales tienen un orden natural (1,414 es menor que 3,14) pero los números complejos no tienen un orden (1 + i no es "menor" que 1 + 2i ). Esta diferencia se refleja en C++ en que hay un operator< para double , pero no hay uno para std::complex .
Sin embargo, para el tipo std::pair , podemos escribir lo siguiente:
auto p1 = std::pair{1, 1};
auto p2 = std::pair{1, 2};
auto const p1smaller = p1 < p2;
Aunque un número complejo está conceptualmente cerca de un par, el código anterior compila y p1smaller es igual a true en este caso.
Esto también funciona para std::tuple , así como para todos los contenedores STL, como std::vector :
auto v1 = std::vector{1, 2, 3, 4, 5};
auto v2 = std::vector{2, 3, 4, 5, 6};
auto const v1smaller = v1 < v2;
En el código anterior v1smaller también es true .
Escribiendo p1 == p2 o v1 == v2 o c1 == c2 (si c1 y c2 son std::complex números) también existe y tiene un significado natural:los dos contenedores tienen los mismos elementos en el mismo orden.
Pero v1 < v2 necesita una definición especial. En C++, esta es una comparación lexicográfica.
Comparación lexicográfica
Antes de definir la comparación lexicográfica, revisemos las posibles opciones para determinar cuál de los dos vectores (o par, tupla, conjunto, etc.) es más pequeño.
Uno de los que me viene a la mente es comparar su tamaño. El vector con menos elementos sería el "más pequeño". Incluso si esto puede tener algún sentido con respecto al significado en inglés de la palabra "pequeño", esta comparación no sería práctica, porque muchos vectores serían entonces equivalentes.
Para ilustrar, imagina que tienes una colección de vectores del mismo tamaño. Usar sus tamaños para compararlos significaría que no podríamos ordenar esa colección (o más bien que se ordenaría sin importar el orden de sus elementos). Esto evitaría realizar una búsqueda binaria en él, por ejemplo.
Dado que comparar el tamaño no sería práctico, podríamos comparar colecciones en función de los valores que contienen. ¿Qué pasa si definimos que v1 es menor que v2 si todos los elementos de v1 son más pequeños que todos los elementos de v2 ? O, dicho de otro modo, que max(v1) es menor que min(v2) ?
Esto tampoco sería práctico, porque todos los vectores no podrían compararse entre sí, por ejemplo, {1, 2, 3, 4, 5} no se pudo comparar con {2, 3, 4, 5, 6} . Un vector vacío también sería difícil de comparar, porque no tiene un mínimo ni un máximo.
Otra posibilidad sería comparar elementos de dos en dos:{1, 2, 3, 4, 5} sería más pequeño que {2, 3, 4, 5, 6} porque 1<2 y 2<3 y 3<4 etc. Pero algunos vectores aún no se pueden comparar entre sí, como {1, 2, 1} y {2, 1, 2} .
Afortunadamente, existe una manera de comparar colecciones que es tanto natural como práctica para propósitos de programación:comparación lexicográfica .
La comparación lexicográfica existe desde mucho antes de que existieran las computadoras y los algoritmos; la comparación lexicográfica es lo que usan los diccionarios para comparar palabras. De hecho, las palabras se pueden ver como colecciones de letras (es por eso que std::string en C++ tiene una interfaz de contenedor como std::vector ) y determinar cuál de las dos palabras debe aparecer antes que la otra es un diccionario se reduce a comparar dos colecciones (de letras) juntas. Siempre que los valores dentro de dos colecciones sean comparables entre sí, podemos realizar una comparación lexicográfica en esas colecciones.
Como en un diccionario, el algoritmo comienza comparando los primeros elementos de las dos colecciones. Si el primero es más pequeño entonces la colección es más pequeña. Si el segundo es más pequeño, entonces la segunda colección es más pequeña. Si ninguno es más pequeño, realizamos la misma verificación en los segundos elementos. Si llegamos al final de uno de la colección, entonces es el más pequeño.
v1 < v2 y p1 < p2 realizar comparaciones lexicograficas. c1 < c2 podría haber hecho lo mismo en teoría, pero los números complejos no definen un orden en matemáticas.
std::lexicographical_compare
Uno de los algoritmos STL, std::lexicographical_compare , también realiza una comparación lexicográfica entre dos colecciones:
auto v1 = std::vector{1, 2, 3, 4, 5};
auto v2 = std::vector{2, 3, 4, 5, 6};
auto const v1smaller = std::lexicographical_compare(begin(v1), end(v1), begin(v2), end(v2)); O, si envolvemos este algoritmo en una función que toma dos rangos (lo que deberías hacer con tus algoritmos antes de que se convierta en estándar en C++20):
auto v1 = std::vector{1, 2, 3, 4, 5};
auto v2 = std::vector{2, 3, 4, 5, 6};
auto const v1smaller = ranges::lexicographical_compare(v1, v2);
Pero entonces, ¿por qué un algoritmo si operator< ya hace lo mismo? Y lo que es más, ¿un algoritmo con el segundo nombre más largo de todo el STL?
std::lexicographical_compare es más poderoso que operator< , ya que puede hacer al menos 3 cosas que operator< no puedo:
1) std::lexicographical_compare puede comparar vectores que contienen diferentes tipos de valores.
El siguiente código no compila:
auto v1 = std::vector<int>{1, 2, 3, 4, 5};
auto v2 = std::vector<double>{2, 3, 4, 5, 6};
auto const v1smaller = v1 < v2;
porque v1 y v2 no son del mismo tipo, a pesar de que int s se puede comparar con double s.
Pero usando std::lexicographical_compare lo hace compilar:
auto v1 = std::vector{1, 2, 3, 4, 5};
auto v2 = std::vector<double>{2, 3, 4, 5, 6};
auto const v1smaller = ranges::lexicographical_compare(v1, v2);
2) std::lexicographical_compare puede comparar contenedores de diferentes tipos.
El siguiente código que compara un vector con un conjunto no se compila:
auto v1 = std::vector<int>{1, 2, 3, 4, 5};
auto s2 = std::set<int>{2, 3, 4, 5, 6};
auto const v1smaller = v1 < s2; Pero este sí:
auto v1 = std::vector<int>{1, 2, 3, 4, 5};
auto s2 = std::set<int>{2, 3, 4, 5, 6};
auto const v1smaller = ranges::lexicographical_compare(v1, s2); Y finalmente:
3) std::lexicographical_compare permite comparadores personalizados.
Si utiliza una colección de pares que representan claves y valores, por ejemplo, es posible que desee realizar una comparación basada únicamente en claves:
auto v1 = std::vector<std::pair<int, std::string>>{{1, "one"}, {2, "two"}, {3, "three"}};
auto v2 = std::vector<std::pair<int, std::string>>{{2, "two"}, {3, "three"}, {4, "four"}};
auto const v1smaller = std::lexicographical_compare(begin(v1), end(v1),
begin(v2), end(v2),
[](auto const& p1, auto const& p2){ return p1.first < p2.first;});
Y operator< no permite tales operadores de comparación personalizados.
Como ejemplo del uso conjunto de estas tres funciones, podríamos usar std::lexicographical_compare para comparar un std::vector<std::pair<int, std::string>> con un std::map<double, std::string> comparando claves entre sí:
auto v1 = std::vector<std::pair<int, std::string>>{{1, "one"}, {2, "two"}, {3, "three"}};
auto m2 = std::map<double, std::string>{{2, "two"}, {3, "three"}, {4, "four"}};
auto const v1smaller = std::lexicographical_compare(begin(v1), end(v1),
begin(m2), end(m2),
[](auto const& p1, auto const& p2){ return p1.first < p2.first;});
Es v1 < v2 eso naturales?
Si no necesita las funciones adicionales que ofrece std::lexicographical_compare , la forma más sencilla de comparar contenedores STL es usar operator< . Y para comparar pares y tuplas, debe usar operator< de todos modos porque los algoritmos STL no operan en ellos.
Pero encuentras la expresión v1 < v2 ¿natural? ¿Interpretaría esto como una comparación lexicográfica cuando lea el código, o preferiría que se explicara explícitamente usando std::lexicographical_compare? incluso en los casos simples? Déjame saber tu opinión dejando un comentario a continuación.