set w C++: unikalne, posortowane elementy w std::set

Worek unikalnych, posortowanych wartości

unordered_map przechowuje pary klucz-wartość z szybkim wyszukiwaniem opartym na haszowaniu. std::set to jego prostszy kuzyn: przechowuje same wartości, bez powiązanych danych, i automatycznie pilnuje dwóch zasad. Każdy element jest unikalny (duplikaty są po cichu odrzucane), a elementy są zawsze trzymane w posortowanej kolejności.

Dlatego set to naturalny wybór przy pytaniach w rodzaju „czy to już się pojawiło?” albo „podaj różne elementy w posortowanej kolejności”. Wstawiasz bez martwienia się o duplikaty i iterujesz bez wcześniejszego sortowania.

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

int main() {
    set<int> s;
    s.insert(40);
    s.insert(10);
    s.insert(30);
    s.insert(10);   // duplikat: zignorowany

    for (int x : s) cout << x << " ";   // 10 30 40 (posortowane, bez powtórzeń)
}

Zauważ, że 10 wstawiono dwa razy i nie po kolei, a mimo to wynik jest posortowany i 10 pojawia się raz. Zbiór sam prowadzi całą ewidencję.

Wstawianie i usuwanie

insert dodaje wartość, jeśli jeszcze jej nie ma. Zwraca pair, którego .second to bool mówiący, czy wstawienie faktycznie nastąpiło; przydaje się, gdy chcesz wiedzieć, czy wartość była nowa:

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

int main() {
    set<string> seen;

    for (string word : {"go", "rust", "go", "cpp"}) {
        auto [it, inserted] = seen.insert(word);
        if (inserted)
            cout << "First time seeing: " << word << "\n";
        else
            cout << "Already saw: " << word << "\n";
    }
}

Aby usunąć wartość, wywołaj erase z samą wartością: zwraca liczbę usuniętych elementów (0 albo 1 dla set). Usuwanie czegoś, czego nie ma, jest nieszkodliwe i nie jest błędem:

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

int main() {
    set<int> s = {1, 2, 3, 4};

    s.erase(3);          // usuwa 3
    s.erase(99);         // nic nie robi, zwraca 0

    for (int x : s) cout << x << " ";   // 1 2 4
}

Sprawdzanie przynależności

Cały sens zbioru to szybkie sprawdzanie „czy to tu jest?”. Najczytelniej robi się to przez count, które zwraca 1 albo 0:

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

int main() {
    set<int> primes = {2, 3, 5, 7, 11};

    if (primes.count(7))
        cout << "7 is prime\n";

    if (!primes.count(9))
        cout << "9 is not in the set\n";
}

Od C++20 jest jeszcze czytelniejsza opcja, contains, która zwraca bool bezpośrednio:

if (primes.contains(7)) { /* ... */ }   // C++20

Częsty błąd to sięganie po operator[] tak jak przy map. set nie ma operator[]: nie ma wartości do pobrania, jest tylko obecność do sprawdzenia. Używaj count albo contains, a nie s[7].

Jeśli potrzebujesz konkretnej pozycji (żeby ją usunąć albo spojrzeć na sąsiadów), użyj find, które zwraca iterator albo end():

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

int main() {
    set<int> s = {10, 20, 30};

    auto it = s.find(20);
    if (it != s.end()) {
        cout << "found " << *it << "\n";
        s.erase(it);   // usuwanie przez iterator: bez drugiego wyszukiwania
    }
    cout << "size now " << s.size() << "\n";
}

Uporządkowana iteracja i zapytania o zakres

Ponieważ set jest posortowany, iteracja zawsze daje elementy od najmniejszego do największego, a sztuczki kontenerów uporządkowanych dostajesz za darmo. lower_bound(x) daje pierwszy element nie mniejszy niż x, a upper_bound(x) pierwszy element ściśle większy od x. Razem pozwalają przejrzeć zakres liczb bez sprawdzania każdego elementu:

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

int main() {
    set<int> s = {5, 12, 18, 23, 31, 47};

    // wypisz wszystko z przedziału [12, 31]
    auto begin = s.lower_bound(12);
    auto end = s.upper_bound(31);
    for (auto it = begin; it != end; ++it)
        cout << *it << " ";   // 12 18 23 31
}

Subtelna, ale ważna zasada: elementy zbioru są niezmienne. Iterator daje referencję const, więc nie możesz zmienić elementu w miejscu, bo mogłoby to zepsuć kolejność sortowania, na której opiera się kontener. Aby „zmienić” wartość, usuń starą i wstaw nową.

Domyślnie kolejność jest rosnąca (std::less). Aby uzyskać kolejność malejącą, podaj inny komparator jako drugi argument szablonu:

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

int main() {
    set<int, greater<int>> s = {5, 12, 18, 23};

    for (int x : s) cout << x << " ";   // 23 18 12 5
}

set, multiset czy unordered_set

std::set to jeden z trzech bliskich krewnych, a wybór właściwego ma znaczenie:

set<int>            // unikalne wartości, posortowane, O(log n)
multiset<int>       // dopuszcza duplikaty, posortowane, O(log n)
unordered_set<int>  // unikalne wartości, BEZ kolejności, średnio O(1)

Sięgaj po unordered_set, gdy potrzebujesz tylko sprawdzania przynależności, a kolejność cię nie obchodzi: wyszukiwanie oparte na haszowaniu jest średnio szybsze niż O(log n) drzewa w set. Wybierz set, gdy potrzebujesz elementów w posortowanej kolejności, zapytań o zakres przez lower_bound/upper_bound albo stabilnego zachowania iteratorów. multiset stosuj tylko wtedy, gdy duplikaty mają znaczenie (na przykład w histogramie powtarzających się wartości): w multiset count(x) może zwrócić więcej niż 1, a erase(x) usuwa wszystkie kopie, chyba że usuwasz przez pojedynczy iterator.

Jedno klasyczne zastosowanie set: usunięcie duplikatów i posortowanie vector za jednym zamachem.

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

int main() {
    vector<int> data = {4, 1, 4, 2, 1, 3};
    set<int> unique(data.begin(), data.end());

    for (int x : unique) cout << x << " ";   // 1 2 3 4
}

Zbudowanie zbioru z iteratorów wektora odrzuca każdy duplikat i sortuje resztę: bez ręcznej pętli i bez jawnego sortowania w duecie ze std::unique.

Dalej: pair i tuple

Na pair zwracanym przez insert pojawiają się już .first i .second, a structured bindings w połączeniu ze słowem kluczowym auto (auto [it, inserted]) czysto go rozpakowują. Takie lekkie typy „połącz kilka wartości razem” są w STL wszędzie. Dalej przyjrzymy się bezpośrednio pair i tuple: jak je budować, rozpakowywać i zwracać wiele wartości z funkcji bez definiowania całej struktury.