Quando deve usar std::set e quando std::unordered_set em C++?

O std::set e o std::unordered_set são usados para armazenar elementos únicos. A escolha entre eles depende das prioridades: ordenação ou desempenho de acesso/inserção/exclusão.

std::set é baseado numa árvore binária de pesquisa equilibrada (geralmente uma árvore vermelho-preto).

Características do std::set:

• Os elementos são armazenados em ordem ordenada.
• Inserir, remover e procurar elementos levam tempo O(log N), onde N é o número de elementos.
• É adequado quando a ordem dos elementos é importante ou quando se precisa obter elementos numa faixa específica.

std::unordered_set é baseado numa tabela de hash.

Características do std::unordered_set:

• Os elementos não são armazenados em ordem ordenada.
• Inserir, remover e procurar elementos em média levam tempo O(1), mas no pior caso (com muitas colisões na função hash) podem atingir O(N).
• Requer que o tipo de elemento tenha uma função hash (std::hash) e um operador de comparação de igualdade (operator==).
• É adequado quando se deseja a inserção, remoção e procura mais rápidas possíveis, e a ordem dos elementos não importa.

Tabela resumo:

Critério	std::set	std::unordered_set
Estrutura interna	Árvore equilibrada	Tabela de hash
Ordem dos elementos	Ordenado	Não ordenado
Tempo de procura/inserção/exclusão (média)	O(log N)	O(1)
Tempo de procura/inserção/exclusão (pior caso)	O(log N)	O(N)
Requisitos do tipo	Operador <	std::hash, operator==

Exemplo de uso do 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);

    // Os elementos serão exibidos em ordem: 2 5 8
    for (int val : ordered_set) {
        std::cout << val << " ";
    }
    std::cout << std::endl;

    return 0;
}

Exemplo de uso do 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);

    // A ordem de saída pode variar
    for (int val : unordered_set) {
        std::cout << val << " ";
    }
    std::cout << std::endl;

    return 0;
}