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


Me pregunto por qué std::map y std::set utilizar 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);
     }
  }

Decir un map tiene dos objetos, con claves key1 y key2. Ahora queremos insertar otro objeto con clave key3.

Cuando usas std::less, el insert la función necesita llamar primero std::less::operator() con key1 y key3. Asumir std::less::operator()(key1, key3) devuelve falso. Tiene que llamar std::less::operator() de nuevo con las teclas conmutadas, 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.

Tenido std::map::insert usado compare, habría suficiente información para tomar la decisión correcta con solo una llamada.

Según el 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ía std::map y std::set usar algo como compare en lugar de std::less como el functor predeterminado para comparar claves?


32
2018-03-10 18:33


origen


Respuestas:


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 preguntó     yo para cambiar 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 para     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 de 3 vías sin ramificación. 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.


20
2018-05-04 03:11



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, p. 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 haga necesita ser comparado El truco es que los contenedores están ordenados.


El resultado es que el equality la información no necesita estar presente. Solo que los elementos pueden tener ordenamiento 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 colecciones grandes, hash-tables (desordenado conjuntos y mapas) a menudo son más eficientes. Tenga en cuenta que estos hacer exigir equatable elementos, y emplean un esquema de hash para búsqueda rápida)


17
2018-03-10 19:31