¿Qué requisitos deben cumplir las clases de claves std :: map para que sean claves válidas?

Quiero mapear objetos de una clase dada a objetos de otro. La clase que quiero usar como clave, sin embargo, no fue escrita por mí y es una struct simple con algunos valores. std :: map ordena sus contenidos, y me preguntaba cómo lo hace, y si se puede utilizar cualquier clase arbitraria como clave o si hay un conjunto de requisitos (operadores y qué no) que deben definirse.

De ser así, podría crear un contenedor para la clase que implementa los usos del mapa del operador. Solo necesito saber qué debo implementar primero, y ninguna de las referencias para la clase que encontré en línea los especifica.

Todo lo que se requiere de la clave es que sea copiable y asignable. El orden dentro del mapa está definido por el tercer argumento de la plantilla (y el argumento para el constructor, si se usa). Esto se establece de manera predeterminada en std::less , que por defecto es el operador < , pero no es necesario utilizar los valores predeterminados. Simplemente escriba un operador de comparación (preferiblemente como un objeto funcional):

 struct CmpMyType { bool operator()( MyType const& lhs, MyType const& rhs ) const { // ... } }; 

Tenga en cuenta que debe definir un orden estricto, es decir, si CmpMyType()( a, b ) devuelve verdadero, entonces CmpMyType()( b, a ) debe devolver falso, y si ambos devuelven falso, los elementos se consideran iguales (miembros del misma clase de equivalencia).

Necesita definir el operador <, por ejemplo, de esta manera:

 struct A { int a; std::string b; }; // Simple but wrong as it does not provide the strict weak ordering. // As A(5,"a") and A(5,"b") would be considered equal using this function. bool operator<(const A& l, const A& r ) { return ( la < ra ) && ( lb < rb ); } // Better brute force. bool operator<(const A& l, const A& r ) { if ( la < ra ) return true; if ( la > ra ) return false; // Otherwise a are equal if ( lb < rb ) return true; if ( lb > rb ) return false; // Otherwise both are equal return false; } // This can often be seen written as bool operator<(const A& l, const A& r ) { // This is fine for a small number of members. // But I prefer the brute force approach when you start to get lots of members. return ( la < ra ) || (( la == ra) && ( lb < rb )); } 

La respuesta está en realidad en la referencia que vincula, bajo la descripción del argumento de la plantilla “Comparar”.

El único requisito es que Compare (que por defecto es less , que usa el operator< para comparar claves) debe ser un "orden débil estricto".

Lo mismo que para el set : la clase debe tener un orden estricto en el espíritu de “menor que”. O bien, sobrecargar un operator< o proporcionar un predicado personalizado. ¡Cualquier dos objetos a y b para los cuales !(aa) serán considerados iguales.

El contenedor del mapa realmente mantendrá todos los elementos en el orden proporcionado por ese orden, que es cómo puede lograr la búsqueda O (log n) y el tiempo de inserción por valor clave.