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

Question

Quiero asignar 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 simple struct 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.

Si es 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 I found online los especifica.

Answer 1

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 predetermina a std::less<KeyType>, que se predetermina al operador <, pero no es necesario utilizar los valores predeterminados. Sólo tiene que escribir 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 ) vuelve verdad, entonces CmpMyType()(b, a) debe devolver falso, y si tanto return false, el los elementos se consideran iguales (miembros de la misma clase de equivalencia ).

Answer 2

Igual que para set: La clase debe tener un orden estricto en el espíritu de "menor que". O bien, sobrecarga un operator< apropiado o proporciona un predicado personalizado. Dos objetos a y b para los cuales !(a<b) && !(b>a) se considerarán 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.

Answer 3

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<Key>, que por defecto es el uso de operator< para comparar claves) debe ser un "ordenamiento débil estricto".

Answer 4

es necesario definir el operador <, por ejemplo como este:

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 (l.a < r.a) && (l.b < r.b); 
} 

// Better brute force. 
bool operator<(const A& l, const A& r) 
{ 
    if (l.a < r.a) return true; 
    if (l.a > r.a) return false; 

    // Otherwise a are equal 
    if (l.b < r.b) return true; 
    if (l.b > r.b) 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 (l.a < r.a) || 
      ((l.a == r.a) && (l.b < r.b)); 
}