Programare Competitivă

set și multiset din STL

Un set este o mulțime ordonată de elemente unice. Elementele sunt mereu sortate și nu pot apărea de două ori.

Un multiset e la fel, dar permite duplicate.

#include <set>

set<T>

set<int> s;

s.insert(5);
s.insert(3);
s.insert(8);
s.insert(3);  // ignorat - 3 există deja

// s conține: {3, 5, 8}

cout << s.size();    // 3
cout << s.count(5);  // 1 (există)
cout << s.count(7);  // 0 (nu există)

Operații

Operație Ce face Complexitate
insert(x) Adaugă x (dacă nu există) O(log n)
erase(x) Șterge x O(log n)
find(x) Iterator la x (sau end() dacă nu există) O(log n)
count(x) 1 dacă există, 0 dacă nu O(log n)
size() Număr elemente O(1)
empty() Verifică gol O(1)
clear() Golește O(n)
begin() Iterator la cel mai mic O(1)
end() Iterator după ultimul O(1)

Iterare prin set

Elementele sunt mereu sortate crescător:

set<int> s = {5, 3, 8, 1, 9};

for (int x : s)
    cout << x << " ";
// Output: 1 3 5 8 9

find și erase

set<int> s = {3, 5, 8};

auto it = s.find(5);
if (it != s.end())
    cout << "Gasit: " << *it;  // *it = valoarea

s.erase(5);     // șterge valoarea 5
s.erase(it);    // șterge elementul la care pointează it

find returnează un iterator. Dacă elementul nu există, returnează s.end().

lower_bound și upper_bound pe set

set<int> s = {1, 3, 5, 8, 12};

auto it1 = s.lower_bound(5);   // iterator la 5 (primul >= 5)
auto it2 = s.upper_bound(5);   // iterator la 8 (primul > 5)
auto it3 = s.lower_bound(6);   // iterator la 8 (primul >= 6)

cout << *it1;  // 5
cout << *it2;  // 8
cout << *it3;  // 8
Funcție Ce returnează
lower_bound(x) Iterator la primul element >= x
upper_bound(x) Iterator la primul element > x

Dacă nu există un astfel de element, returnează end().

Important: folosește s.lower_bound(x) (metoda set-ului), nu lower_bound(s.begin(), s.end(), x) (funcția globală). Metoda e O(log n), funcția globală pe set e O(n).

Exemplu: elemente distincte

#include <fstream>
#include <set>
using namespace std;
ifstream fin("date.in");
ofstream fout("date.out");

int main()
{
    int n;
    fin >> n;

    set<int> s;
    for (int i = 0; i < n; i++) {
        int x;
        fin >> x;
        s.insert(x);
    }

    fout << "Distincte: " << s.size() << endl;
    for (int x : s)
        fout << x << " ";

    return 0;
}

date.in:

8
3 1 2 3 1 3 2 3

date.out:

Distincte: 3
1 2 3

multiset<T>

Ca set, dar permite duplicate:

multiset<int> ms;

ms.insert(3);
ms.insert(5);
ms.insert(3);
ms.insert(3);

// ms conține: {3, 3, 3, 5}

cout << ms.size();     // 4
cout << ms.count(3);   // 3

Ștergerea din multiset

ms.erase(3);           // ATENȚIE: șterge TOATE aparițiile lui 3!

// Dacă vrem să ștergem doar UNA:
auto it = ms.find(3);
if (it != ms.end())
    ms.erase(it);      // șterge doar o apariție

Exemplu: mediana curentă

Primim numere și după fiecare afișăm mediana (elementul din mijloc).

Folosim un multiset care menține elementele sortate. Mediana e la mijloc.

#include <fstream>
#include <set>
using namespace std;
ifstream fin("date.in");
ofstream fout("date.out");

int main()
{
    int n;
    fin >> n;

    multiset<int> ms;

    for (int i = 0; i < n; i++) {
        int x;
        fin >> x;
        ms.insert(x);

        // Mediana: elementul de pe poziția size/2
        auto it = ms.begin();
        advance(it, ms.size() / 2);
        fout << *it << " ";
    }

    return 0;
}
advance(it, k)

advance mută un iterator cu k poziții. Pe set, e O(k) - nu O(1) ca pe vector.

Pentru mediana eficientă, se folosesc două structuri (un max-heap și un min-heap) sau un Order Statistics Tree (GNU extension).

Set descrescător

set<int, greater<int>> s;
s.insert(3);
s.insert(7);
s.insert(1);

for (int x : s)
    cout << x << " ";
// Output: 7 3 1

set vs vector de frecvență vs vector sortat

set Vector frecvență Vector sortat
Insert O(log n) O(1) O(n)
Find O(log n) O(1) O(log n)
Erase O(log n) O(1) O(n)
Ordine Mereu sortat Nu Doar dacă sortăm
Valori mari Da Nu (limitare dimensiune) Da
Duplicate Nu (set) / Da (multiset) Da Da

Folosește set când valorile sunt mari (nu încap într-un vector de frecvență) sau când ai nevoie de ordine și ștergere.

Greșeli frecvente

1. erase(x) pe multiset șterge TOATE aparițiile

multiset<int> ms = {3, 3, 5};
ms.erase(3);   // ms = {5}, nu {3, 5}!

// Pentru o singură apariție:
ms.erase(ms.find(3));  // ms = {3, 5}

2. Iterare și ștergere simultană

// GREȘIT:
for (auto it = s.begin(); it != s.end(); it++)
    if (*it % 2 == 0)
        s.erase(it);  // iteratorul devine invalid!

// CORECT:
for (auto it = s.begin(); it != s.end(); )
    if (*it % 2 == 0)
        it = s.erase(it);
    else
        it++;

3. Acces prin indice

cout << s[0]; // GREȘIT - set nu are operator []

Set nu suportă acces prin indice. Folosește iteratori.

Ce să reții

  • set<T>: mulțime ordonată de elemente unice. Insert/find/erase în O(log n).
  • multiset<T>: ca set dar permite duplicate. erase(x) șterge toate aparițiile.
  • Elementele sunt mereu sortate. Iterarea e în ordine crescătoare.
  • lower_bound(x) = primul >= x, upper_bound(x) = primul > x.
  • Folosește metoda set-ului (s.lower_bound(x)), nu funcția globală.
  • Fără acces prin indice - doar iteratori.
Cuprins Inapoi Inainte