Bagaimana vektor sebagai kunci bekerja secara internal di C ++?

14

Jawaban SO ini mengatakan bahwa STL Map dengan Vector for Key , vektor dapat digunakan sebagai kunci. Jadi ketika kita menggunakan vektor sebagai kunci. Bagaimana cara kerjanya karena kunci harus unik sehingga ketika kita memasukkan vektor lain dengan elemen yang sama akankah mapmemeriksa duplikat elemen demi elemen atau nama vektor menentukan sesuatu? Seperti nama array mewakili alamat basis. Jadi array dapat digunakan sebagai kunci karena alamat dasar dapat digunakan sebagai kunci dalam kasus ini, tetapi apa kunci dalam kasus vektor. Bagaimana cara kerjanya secara internal.

Karena ketika saya mencetak nama vektor, saya mendapatkan kesalahan

vector<int> v;
cout<<v; //error
c++ arrays dictionary vector stl Pulkit Bhatnagar
sumber
Apa yang Anda maksud dengan mencetak nama vektor?
Bart
has operators == and <bagaimana itu membantu? pertanyaan saya adalah untuk memeriksa elemen duplikat akan memetakan membandingkan elemen kunci vektor dengan elemen
Pulkit Bhatnagar
3
@ PulkitBhatnagar Tapi ... Tidak ada yang akan memaksa Anda untuk menggunakan std::vectorkunci std::map. Anda membayar apa yang Anda gunakan . Ini bisa dilakukan, dan mungkin ada beberapa kasus penggunaan untuk itu, tetapi yang paling pasti Anda dapat mengubah struktur data pilihan Anda. Wadah STL dirancang agar fleksibel dan dapat digunakan dengan cara apa pun yang diinginkan pengguna untuk menggunakannya.
Yksisarvinen
1
@PulkitBhatnagar Lihat, misalnya, Mengapa std :: map diimplementasikan sebagai pohon merah-hitam? .
Daniel Langr
1
@PulkitBhatnagar Stores secara langsung. std::mapakan menyalin kunci dan nilai ke dalam dirinya sendiri. std::unordered_mapdapat menyimpan hash kunci.
Yksisarvinen

Jawaban:

9

Ada operator kelebihan <untuk template kelas std :: vector.

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

yang didasarkan pada algoritma standar std::lexicographical_compare.

Ini adalah program demonstratif.

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

Outputnya adalah

true
true
true
true
true
true

Sehingga kelas dapat digunakan sebagai kunci dalam peta.

Secara default peta templat kelas menggunakan objek fungsi std :: less yang pada gilirannya menggunakan operator <

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

Namun tidak ada operator kelebihan << untuk std template class :: vektor.

Vlad dari Moskow
sumber
5
Saya melihat jawaban Anda baru-baru ini di hampir semua pertanyaan C ++ di SO, saya tidak tahu apakah sepanjang hidup saya, saya akan pernah dapat mencapai apa yang Anda miliki tetapi saya akan mencoba yang terbaik. Terima kasih atas jawabannya
Pulkit Bhatnagar
8

Nama suatu benda dan isi benda itu selalu merupakan hal yang tidak berkaitan.

operator ==karena std::vectorpertama-tama akan membandingkan panjang vektor dan kemudian masing-masing elemen itu menggunakan operator ==juga.

operator <membandingkan elemen dalam vektor secara leksikografis, yaitu mengembalikan x[i] < y[i]untuk elemen tidak sama pertama dalam vektor xdan y.

Ini adalah persyaratan std::mapuntuk tipe yang digunakan Key. Karena std::vectormemenuhi keduanya, dapat digunakan oleh sebagai Key. Perhatikan bahwa jenis yang dikelola oleh vektor juga harus membuat operator ini kelebihan beban agar dapat berfungsi (karena std::vectorbergantung pada operator tersebut untuk mengimplementasikan operatornya sendiri).

Yksisarvinen
sumber