Docs executáveis de C++: set

Q: O que é um set em C++?

Um std::set é um contêiner associativo que armazena valores únicos em ordem crescente. Inserir um valor que já existe não faz nada, e ao iterar percorrem-se os elementos do menor para o maior. Buscas, inserções e remoções são todas O(log n) porque ele é implementado com uma árvore binária de busca balanceada.

Q: Como verifico se um elemento existe em um set de C++?

Use s.count(x), que retorna 1 se x estiver presente e 0 caso contrário, ou s.contains(x) no C++20, que retorna um bool. Evite s.find(x) != s.end() a menos que você realmente precise do iterador: tem o mesmo custo, mas é mais verboso.

Q: Qual é a diferença entre set e unordered_set em C++?

std::set mantém os elementos ordenados e oferece operações O(log n); std::unorderedset os mantém sem ordem definida usando uma tabela hash, com operações O(1) em média. Use set quando precisar de iteração ordenada ou consultas por intervalo, e unorderedset quando precisar apenas de testes rápidos de existência e a ordem não importar.

Um conjunto de valores únicos e ordenados

Você já viu o unordered_map armazenar pares chave-valor com busca rápida baseada em hash. Um std::set é o primo mais simples: ele armazena apenas valores — sem dados associados — e aplica duas regras automaticamente. Cada elemento é único (duplicados são descartados silenciosamente) e os elementos são sempre mantidos em ordem crescente.

Isso faz do set a escolha natural para perguntas como "já vi isto antes?" ou "me dê os itens distintos em ordem". Você insere sem se preocupar com duplicados e itera sem ordenar primeiro.

#include <iostream>
#include <set>
using namespace std;

int main() {
    set<int> s;
    s.insert(40);
    s.insert(10);
    s.insert(30);
    s.insert(10);   // duplicado - ignorado

    for (int x : s) cout << x << " ";   // 10 30 40 (ordenado, sem repetir)
}

Repare que inserimos 10 duas vezes e fora de ordem, mas mesmo assim a saída está ordenada e o 10 aparece uma única vez. O set fez o trabalho de organização por você.

Inserir e remover

insert adiciona um valor se ele ainda não estiver presente. Retorna um pair cujo .second é um bool que indica se a inserção realmente aconteceu — útil quando você quer saber se um valor era novo:

#include <iostream>
#include <set>
#include <string>
using namespace std;

int main() {
    set<string> seen;

    for (string word : {"go", "rust", "go", "cpp"}) {
        auto [it, inserted] = seen.insert(word);
        if (inserted)
            cout << "First time seeing: " << word << "\n";
        else
            cout << "Already saw: " << word << "\n";
    }
}

Para remover um valor, chame erase com o próprio valor: ele retorna o número de elementos removidos (0 ou 1 para um set). Remover algo que não está presente é inofensivo, não é um erro:

#include <iostream>
#include <set>
using namespace std;

int main() {
    set<int> s = {1, 2, 3, 4};

    s.erase(3);          // remove o 3
    s.erase(99);         // não faz nada, retorna 0

    for (int x : s) cout << x << " ";   // 1 2 4
}

Verificando a existência

O objetivo principal de um set são os testes rápidos de "isto está aqui?". A forma mais clara é count, que retorna 1 ou 0:

#include <iostream>
#include <set>
using namespace std;

int main() {
    set<int> primes = {2, 3, 5, 7, 11};

    if (primes.count(7))
        cout << "7 is prime\n";

    if (!primes.count(9))
        cout << "9 is not in the set\n";
}

Desde o C++20 há uma opção ainda mais legível, contains, que retorna um bool diretamente:

if (primes.contains(7)) { /* ... */ }   // C++20

Um erro comum é recorrer ao operator[] como você faria com um map. Um set não tem operator[]: não há valor a recuperar, apenas presença a verificar. Use count ou contains, não s[7].

Se você precisar da posição exata (para removê-la ou olhar os vizinhos), use find, que retorna um iterador ou end():

#include <iostream>
#include <set>
using namespace std;

int main() {
    set<int> s = {10, 20, 30};

    auto it = s.find(20);
    if (it != s.end()) {
        cout << "found " << *it << "\n";
        s.erase(it);   // remove pelo iterador - sem uma segunda busca
    }
    cout << "size now " << s.size() << "\n";
}

Iteração ordenada e consultas por intervalo

Como um set é ordenado, iterar sempre produz os elementos do menor para o maior, e você ganha de graça os truques de contêineres ordenados. lower_bound(x) dá o primeiro elemento não menor que x, e upper_bound(x) o primeiro elemento estritamente maior que x; juntos eles permitem percorrer um intervalo numérico sem verificar cada elemento:

#include <iostream>
#include <set>
using namespace std;

int main() {
    set<int> s = {5, 12, 18, 23, 31, 47};

    // imprime tudo que estiver em [12, 31]
    auto begin = s.lower_bound(12);
    auto end = s.upper_bound(31);
    for (auto it = begin; it != end; ++it)
        cout << *it << " ";   // 12 18 23 31
}

Uma regra sutil, mas importante: os elementos de um set são imutáveis. O iterador entrega uma referência const, então você não pode alterar um elemento no lugar — fazer isso poderia quebrar a ordenação da qual o contêiner depende. Para "alterar" um valor, remova o antigo e insira o novo.

Por padrão a ordenação é crescente (std::less). Para ordem decrescente, forneça um comparador diferente como segundo argumento de template:

#include <iostream>
#include <functional>
#include <set>
using namespace std;

int main() {
    set<int, greater<int>> s = {5, 12, 18, 23};

    for (int x : s) cout << x << " ";   // 23 18 12 5
}

set vs multiset vs unordered_set

std::set é um de três parentes próximos, e escolher o certo faz diferença:

set<int>            // valores únicos, ordenados, O(log n)
multiset<int>       // permite duplicados, ordenados, O(log n)
unordered_set<int>  // valores únicos, SEM ordem, O(1) em média

Recorra ao unordered_set quando precisar apenas de testes de existência e não se importar com a ordem — suas buscas baseadas em hash são, em média, mais rápidas que o O(log n) baseado em árvore do set. Escolha set quando precisar de elementos em ordem, consultas por intervalo com lower_bound/upper_bound ou comportamento estável dos iteradores. Use multiset apenas quando os duplicados forem significativos (por exemplo, um histograma de valores repetidos): em um multiset, count(x) pode retornar mais de 1, e erase(x) remove todas as cópias a menos que você remova por um único iterador.

Um uso clássico de set: remover duplicados e ordenar um vector de uma só vez.

#include <iostream>
#include <set>
#include <vector>
using namespace std;

int main() {
    vector<int> data = {4, 1, 4, 2, 1, 3};
    set<int> unique(data.begin(), data.end());

    for (int x : unique) cout << x << " ";   // 1 2 3 4
}

Construir o set a partir dos iteradores do vector descarta cada duplicado e ordena o restante — sem laço manual, sem a dança de std::sort mais std::unique.

Próximo: pair e tuple

Você já viu .first e .second aparecerem no pair que insert retorna, e as ligações estruturadas (auto [it, inserted]) o desempacotarem de forma limpa. Esses tipos leves para "agrupar alguns valores" estão por toda parte na STL. A seguir vamos ver pair e tuple diretamente: como construí-los, desempacotá-los e retornar vários valores de uma função sem definir uma struct inteira.

Perguntas frequentes

O que é um set em C++?

Um std::set é um contêiner associativo que armazena valores únicos em ordem crescente. Inserir um valor que já existe não faz nada, e ao iterar percorrem-se os elementos do menor para o maior. Buscas, inserções e remoções são todas O(log n) porque ele é implementado com uma árvore binária de busca balanceada.

Como verifico se um elemento existe em um set de C++?

Use s.count(x), que retorna 1 se x estiver presente e 0 caso contrário, ou s.contains(x) no C++20, que retorna um bool. Evite s.find(x) != s.end() a menos que você realmente precise do iterador: tem o mesmo custo, mas é mais verboso.

Qual é a diferença entre set e unordered_set em C++?

std::set mantém os elementos ordenados e oferece operações O(log n); std::unordered_set os mantém sem ordem definida usando uma tabela hash, com operações O(1) em média. Use set quando precisar de iteração ordenada ou consultas por intervalo, e unordered_set quando precisar apenas de testes rápidos de existência e a ordem não importar.

Conceitos relacionados