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

las 7 claves musicales

Question

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.

Answer 1

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 usa el operator< para comparar claves) debe ser un "orden débil estricto".

Answer 2

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 !(a<b) && !(b>a) 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.

Answer 3

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 ( 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 ));
}

Answer 4

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<KeyType> , 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).