multimap — o cheie cu mai multe valori

Ce este un multimap și de ce diferă de map

Un map leagă fiecare cheie de o singură valoare. Dacă inserezi din nou aceeași cheie, vechea valoare se pierde sau este ignorată. Bun pentru „CNP → nume”, unde un CNP are un singur nume.

Dar ce faci când o cheie are mai multe valori? „autor → cărți”, „oraș → locuitori”, „cuvânt → paginile unde apare”. Aici intră multimap: păstrează toate perechile, chiar dacă au aceeași cheie. Stă tot în <map>, este tot ordonat crescător după cheie și are tot operații în O(log n).

Diferența cheie: pentru că o cheie are mai multe valori, multimap NU are operator[]. Nu ai cum să scrii m[cheie] — care dintre valori ar trebui să returneze? Adaugi mereu cu insert({cheie, val}).

Exemplu pas cu pas

Construim un index invers: cuvânt → paginile pe care apare. Inserăm pe rând:

• insert({"alfa", 1}) → alfa apare la pagina 1
• insert({"beta", 2}) → beta la pagina 2
• insert({"alfa", 5}) → alfa are acum două valori: 1 și 5
• insert({"alfa", 9}) → alfa are trei: 1, 5, 9

Structura ține toate perechile, grupate și ordonate după cheie:

alfa -> 1
alfa -> 5
alfa -> 9
beta -> 2

Acum count("alfa") întoarce 3, iar count("gama") întoarce 0. Ca să vezi toate paginile lui alfa, ceri intervalul lor cu equal_range("alfa").

Implementare C++

equal_range(cheie) întoarce o pereche {first, second}: first arată spre prima apariție a cheii, second arată imediat după ultima. Parcurgi de la first până la second (interval semideschis, ca la begin/end).

#include <iostream>
#include <map>
#include <string>
using namespace std;

int main() {
    multimap<string, int> index;

    // insert: o cheie poate primi mai multe valori
    index.insert({"alfa", 1});
    index.insert({"beta", 2});
    index.insert({"alfa", 5});
    index.insert({"alfa", 9});

    cout << index.count("alfa") << "\n";  // 3 valori pentru alfa
    cout << index.count("gama") << "\n";  // 0 (cheie inexistenta)

    // equal_range: parcurgem TOATE valorile cheii "alfa"
    auto interval = index.equal_range("alfa");
    cout << "alfa apare la paginile:";
    for (auto it = interval.first; it != interval.second; ++it) {
        cout << " " << it->second;        // it->first e cheia, it->second valoarea
    }
    cout << "\n";

    return 0;
}

Rezultat la rulare:

3
0
alfa apare la paginile: 1 5 9

Observă: nicăieri nu apare index[...], pentru că multimap nu permite. Tot ce ține de o cheie trece prin insert, equal_range și count.

Complexitate

*k = numărul de valori ale cheii. Localizarea cheii e O(log n); parcurgerea celor k valori adaugă O(k).

Recapitulare

• multimap leagă o cheie de mai multe valori; e ordonat, cu operații O(log n), din <map>.
• NU are operator[]: adaugi cu insert({cheie, val}), numeri cu count, citești o cheie cu equal_range.
• equal_range(cheie) dă intervalul [first, second) — parcurgi it != second și citești valoarea cu it->second.