multiset — mulțime ordonată cu duplicate

Ce este un multiset și de ce diferă de set

Un multiset este o colecție ordonată care permite valori duplicate. Un set obișnuit refuză un al doilea element egal: dacă inserezi 5 de două ori, în set rămâne un singur 5. Multiset-ul le păstrează pe amândouă.

Asta înseamnă că count(valoare) poate fi mai mare decât 1 — chiar exact câte copii ai inserat. Tot ce e ordonat și logaritmic la set rămâne la fel aici: elementele sunt mereu sortate crescător, iar insert, find, count și erase sunt O(log n).

Îl folosești când ai nevoie de duplicate plus ordine: minimul și maximul dintr-o mulțime care se schimbă, mediana glisantă, sau pur și simplu să numeri câte elemente sunt mai mici decât o valoare.

Exemplu pas cu pas

Pornim cu un multiset gol și inserăm pe rând: 4, 2, 4, 7, 4, 2.

• insert 4 → {4}
• insert 2 → {2, 4} (se așază înaintea lui 4, ordonat)
• insert 4 → {2, 4, 4} (duplicat acceptat)
• insert 7 → {2, 4, 4, 7}
• insert 4 → {2, 4, 4, 4, 7}
• insert 2 → {2, 2, 4, 4, 4, 7}

Acum count(4) întoarce 3, iar count(2) întoarce 2. Minimul e primul, 2, maximul e ultimul, 7. Dacă apelezi erase(4), dispar toate cele trei apariții deodată — atenție aici, e cea mai frecventă capcană.

Implementare C++

Multiset-ul vine tot din header-ul <set>. Iată operațiile esențiale și, mai ales, diferența dintre erase(valoare) și erase(find(...)):

#include <iostream>
#include <set>
using namespace std;

int main() {
    multiset<int> s;
    s.insert(4);
    s.insert(2);
    s.insert(4);
    s.insert(7);
    s.insert(4);                    // acum avem {2, 4, 4, 4, 7}

    cout << s.count(4) << "\n";     // 3 (trei aparitii)
    cout << s.size() << "\n";       // 5
    cout << *s.begin() << "\n";     // 2 (minimul)
    cout << *s.rbegin() << "\n";    // 7 (maximul)

    // CAPCANA: erase(valoare) sterge TOATE aparitiile
    multiset<int> a = s;
    a.erase(4);                     // scoate toti cei trei de 4
    cout << a.count(4) << "\n";     // 0

    // CORECT pentru o singura aparitie: erase(find(valoare))
    multiset<int> b = s;
    auto it = b.find(4);            // iterator spre UN singur 4
    if (it != b.end()) {
        b.erase(it);               // sterge doar acel element
    }
    cout << b.count(4) << "\n";     // 2 (au mai ramas doi)

    return 0;
}

Reține tiparul: find returnează un iterator spre o singură copie, iar erase(iterator) scoate exact acel element. erase(valoare) lucrează pe valoare și mătură tot ce e egal cu ea.

Complexitate

Recapitulare

• Multiset = set ordonat care permite duplicate, deci count poate fi > 1; toate operațiile sunt O(log n).
• erase(valoare) șterge toate aparițiile; pentru una singură folosești s.erase(s.find(valoare)) — după ce verifici că nu e end().
• Minimul e *s.begin(), maximul *s.rbegin(): ideal pentru min/max dinamic, mediană sau cele mai mici k elemente într-o mulțime care se schimbă.