Kdy používat std::set a kdy std::unordered_set v C++?

std::set a std::unordered_set jsou datové struktury používané pro ukládání unikátních prvků. Výběr mezi nimi závisí na prioritách: řazení nebo výkon přístupu/vkládání/mazání.

std::set je založen na vyváženém binárním vyhledávacím stromu (obvykle červené-černé stromy).

Vlastnosti std::set:

• Prvky jsou uloženy v seřazeném pořadí.
• Vkládání, mazání a hledání prvků trvá průměrně O(log N), kde N je počet prvků.
• Je vhodný, když je důležité seřazené pořadí prvků nebo když je potřeba získat prvky v určitém rozsahu.

std::unordered_set je založen na hash tabulce.

Vlastnosti std::unordered_set:

• Prvky nejsou uloženy v seřazeném pořadí.
• Vkládání, mazání a hledání prvků trvá průměrně O(1), ale v nejhorším případě (při mnoha kolizích hash funkce) může dosáhnout O(N).
• Vyžaduje, aby typ prvku měl definovanou hash funkci (std::hash) a operátor rovnosti (operator==).
• Je vhodný, když je potřeba co nejrychlejší vkládání, mazání a hledání, a pořadí prvků není důležité.

Souhrnná tabulka:

Kritérium	std::set	std::unordered_set
Vnitřní struktura	Vyvážené strom	Hash tabulka
Pořadí prvků	Seřazené	Neseřazené
Čas hledání/vkládání/mazání (průměr)	O(log N)	O(1)
Čas hledání/vkládání/mazání (nejhorší)	O(log N)	O(N)
Požadavky na typ	Operátor <	std::hash, operator==

Příklad použití std::set:

#include <iostream>
#include <set>

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

    // Prvky se vypíšou v pořadí: 2 5 8
    for (int hodnota : seřazený_set) {
        std::cout << hodnota << " ";
    }
    std::cout << std::endl;

    return 0;
}

Příklad použití std::unordered_set:

#include <iostream>
#include <unordered_set>

int main() {
    std::unordered_set<int> neuspořádaný_set;
    neuspořádaný_set.insert(5);
    neuspořádaný_set.insert(2);
    neuspořádaný_set.insert(8);

    // Pořadí výstupu se může lišit
    for (int hodnota : neuspořádaný_set) {
        std::cout << hodnota << " ";
    }
    std::cout << std::endl;

    return 0;
}