Wie kann ich std :: maps mit benutzerdefinierten Typen als Schlüssel verwenden?

73

Ich frage mich, warum ich STL-Maps nicht mit benutzerdefinierten Klassen verwenden kann. Wenn ich den folgenden Code kompiliere, wird die folgende kryptische Fehlermeldung angezeigt. Was heißt das? Warum passiert das nur bei benutzerdefinierten Typen? (Primitive Typen sind in Ordnung, wenn sie als Schlüssel verwendet werden.)

C: \ MinGW \ bin .. \ lib \ gcc \ mingw32 \ 3.4.5 ........ \ include \ c ++ \ 3.4.5 \ bits \ stl_function.h || In der Mitgliedsfunktion `bool std :: less <_Tp> :: operator () (const _Tp &, const _Tp &) const [mit _Tp = Class1] ': |

C: \ MinGW \ bin .. \ lib \ gcc \ mingw32 \ 3.4.5 ........ \ include \ c ++ \ 3.4.5 \ bits \ stl_map.h | 338 | instanziiert von `_Tp & std :: map <_Key, _Tp, _Compare, _Alloc> :: operator [] (const _Key &) [mit _Key = Class1, _Tp = int, _Compare = std :: less, _Alloc = std :: allocator>] '|

C: \ Benutzer \ Admin \ Dokumente \ dev \ sandbox \ sandbox \ sandbox.cpp | 24 | von hier aus instanziiert |

C: \ MinGW \ bin .. \ lib \ gcc \ mingw32 \ 3.4.5 ........ \ include \ c ++ \ 3.4.5 \ bits \ stl_function.h | 227 | Fehler: Keine Übereinstimmung für 'Operator <'in' __x <__y '| || === Build beendet: 1 Fehler, 0 Warnungen === |

#include <iostream>
#include <map>

using namespace std;

class Class1
{
public:
    Class1(int id);

private:
    int id;
};

Class1::Class1(int id): id(id)
{}

int main()
{
    Class1 c1(1);

    map< Class1 , int> c2int;
    c2int[c1] = 12;

    return 0;
}
Unbekannt
quelle
Mögliches Duplikat von C ++ unordered_map unter Verwendung eines benutzerdefinierten Klassentyps als Schlüssel
Ciro Santilli 法轮功 冠状 病 六四 事件 法轮功

Antworten:

150

Sie müssen nicht haben zu definieren , operator<für Ihre Klasse, eigentlich. Sie können auch eine Vergleichsfunktionsobjektklasse dafür erstellen und diese zur Spezialisierung verwenden std::map. So erweitern Sie Ihr Beispiel:

struct Class1Compare
{
   bool operator() (const Class1& lhs, const Class1& rhs) const
   {
       return lhs.id < rhs.id;
   }
};

std::map<Class1, int, Class1Compare> c2int;

Es kommt einfach so vor, dass der Standardwert für den dritten Vorlagenparameter von std::maplautet std::less, der an operator<die für Ihre Klasse definierte delegiert wird (und fehlschlägt, wenn keine vorhanden ist). Aber manchmal möchten Sie, dass Objekte als Kartenschlüssel verwendet werden können, aber Sie haben tatsächlich keine aussagekräftige Vergleichssemantik, und deshalb möchten Sie die Leute nicht verwirren, indem Sie operator<Ihre Klasse nur dafür bereitstellen . Wenn dies der Fall ist, können Sie den obigen Trick verwenden.

Ein weiterer Weg, um dasselbe zu erreichen, ist die Spezialisierung std::less:

namespace std
{
    template<> struct less<Class1>
    {
       bool operator() (const Class1& lhs, const Class1& rhs) const
       {
           return lhs.id < rhs.id;
       }
    };
}

Dies hat den Vorteil, dass es std::map"standardmäßig" ausgewählt wird und Sie sonst keinen operator<Client-Code verwenden.

Pavel Minaev
quelle
5
Ich würde vorschlagen, den beiden Funktionen ein const-Schlüsselwort hinzuzufügen.
Diomidis Spinellis
Vielleicht lohnt es sich, friendmit der Struktur weniger zu arbeiten, sonst sehe ich es als kompromittierte Kapselung.
SkyWalker
Die Struktur mit Vorlagen sollte mit einem Semikolon abgeschlossen werden, da sonst Kompilierungsfehler auftreten. Leider konnte ich dies aufgrund der geringen Anzahl geänderter Zeichen nicht mit einer Bearbeitung beheben
Ident
Aber warum setzen Sie struct less info std?
Vladimir Tsyshnatiy
Es ist schon drin std. Dies ist nur eine Spezialisierung davon.
Pavel Minaev
29

Standardmäßig std::map(und std::set) verwenden operator<, um die Sortierung zu bestimmen. Daher müssen Sie operator<für Ihre Klasse definieren .

Zwei Objekte werden als gleichwertig angesehen if !(a < b) && !(b < a) .

Wenn Sie aus irgendeinem Grund einen anderen Komparator verwenden möchten, kann das dritte Vorlagenargument von mapbeispielsweise geändert werden std::greater.

GManNickG
quelle
3
Tatsächlich können Sie den Komparator auf fast jede Funktion mit zwei Argumenten ändern.
xtofl
17

Sie müssen operator <für die Klasse1 definieren .

Map muss die Werte mit dem Operator <vergleichen und daher müssen Sie dasselbe angeben, wenn benutzerdefinierte Klassen als Schlüssel verwendet werden.

class Class1
{
public:
    Class1(int id);

    bool operator <(const Class1& rhs) const
    {
        return id < rhs.id;
    }
private:
    int id;
};
aJ.
quelle
1
Es braucht keinen Operator <; es wird lediglich standardmäßig verwendet. Siehe die Antwort von GMan oder Pavel.
xtofl
4
class key
{
    int m_value;
public:
    bool operator<(const key& src)const
    {
        return (this->m_value < src.m_value);
    }

};
int main()
{
    key key1;
    key key2;
    map<key,int> mymap;
    mymap.insert(pair<key,int>(key1,100));
    mymap.insert(pair<key,int>(key2,200));
    map<key,int>::iterator iter=mymap.begin();
    for(;iter!=mymap.end();++iter)
    {
        cout<<iter->second<<endl;
    }


}
Kaushal
quelle
6
Willkommen bei StackOverflow! Bitte fügen Sie Ihrer Antwort einige Erklärungen hinzu.
Aurasphere
3

Schlüssel müssen vergleichbar sein, aber Sie haben keine operator<für Ihre benutzerdefinierte Klasse geeignete definiert .

entspannen
quelle
2

Ich möchte ein wenig auf Pavel Minaevs Antwort eingehen , die Sie lesen sollten, bevor Sie meine Antwort lesen. Beide von Pavel vorgestellten Lösungen werden nicht kompiliert, wenn das zu vergleichende Mitglied (wie idim Code der Frage) privat ist. In diesem Fall gibt VS2013 für mich den folgenden Fehler aus:

Fehler C2248: 'Class1 :: id': Zugriff auf privates Mitglied in Klasse 'Class1' nicht möglich

Wie von SkyWalker in den Kommentaren zu Pavel's Antwort erwähnt, friendhilft die Verwendung einer Erklärung. Wenn Sie sich über die richtige Syntax wundern, finden Sie hier:

class Class1
{
public:
    Class1(int id) : id(id) {}

private:
    int id;
    friend struct Class1Compare;      // Use this for Pavel's first solution.
    friend struct std::less<Class1>;  // Use this for Pavel's second solution.
};

Code auf Ideone

Wenn Sie jedoch eine Zugriffsfunktion für privates Mitglied, zum Beispiel getId()für id, wie folgt:

class Class1
{
public:
    Class1(int id) : id(id) {}
    int getId() const { return id; }

private:
    int id;
};

dann können Sie es anstelle einer friendDeklaration verwenden (dh Sie vergleichen lhs.getId() < rhs.getId()). Seit C ++ 11 können Sie auch einen Lambda-Ausdruck für Pavel's erste Lösung verwenden, anstatt eine Objektklasse für Komparatorfunktionen zu definieren. Alles zusammen könnte der Code wie folgt geschrieben werden:

auto comp = [](const Class1& lhs, const Class1& rhs){ return lhs.getId() < rhs.getId(); };
std::map<Class1, int, decltype(comp)> c2int(comp);

Code auf Ideone

hupen
quelle
1

Die richtige Lösung besteht darin, sich std::lessauf Ihre Klasse / Struktur zu spezialisieren.

• Grundsätzlich werden Karten in cpp als binäre Suchbäume implementiert.

  1. BSTs vergleichen Elemente von Knoten, um die Organisation des Baums zu bestimmen.
  2. Knoten, deren Element weniger als das des übergeordneten Knotens vergleicht, werden links vom übergeordneten Knoten platziert, und Knoten, deren Elemente größer als das Element des übergeordneten Knotens sind, werden rechts platziert. dh

Für jeden Knoten node.left.key <node.key <node.right.key

Jeder Knoten in der BST enthält Elemente und bei Karten seinen SCHLÜSSEL und einen Wert. Und Schlüssel sollen bestellt werden. Weitere Informationen zur Kartenimplementierung: Der Kartendatentyp .

Bei cpp-Maps sind Schlüssel die Elemente der Knoten, und Werte sind nicht an der Organisation des Baums beteiligt, sondern lediglich ergänzende Daten.

Das bedeutet, dass Schlüssel mit std::lessoder kompatibel sein sollten, operator<damit sie organisiert werden können. Bitte überprüfen Sie die Kartenparameter .

Andernfalls müssen Sie, wenn Sie einen benutzerdefinierten Datentyp als Schlüssel verwenden, eine vollständige Vergleichssemantik für diesen Datentyp angeben.

Lösung : Spezialisieren std::less:

Der dritte Parameter in der Kartenvorlage ist optional und wird an std::lessFolgendes delegiert operator<:

Erstellen Sie also einen neuen std::lessfür Ihren benutzerdefinierten Datentyp. Nun ist diese neue std::lesswird abgeholt werden std::mapstandardmäßig aktiviert .

namespace std
{
    template<> struct  less<MyClass>
    {
        bool operator() (const MyClass& lhs, const MyClass& rhs) const
        {
            return lhs.anyMemen < rhs.age;
        }
    };

}

Hinweis: Sie müssen std::lessfür jeden benutzerdefinierten Datentyp einen speziellen Datentyp erstellen (wenn Sie diesen Datentyp als Schlüssel für CPP-Maps verwenden möchten).

Schlechte Lösung: Überladung operator<für Ihren benutzerdefinierten Datentyp. Diese Lösung funktioniert auch, ist jedoch sehr schlecht, da der Operator <für Ihren Datentyp / Ihre Datensklasse universell überlastet wird. Dies ist in Client-Szenarien unerwünscht.

Bitte überprüfen Sie die Antwort von Pavel Minaev

BreakBadSP
quelle