c++ - example - ¿Por qué usar std:: less como el functor predeterminado para comparar claves en std:: map y std:: set?

set insert c++

Question

Me pregunto por qué std::map y std::set usan std::less como el functor predeterminado para comparar claves. ¿Por qué no usar un functor que funciona de forma similar a strcmp? Algo como:

 template <typename T> struct compare
{
// Return less than 0 if lhs < rhs
// Return 0 if lhs == rhs
// Return greater than 0 if lhs > rhs
int operator()(T const& lhs, T const& rhs)
{
return (lhs-rhs);
}
}

Supongamos que un map tiene dos objetos, con las teclas key2 y key2 . Ahora queremos insertar otro objeto con key key3 .

Al usar std::less , la función de insert necesita primero llamar a std::less::operator() con key3 y key3 . Supongamos que std::less::operator()(key1, key3) devuelve falso. Tiene que volver a llamar a std::less::operator() con las teclas switched, std::less::operator()(key3, key1) , para decidir si key1 es igual a key3 o key3 es mayor que key1 . Hay dos llamadas a std::less::operator() para tomar una decisión si la primera llamada devuelve falso.

Si std::map::insert used compare , hubiera suficiente información para tomar la decisión correcta con solo una llamada.

Dependiendo del tipo de clave en el mapa, std::less::operator()(key1, key2) podría ser costoso.

A menos que me falta algo muy básico, ¿no deberían std::map y std::set usar algo como compare lugar de std::less como el functor predeterminado para comparar claves?

Answer 1

Decidí preguntarle a Alexander Stepanov (diseñador de STL) sobre esto. Puedo citarlo de la siguiente manera:

Originalmente, propuse comparaciones tripartitas. El comité estándar me pidió que cambie a los operadores de comparación estándar. Hice lo que me dijeron. He estado abogando por agregar componentes de 3 vías al estándar por más de 20 años.

Pero tenga en cuenta que quizás no sea intuitivo, 2 vías no es una gran sobrecarga. No tiene que hacer el doble de comparaciones. Solo hay una comparación por nodo en el camino hacia abajo (sin verificación de igualdad). El costo no puede regresar temprano (cuando la clave está en una hoja) y una comparación adicional al final (intercambiando los argumentos para verificar la igualdad). Si no me equivoco, eso hace

1 + 1/2*1 + 1/4*2 + 1/8*3 + ...
= 1 + 1/2+1/4+1/8+... + 1/4+1/8+... + ...
-> 3 (depth -> infty)

Comparaciones adicionales en promedio en un árbol equilibrado que contiene el elemento consultado.

Por otro lado, la comparación de 3 vías no tiene una sobrecarga terrible: comparación entera sin ramificación de 3 vías . Ahora bien, si una rama adicional para verificar el resultado de la comparación contra 0 (igualdad) en cada nodo es menos sobrecarga que pagar ~ 3 comparaciones adicionales al final es otra pregunta. Probablemente no importe mucho. Pero creo que la comparación en sí debería haber sido de 3 valores, por lo que la decisión de utilizar los 3 resultados podría cambiarse.

Actualización: vea los comentarios a continuación sobre por qué creo que la comparación tridireccional es mejor en árboles, pero no necesariamente en matrices planas.

Answer 2

Los contenedores basados ​​en árboles solo requieren un estricto pedido total débil.

Ver https://www.sgi.com/tech/stl/StrictWeakOrdering.html

1. acceso de escritura

   El punto de inserción para mapas y conjuntos está determinado exclusivamente por una única búsqueda binaria, por ejemplo, lower_bound o upper_bound . La complejidad del tiempo de ejecución de la búsqueda binaria es O(log n)

2. acceso de lectura

   Lo mismo se aplica a la búsqueda: la búsqueda es mucho más eficiente que una exploración de igualdad lineal, precisamente porque la mayoría de los elementos no necesitan ser comparados. El truco es que los contenedores están ordenados.

El resultado es que la información de equality no necesita estar presente. Solo que los artículos pueden tener un orden equivalente .

En la práctica, esto solo significa menos restricciones en los tipos de elementos, menos trabajo para implementar los requisitos y un rendimiento óptimo en los escenarios de uso común. Siempre habrá compensaciones. (Por ejemplo, para grandes colecciones, las tablas hash (conjuntos no ordenados y mapas) a menudo son más eficientes. Tenga en cuenta que estos requieren elementos equatable , y emplean un esquema de hash para búsqueda rápida)