Quelles sont les conditions que doivent remplir les classes de clés std::map pour être des clés valides ?

Question

Je souhaite faire correspondre des objets d'une classe donnée à des objets d'une autre classe. La classe que je veux utiliser comme clé, cependant, n'a pas été écrite par moi et est une simple struct avec quelques valeurs. std::map ordonne son contenu, et je me demandais comment il le fait, et si n'importe quelle classe arbitraire peut être utilisée comme clé ou s'il y a un ensemble d'exigences (opérateurs et autres) qui doivent être définies.

Si c'est le cas, je pourrais créer un wrapper pour la classe qui implémente les opérateurs utilisés par map. J'ai juste besoin de savoir ce que je dois implémenter en premier, et aucune des références de la classe que j'utilise n'est disponible. trouvé en ligne les spécifier.

Answer 1

Il suffit que la clé soit copiable et cessible. L'ordre dans la carte est défini par le troisième argument du modèle (et l'argument du constructeur, s'il est utilisé). Cet ordre est défini par le troisième argument du modèle (et l'argument du constructeur, le cas échéant). Défauts à std::less<KeyType> qui, par défaut, est le < de l'opérateur, mais il n'est pas nécessaire d'utiliser les valeurs par défaut. Il suffit d'écrire une comparaison (de préférence sous la forme d'un objet fonctionnel) :

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

Notez qu'il doit définir un ordre strict, c'est-à-dire que si CmpMyType()( a, b ) retourne vrai, alors CmpMyType()( b, a ) doit renvoyer false, et si les deux renvoient false, les éléments sont considérés comme égaux (membres de la même classe d'équivalence). même classe d'équivalence).

Answer 2

Vous devez définir l'opérateur<, par exemple comme ceci :

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;

    // a are equal, compare b
    return ( l.b < r.b );
}

// 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 3

La réponse se trouve en fait dans la référence que vous citez, sous la description de l'argument du modèle "Compare".

La seule condition est que Compare (dont la valeur par défaut est less<Key> qui, par défaut, utilise operator< pour comparer des clés) doit être un "ordre faible strict".

Answer 4

Même chose que pour set : La classe doit avoir un ordre strict dans l'esprit de "moins que". Soit surcharger un operator< ou fournir un prédicat personnalisé. Deux objets quelconques a y b pour lequel !(a<b) && !(b>a) seront considérées comme égales.

Le conteneur de la carte conservera tous les éléments dans l'ordre prévu par cet ordre, ce qui permet d'obtenir un temps de consultation et d'insertion par valeur de clé de O(log n).