Apa perbedaan antara std :: multimap <key, value> dan std :: map <key, std :: set <value>>

Jawaban:

52

Multimap menyimpan pasangan (kunci, nilai) di mana kunci dan nilai dapat muncul beberapa kali.

Hanya map<key, set<value>>akan menyimpan setiap nilai satu kali untuk kunci tertentu. Untuk melakukan itu, ia harus dapat membandingkan nilainya, bukan hanya kuncinya.

Itu bergantung pada aplikasi Anda jika nilai yang dibandingkan sama setara, atau jika Anda tetap ingin menyimpannya secara terpisah. Mungkin mereka berisi bidang yang berbeda tetapi tidak mengambil bagian dalam perbandingan untuk himpunan.

Bo Persson
sumber
5
Jadi, std :: multimap <key, value> seperti std :: map <key, std :: multiset <value>>, perbedaan di antara mereka adalah nilai-nilai yang kemudian diurutkan. Apakah itu benar?
大 宝剑
2
Tidak, std::multimap<key, value>memungkinkan kunci yang sama muncul beberapa kali sedangkan std::map<key, whatever>membutuhkan keunikan key.
Yixing Liu
75

A std::mapadalah wadah asosiatif, yang memungkinkan Anda memiliki kunci unik yang terkait dengan nilai jenis Anda. Sebagai contoh,

void someFunction()
{
    typedef std::map<std::string, int> MapType;
    MapType myMap;

    // insertion
    myMap.insert(MapType::value_type("test", 42));
    myMap.insert(MapType::value_type("other-test", 0));

    // search
    auto it = myMap.find("test");
    if (it != myMap.end())
        std::cout << "value for " << it->first << " is " << it->second << std::endl;
    else
        std::cout << "value not found" << std::endl;
}

A std::multimapsama dengan a std::map, tetapi kunci Anda tidak unik lagi. Oleh karena itu, Anda dapat menemukan berbagai item daripada hanya menemukan satu item unik. Sebagai contoh,

void someFunction()
{
    typedef std::multimap<std::string, int> MapType;
    MapType myMap;

    // insertion
    myMap.insert(MapType::value_type("test", 42));
    myMap.insert(MapType::value_type("test", 45));
    myMap.insert(MapType::value_type("other-test", 0));

    // search
    std::pair<auto first, auto second> range = myMap.equal_range("test");
    for (auto it = range.first; it != range.second; ++it)
        std::cout << "value for " << it->first << " can be " << it->second << std::endl;
}

Ini std::setseperti sebuah std::map, tetapi tidak menyimpan kunci yang terkait dengan suatu nilai. Ini hanya menyimpan jenis kunci, dan meyakinkan Anda bahwa itu unik dalam set.

Anda juga memiliki std::multiset, yang mengikuti pola yang sama.

Semua kontainer ini menyediakan akses O (log (n)) dengan find / equal_range-nya.

typedef
sumber
6
Dalam fungsi multimap, baris std::pair<auto first, auto second> range = myMap.equal_range("test");ini tidak berfungsi, karena error: 'auto' not allowed in template argument. Gunakan const auto range = myMap.equal_range("test")sebagai gantinya.
vancexu
2
jenis peta? Bukankah seharusnya MapType di baris 4?
lolololol ol
tidak yakin siapa yang pertama, tapi satu jelas copy paste dari yang lain: cppbuzz.com/What-is-difference-between-map-and-multimap
largest_prime_is_463035818
1
ahah, cppbuzz mengikis StackOverflow atau apa ?, Saya menulis jawaban ini sendiri bertahun-tahun yang lalu ketika saya masih melakukan coding harian di c ++. Dan memang ada kesalahan ketik baris 4 makasih @lololololol
typedef
1
(dan salin / tempelnya gagal, mereka bahkan tidak menampilkan tipe di template std :: deklarasi peta: std :: map <std :: string, int>)
typedef
13
map::insert

Karena mappenampung tidak mengizinkan nilai kunci duplikat, operasi penyisipan memeriksa setiap elemen yang dimasukkan apakah elemen lain sudah ada dalam penampung dengan nilai kunci yang sama, jika demikian, elemen tersebut tidak disisipkan dan nilai yang dipetakan tidak diubah dengan cara apa pun.

di samping itu

multimap::insert 

dapat memasukkan sejumlah item dengan kunci yang sama.

http://www.cplusplus.com/reference/stl/map/
http://www.cplusplus.com/reference/stl/multimap/

Luka Rahne
sumber
Tautan bagus tentang perbedaan dan cara kerjanya secara internal. tautan
Rndp13
10

Yang terakhir mensyaratkan bahwa nilai-nilai dapat diurutkan (baik melalui operator<atau fungsi pembanding), yang pertama tidak.

Björn Pollex
sumber
Akan tampak operator <bekerja sama pada peta atau multimap? en.cppreference.com/w/cpp/container/map/operator_cmp
johnbakers
Ya, tetapi jawaban saya mengacu pada urutan nilai. Misalkan Anda memiliki tipe Tyang tidak ada pemesanan. Anda dapat menggunakannya untuk membuat file std::multimap<U, T>, tetapi Anda tidak dapat menggunakannya untuk membuat file std::map<U, std::set<T> >.
Björn Pollex