webentwicklung-frage-antwort-db.com.de

Welche Anforderungen müssen std :: map-Schlüsselklassen erfüllen, um gültige Schlüssel zu sein?

Ich möchte Objekte einer bestimmten Klasse Objekten einer anderen zuordnen. Die Klasse, die ich als Schlüssel verwenden möchte, wurde jedoch nicht von mir geschrieben und ist ein einfaches struct mit einigen Werten. std :: map ordnet den Inhalt an und ich habe mich gefragt, wie es funktioniert und ob eine beliebige Klasse als Schlüssel verwendet werden kann oder ob eine Reihe von Anforderungen (Operatoren und was nicht) definiert werden müssen.

In diesem Fall könnte ich einen Wrapper für die Klasse erstellen, die die Operatoren implementiert, die map verwendet. Ich muss nur wissen, was ich zuerst implementieren muss, und keine der Referenzen für die Klasse I online gefunden spezifizieren sie.

68
Kian

Der Schlüssel muss nur kopierbar und zuweisbar sein. Die Reihenfolge innerhalb der Map wird durch das dritte Argument der Vorlage (und das Argument des Konstruktors, falls verwendet) definiert. Dies Standardeinstellungen bis std::less<KeyType>, Wobei der Standardwert < Ist, die Standardeinstellungen jedoch nicht verwendet werden müssen. Schreiben Sie einfach einen Vergleichsoperator (vorzugsweise als funktionales Objekt):

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

Beachten Sie, dass eine strikte Reihenfolge definiert werden muss. Wenn CmpMyType()( a, b ) true zurückgibt, muss CmpMyType()( b, a ) false zurückgeben. Wenn beide false zurückgeben, werden die Elemente als gleich angesehen (Mitglieder derselben Äquivalenz) Klasse).

62
James Kanze

Sie müssen den Operator <wie folgt definieren:

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 ));
}
22
BЈовић

Die Antwort befindet sich in der Referenz, die Sie verknüpfen, unter der Beschreibung des Vorlagenarguments "Compare".

Die einzige Voraussetzung ist, dass Compare (standardmäßig less<Key>, Standardmäßig operator< Zum Vergleichen von Schlüsseln verwendet) eine "strikte schwache Reihenfolge" aufweist.

3
Nemo

Dasselbe wie für set: Die Klasse muss eine strikte Reihenfolge im Sinne von "kleiner als" haben. Überladen Sie entweder ein geeignetes operator< Oder geben Sie ein benutzerdefiniertes Prädikat an. Zwei beliebige Objekte a und b, für die !(a<b) && !(b>a) als gleich gelten.

Der Kartencontainer behält tatsächlich alle Elemente in der Reihenfolge bei, die in dieser Reihenfolge angegeben ist. Auf diese Weise können Sie die O (log n) -Such- und Einfügungszeit nach Schlüsselwert erreichen.

2
Kerrek SB