Wie funktioniert ein Vektor als Schlüssel intern in C ++?

14

Diese SO-Antwort besagt, dass die STL-Karte mit einem Vektor für den Schlüssel Vektor als Schlüssel verwendet werden kann. Wenn wir also einen Vektor als Schlüssel verwenden. Wie funktioniert das tatsächlich, da der Schlüssel eindeutig sein mapmuss? Wenn wir also einen anderen Vektor mit denselben Elementen einfügen, wird die Überprüfung auf doppelte Elemente für Elemente oder der Name des Vektors etwas angeben? Wie der Name des Arrays die Basisadresse darstellt. Ein Array kann also als Schlüssel verwendet werden, da die Basisadresse in diesem Fall als Schlüssel verwendet werden kann, aber was ist der Schlüssel im Fall eines Vektors. Wie funktioniert es intern?

Denn wenn ich den Namen des Vektors drucke, wird eine Fehlermeldung angezeigt

vector<int> v;
cout<<v; //error
c++ arrays dictionary vector stl Pulkit Bhatnagar
quelle
Was meinst du mit dem Drucken des Vektornamens?
Bart
has operators == and <Wie hilft das? Meine Frage war zu überprüfen, ob doppelte Elemente zugeordnet sind, um den Vektorschlüssel Element für Element zu vergleichen
Pulkit Bhatnagar
3
@PulkitBhatnagar Aber ... Niemand wird dich jemals zwingen, std::vectorals Schlüssel für zu verwenden std::map. Sie bezahlen für das, was Sie verwenden . Es kann getan werden, und vielleicht gibt es einige Anwendungsfälle dafür, aber mit Sicherheit können Sie die Datenstruktur Ihrer Wahl ändern. STL-Container sind so konzipiert, dass sie maximal vielseitig und in jeder Weise verwendbar sind, die der Benutzer jemals verwenden möchte.
Yksisarvinen
1
@PulkitBhatnagar Siehe zum Beispiel: Warum wird std :: map als rot-schwarzer Baum implementiert? .
Daniel Langr
1
@PulkitBhatnagar Speichert direkt. std::mapkopiert sowohl Schlüssel als auch Wert in sich. std::unordered_mapkann den Hash des Schlüssels speichern.
Yksisarvinen

Antworten:

9

Es gibt einen überladenen Operator <für die Klassenvorlage std :: vector.

template <class T, 
class Allocator>
bool operator< (const vector<T, Allocator>& x, const vector<T, Allocator>& y);

das basiert auf dem Standardalgorithmus std::lexicographical_compare.

Hier ist ein Demonstrationsprogramm.

#include <iostream>
#include <iomanip>
#include <vector>
#include <iterator>
#include <algorithm>

int main() 
{
    std::vector<int> v1 = { 1, 2 };
    std::vector<int> v2 = { 1, 2, 3 };
    std::vector<int> v3 = { 2 };

    std::cout << std::boolalpha << ( v1 < v2 ) << '\n';
    std::cout << std::lexicographical_compare( std::begin( v1 ), std::end( v1 ),
                                               std::begin( v2 ), std::end( v2 ) )
             << '\n';                                              

    std::cout << std::boolalpha << ( v1 < v3 ) << '\n';
    std::cout << std::lexicographical_compare( std::begin( v1 ), std::end( v1 ),
                                               std::begin( v3 ), std::end( v3 ) )
             << '\n';                                              

    std::cout << std::boolalpha << ( v2 < v3 ) << '\n';
    std::cout << std::lexicographical_compare( std::begin( v2 ), std::end( v2 ),
                                               std::begin( v3 ), std::end( v3 ) )
             << '\n';                                              

    return 0;
}

Seine Ausgabe ist

true
true
true
true
true
true

Die Klasse kann also als Schlüssel in der Karte verwendet werden.

Standardmäßig verwendet die Klassenvorlagenzuordnung das Funktionsobjekt std :: less, das wiederum den Operator <verwendet

template <class Key, class T, class Compare = less<Key>,
class Allocator = allocator<pair<const Key, T>>>
class map 
{
    //...
};

Es gibt jedoch keinen überladenen Operator << für die Klassenvorlage std :: vector.

Vlad aus Moskau
quelle
5
Ich sehe Ihre Antworten kürzlich in fast allen C ++ - Fragen zu SO. Ich weiß nicht, ob ich in meinem ganzen Leben jemals in der Lage sein werde, das zu erreichen, was Sie haben, aber ich werde mein Bestes geben. Vielen Dank für die Antwort
Pulkit Bhatnagar
8

Der Name eines Objekts und der Inhalt dieses Objekts sind immer nicht miteinander verbundene Dinge.

operator ==for std::vectorvergleicht zuerst die Länge der Vektoren und dann auch jedes seiner Elemente mit operator ==.

operator <vergleicht Elemente in Vektoren lexikographisch, dh es wird x[i] < y[i]für das erste ungleiche Element in Vektoren xund zurückgegeben y.

Dies sind die Anforderungen std::mapfür einen Typ, der als verwendet wird Key. Da std::vectorbeide erfüllt sind, kann es von as verwendet werden Key. Beachten Sie, dass für den von vector verwalteten Typ auch diese Operatoren überladen sein müssen, damit dies funktioniert (da std::vectordiese Operatoren ihre eigenen Operatoren implementieren müssen).

Yksisarvinen
quelle