Mikor kell használni a std::set-et és mikor a std::unordered_set-et C++-ban?

A std::set és a std::unordered_set olyan adatszerkezetek, amelyek egyedi elemek tárolására szolgálnak. A közöttük választás attól függ, hogy prioritást adunk-e a rendezésnek vagy a hozzáférés/ beszúrás/ törlés gyorsaságának.

A std::set egy kiegyensúlyozott bináris keresőfán alapul (általában piros-fekete fa).

A std::set jellemzői:

• Az elemek rendezett sorrendben vannak tárolva.
• A beszúrás, törlés és keresés átlagosan O(log N) időt vesz igénybe, ahol N az elemek száma.
• Akkor ideális, ha fontos a rendezett sorrend vagy ha tartományon belüli elemeket akarunk lekérdezni.

Az std::unordered_set egy hash-táblán alapul.

Az std::unordered_set jellemzői:

• Az elemek nem rendezettek.
• A beszúrás, törlés és keresés átlagosan O(1) időt vesz igénybe, de a legrosszabb esetben (sok hash ütközés esetén) O(N) is lehet.
• Megköveteli, hogy az elem típusának legyen egy hash függvénye (std::hash) és egy egyenlőség operátora (operator==).
• Akkor ideális, ha a lehető leggyorsabb beszúrásra, törlésre és keresésre van szükség, és nem számít a sorrend.

Összefoglaló táblázat:

Kritérium	std::set	std::unordered_set
Belső struktúra	Kiegyensúlyozott fa	Hash-tábla
Elem sorrend	Rendezett	Rendezettlen
Átlagos keresési/beszúrási/törlési idő	O(log N)	O(1)
Legrosszabb eset idő	O(log N)	O(N)
Típus követelmények	< operátor	std::hash, operator==

A std::set használatának példája:

#include <iostream>
#include <set>

int main() {
    std::set<int> rendezett_set;
    rendezett_set.insert(5);
    rendezett_set.insert(2);
    rendezett_set.insert(8);

    // Az elemek rendezett sorrendben jelennek meg: 2 5 8
    for (int érték : rendezett_set) {
        std::cout << érték << " ";
    }
    std::cout << std::endl;

    return 0;
}

A std::unordered_set példája:

#include <iostream>
#include <unordered_set>

int main() {
    std::unordered_set<int> nem_rendezett_set;
    nem_rendezett_set.insert(5);
    nem_rendezett_set.insert(2);
    nem_rendezett_set.insert(8);

    // A kiírás sorrendje változhat
    for (int érték : nem_rendezett_set) {
        std::cout << érték << " ";
    }
    std::cout << std::endl;

    return 0;
}