Kiedy używać std::set, a kiedy std::unordered_set w C++?

std::set i std::unordered_set są używane do przechowywania unikalnych elementów. Wybór między nimi zależy od priorytetów: uporządkowania czy wydajności dostępu/wstawiania/usuwania.

std::set opiera się na zrównoważonym drzewie binarnym (zwykle drzewo czerwono-czarne).

Charakterystyka std::set:

• Elementy są przechowywane w posortowanej kolejności.
• Wstawianie, usuwanie i wyszukiwanie elementów zajmuje średnio O(log N), gdzie N to liczba elementów.
• Nadaje się, gdy ważne jest uporządkowanie elementów lub gdy konieczne jest pobranie elementów w określonym zakresie.

std::unordered_set opiera się na tablicy haszującej.

Charakterystyka std::unordered_set:

• Elementy nie są przechowywane w uporządkowanej kolejności.
• Wstawianie, usuwanie i wyszukiwanie elementów w średnim czasie O(1), ale w najgorszym przypadku (przy dużej liczbie kolizji funkcji hash) może osiągnąć O(N).
• Wymaga, aby typ elementu miał zdefiniowaną funkcję hash (std::hash) i operator porównania równości (operator==).
• Nadaje się, gdy potrzebna jest maksymalna szybkość wstawiania, usuwania i wyszukiwania, a kolejność elementów nie ma znaczenia.

Tabela podsumowująca:

Kryterium	std::set	std::unordered_set
Struktura wewnętrzna	Zrównoważone drzewo	Tablica haszująca
Kolejność elementów	Posortowana	Nieposortowana
Czas wyszukiwania/wstawiania/usuwania (średni)	O(log N)	O(1)
Czas wyszukiwania/wstawiania/usuwania (najgorszy)	O(log N)	O(N)
Wymagania dotyczące typu	Operator <	std::hash, operator==

Przykład użycia std::set:

#include <iostream>
#include <set>

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

    // Elementy zostaną wyświetlone w kolejności: 2 5 8
    for (int val : ordered_set) {
        std::cout << val << " ";
    }
    std::cout << std::endl;

    return 0;
}

Przykład użycia std::unordered_set:

#include <iostream>
#include <unordered_set>

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

    // Kolejność wyświetlania może się różnić
    for (int val : unordered_set) {
        std::cout << val << " ";
    }
    std::cout << std::endl;

    return 0;
}