Jak wektor jako klucz działa wewnętrznie w C ++?

Ta odpowiedź SO mówi, że mapa STL z wektorem dla klucza wektor może być używany jako klucz. Więc kiedy używamy wektora jako klucza. Jak to faktycznie działa, skoro klucz musi być unikalny, więc kiedy wstawimy inny wektor z tymi samymi elementami, czy mapsprawdzanie duplikatu elementu po elemencie lub nazwa wektora coś określi? Podobnie jak nazwa tablicy reprezentuje adres podstawowy. Tak więc tablica może być używana jako klucz, ponieważ adres podstawowy może być użyty jako klucz w tym przypadku, ale jaki jest klucz w przypadku wektora. Jak to działa wewnętrznie.

Ponieważ kiedy drukuję nazwę wektora, pojawia się błąd

vector<int> v;
cout<<v; //error

c++ arrays dictionary vector stl Pulkit Bhatnagar
źródło

Co masz na myśli, drukując nazwę wektora?

Bart

has operators == and <jak to pomaga? moim pytaniem było sprawdzenie, czy zduplikowane elementy

odwzorują

@PulkitBhatnagar Ale ... Nikt nigdy nie zmusi cię do użycia std::vectorjako klucza std::map. Płacisz za to, czego używasz . Można to zrobić i być może istnieją do tego pewne przypadki użycia, ale z pewnością możesz zmienić wybraną strukturę danych. Kontenery STL są zaprojektowane tak, aby były maksymalnie wszechstronne i użyteczne w dowolny sposób, w jaki użytkownik może chcieć z nich korzystać.

Yksisarvinen

@PulkitBhatnagar Zobacz na przykład: Dlaczego std :: map jest implementowany jako czerwono-czarne drzewo? .

Daniel Langr

@PulkitBhatnagar Sklepy bezpośrednio. std::mapskopiuje zarówno klucz, jak i wartość do siebie. std::unordered_mapmoże przechowywać skrót klucza.

Yksisarvinen

Odpowiedzi:

Istnieje przeciążony operator <dla szablonu klasy std :: vector.

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

oparty na standardowym algorytmie std::lexicographical_compare.

Oto program demonstracyjny.

#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;
}

Jego wydajność to

true
true
true
true
true
true

Tak więc klasa może być używana jako klucz na mapie.

Domyślnie mapa szablonów klas używa obiektu funkcji std :: less, który z kolei używa operatora <

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

Jednak nie ma przeciążonego operatora << dla szablonu klasy std :: vector.

Vlad z Moskwy
źródło

Widzę twoje odpowiedzi ostatnio w prawie wszystkich pytaniach C ++ na SO, nie wiem, czy w całym moim życiu kiedykolwiek będę w stanie osiągnąć to, co masz, ale postaram się jak najlepiej. Dzięki za odpowiedź

Pulkit Bhatnagar

Nazwa obiektu i treść tego obiektu są zawsze rzeczami niepowiązanymi.

operator ==for std::vectornajpierw porównuje długość wektorów, a następnie używa każdego z jego elementów operator ==.

operator <porównuje elementy w wektorze leksykograficznie, tzn. zwraca x[i] < y[i]pierwszy nierównoprawny element w wektorach xi y.

Są to wymagania std::mapdla typu używanego jako Key. Ponieważ std::vectorspełnia oba, może być używany przez as Key. Zauważ, że typ zarządzany przez wektor musi również mieć przeciążonych operatorów, aby to działało (ponieważ std::vectorpolega na tym, że operatorzy wdrażają własne operatory).

Yksisarvinen
źródło