Wie kann ich das einfügen einer Struktur, die als Schlüssel in einer map?

Einer std::map Schlüssel gespeichert werden intern in einem binären Suchbaum. Um für Schlüssel und suchte in einer binären Suche Baum, Sie müssen vergleichbar sein. Zum Beispiel, eine Anforderung in einem binären Suchbaum ist, dass eine Links-Kind-Schlüssel ist weniger als die übergeordnete Schlüssel und einem rechten Kind-Schlüssel ist größer als der übergeordneten Schlüssel. Allerdings, wenn die Tasten nicht vergleichbar sind, wie sollen wir sagen, ob die Kinder sich mehr oder weniger als die Eltern? Wir können nicht die form eines Baumes und daher die std::map funktioniert nicht mit diesen Typen.

Müssen Sie einfach zu definieren, der kleiner-als-operator wie folgt:

bool operator<(const node& n1, const node& n2)
{
    return n1.test < n2.test;
}

Dies muss auch ein Freund sein von Ihren Knoten struct, wenn die "test" - Daten Mitglied ist private (Es ist öffentlich nun da Knoten ist derzeit ein struct). Aber wahrscheinlich würde ich es so machen:

#include <map>

class node
{
    public:
        int getTest() const { return _test; }
        void setTest(int test) { _test = test; }
    private:
        int _test;
};

bool operator<(const node& n1, const node& n2)
{
    return n1.getTest() < n2.getTest();
}

int main()
{
    std::map<node,bool> foo;
    node n;
    n.setTest(25);

    foo[n] = true;

    return 0;
}

Hier ist, wie zu Lesen die Fehlermeldungen:

/usr/lib/gcc/i686-pc-linux-gnu/4.3.4/include/g++-v4/bits/stl_function.h: In member function ‘bool std::less<_Tp>::operator()(const _Tp&, const _Tp&) const [with _Tp = node]’:
/usr/lib/gcc/i686-pc-linux-gnu/4.3.4/include/g++-v4/bits/stl_tree.h:1141:   instantiated from ‘std::pair<typename std::_Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::iterator, bool> std::_Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::_M_insert_unique(const _Val&) [with _Key = node, _Val = std::pair<const node, bool>, _KeyOfValue = std::_Select1st<std::pair<const node, bool> >, _Compare = std::less<node>, _Alloc = std::allocator<std::pair<const node, bool> >]’
/usr/lib/gcc/i686-pc-linux-gnu/4.3.4/include/g++-v4/bits/stl_map.h:469:   instantiated from ‘std::pair<typename std::_Rb_tree<_Key, std::pair<const _Key, _Tp>, std::_Select1st<std::pair<const _Key, _Tp> >, _Compare, typename _Alloc::rebind<std::pair<const _Key, _Tp> >::other>::iterator, bool> std::map<_Key, _Tp, _Compare, _Alloc>::insert(const std::pair<const _Key, _Tp>&) [with _Key = node, _Tp = bool, _Compare = std::less<node>, _Alloc = std::allocator<std::pair<const node, bool> >]’
prog.cpp:15:   instantiated from here
/usr/lib/gcc/i686-pc-linux-gnu/4.3.4/include/g++-v4/bits/stl_function.h:230: error: no match for ‘operator<’ in ‘__x < __y’

Erste, ignorieren wir die meisten der " instanziiert von Linien, weil Sie nur darüber zu reden, wie die Vorlagen bekam ausgebaut. Das wichtige ist das Letzte, was unsere source-code, weil es uns sagt, wo der Fehler ausgelöst wurde. Natürlich wussten wir das sowieso, also werden wir überspringen das auch. Wir ignorieren auch den Pfad zu der Bibliothek-header in Frage, weil wir nicht wirklich, wie der compiler speichert seine Sachen.

stl_function.h: In member function ‘bool std::less<_Tp>::operator()(const _Tp&, const _Tp&) const [with _Tp = node]’:
stl_function.h:230: error: no match for ‘operator<’ in ‘__x < __y’

Also... unser code indirekt fordert ‘bool std::less<_Tp>::operator()(const _Tp&, const _Tp&) const [with _Tp = node]’ oder wenn wir tatsächlich tun, dass die substitution, die ‘bool std::less<node>::operator()(const node&, const node&) const’. Und das ist ein problem, weil es no match for ‘operator<’ in ‘__x < __y’.

__x und __y sind Variablen, die innerhalb der std::less Umsetzung (Sie sollten in der Lage sein, zu erraten, dass viel). Von den Namen, können wir vermuten (und wenn wir studiert hatten, die standard-Bibliothek, die wir so kennen), dass std::less ist eine template-Funktion vergleicht zwei Dinge der gleichen Art und gibt an, ob der erste kleiner als der zweite.

Wie tut es das? Mithilfe der operator< natürlich. Also das ist, was wir tun müssen, um das problem zu lösen: es sagt, dass die operator< gibt es nicht für das, was verglichen wird, also müssen wir es geben. Was wird verglichen? nodes, natürlich. So definieren wir operator< für unsere Klasse.

Warum tut er das? Damit können wir Funktionen schreiben, annehmen ein-Vergleich-der Betrieb als argument (entweder ein template-argument, oder ein Laufzeit-parameter - aber die erstere ist viel häufiger), und pass std::less. Das ist der Grund für std::less's Existenz: es stellt sich die Handlung des Vergleichens, die Dinge in einer Funktion, und die eigentlichen Funktionen sind etwas mehr nützlich.

Wie ist dass relevant? Weil, wie die anderen gesagt haben, std::map ist eigentlich vorbei std::less als argument. Es ist eigentlich ein Standard-argument, um die std::map Vorlage, die verwendet wird, zu vergleichen Elemente. Nachdem alle Teil der Schnittstelle einer Karte ist, dass jeder Schlüssel einmalig ist. Wie willst du das überprüfen Schlüssel für die Einzigartigkeit, wenn Sie nicht können Sie vergleichen? Zugegeben, technisch würden Sie nur haben, um Sie zu vergleichen, für Gleichheit, für diese zu arbeiten. Aber es stellt sich heraus, dass in der Lage, um die Reihenfolge der Tasten macht es möglich, zu erstellen, die eine viel mehr effiziente Datenstruktur. (Sie würde das kennen, wenn Sie tatsächlich nahm Kurse in der Universität über das Programmieren und CS.)

Warum war da nicht ein problem mit int? Sie sollten in der Lage sein, zu erraten, von jetzt: operator< bereits natürlich funktioniert für ints. Aber Sie müssen sagen, C++, wie es für jeden Anwender-Typen, weil Sie vielleicht etwas anderes im Sinn.