Kedy použiť std::set a kedy std::unordered_set v C++?

std::set a std::unordered_set sa používajú na ukladanie jedinečných prvkov. Výber medzi nimi závisí od priorít: usporiadanie alebo výkon prístupu/vkladania/odstraňovania.

std::set je založené na vyváženom binárnom vyhľadávacom strome (zvyčajne červeno-čiernom strome).

Charakteristiky std::set:

• Prvky sú uložené v zoradenom poradí.
• Vkladanie, odstraňovanie a vyhľadávanie prvkov trvá v čase O(log N), kde N je počet prvkov.
• Je vhodné, keď je dôležité zoradené poradie prvkov alebo keď je potrebné získať prvky v určitom rozsahu.

std::unordered_set je založené na hash tabuľke.

Charakteristiky std::unordered_set:

• Prvky nie sú uložené v zoradenom poradí.
• Vkladanie, odstraňovanie a vyhľadávanie prvkov trvá v priemere v čase O(1), ale v najhoršom prípade (pri veľkom počte kolízií hash funkcie) môže dosiahnuť O(N).
• Vyžaduje, aby mal typ prvku definovanú hash funkciu (std::hash) a operátor porovnania na rovnosť (operator==).
• Je vhodné, keď je potrebná maximálna rýchlosť vkladania, odstraňovania a vyhľadávania a poradie prvkov nie je dôležité.

Prehľadná tabuľka:

Kritérium	std::set	std::unordered_set
Vnútorná štruktúra	Vyvážené strom	Hash tabuľka
Poradie prvkov	Zoradené	Nezoradené
Čas vyhľadávania/vkladania/odstraňovania (priemer)	O(log N)	O(1)
Čas vyhľadávania/vkladania/odstraňovania (najhorší prípad)	O(log N)	O(N)
Požiadavky na typ	Operator <	std::hash, operator==

Príklad použitia std::set:

#include <iostream>
#include <set>

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

    // Prvky budú vypísané v zoradenom poradí: 2 5 8
    for (int hodnota : zoradený_set) {
        std::cout << hodnota << " ";
    }
    std::cout << std::endl;

    return 0;
}

Príklad použitia std::unordered_set:

#include <iostream>
#include <unordered_set>

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

    // Poradie výstupu môže byť odlišné
    for (int hodnota : neusporiadaný_set) {
        std::cout << hodnota << " ";
    }
    std::cout << std::endl;

    return 0;
}