De ce contează?
Ai un coș de fructe și începi să strângi mere. Spre deosebire de o listă în care
fiecare nume apare o singură dată, în coș poți pune trei mere identice — și toate
trei contează. Le ții totuși aranjate frumos, de la cel mai mic la cel mai mare.
Asta e un multiset: ca un set, dar permite copii ale aceleiași valori, și le
păstrează mereu sortate.
Ce este
Un multiset este o colecție ordonată care, spre deosebire de set, permite
duplicate. Inserezi câte valori vrei, inclusiv aceeași de mai multe ori, iar
containerul le ține automat sortate crescător.
De ce nu folosești pur și simplu un set? Pentru că set-ul aruncă duplicatele:
dacă inserezi 5 de două ori, rămâne un singur 5. Când valorile repetate
contează — de pildă vrei să menții o mulțime de scoruri din care extragi mereu
minimul sau maximul, chiar dacă două scoruri sunt egale — ai nevoie de multiset.
Operațiile-cheie:
insert(x)— adaugă o apariție a luix. O(log n).count(x)— câte apariții arex(poate fi mai mare decât 1). O(log n).erase(x)— șterge toate aparițiile luix.erase(find(x))— șterge o singură apariție (un iterator anume). O(log n).
Capcana centrală a lui multiset: erase(x) cu o valoare șterge toate
copiile lui x dintr-o dată. Dacă vrei să scoți o singură apariție, dă-i un
iterator: s.erase(s.find(x)). find(x) îți întoarce un iterator către una
dintre copii, iar erase pe iterator scoate exact acea copie.