C++ std::set

O irmão da Ana coleciona figurinhas. Ele não quer saber quantas vezes tirou a número 17; quer saber se tem a 17, e quantas figurinhas diferentes já colou. É exatamente o que o std::set ("conjunto") faz: guarda valores sem repetidos, sempre em ordem, e responde rápido "este valor está aqui?". Ele é como um std::map que só tem as chaves, sem os valores.

Você vai aprender

O que é um std::set: sem repetidos e ordenado.
Como inserir e como o insert conta se o valor era novo.
Como perguntar com contains, count e find, e como apagar.
Dois jeitos de tirar os repetidos de um std::vector.
O std::unordered_set (sem ordem, mais rápido em média).
Que existe o std::multiset (com repetidos).

Todos os programas desta aula foram compilados com o g++ 15.2 na máquina fictícia da Ana, na pasta ~/cpp/set, com g++ -std=c++23 -Wall -Wextra arquivo.cpp -o programa. É bom ter visto std::map e std::unordered_map.

A ideia: o álbum de figurinhas

O álbum tem um espaço para cada número. Se você tira a 17 e ela já está colada, não tem onde pôr: ela vai para a pilha de trocas. Folheando o álbum, as figurinhas aparecem em ordem de número, não na ordem em que foram coladas. E para saber se tem a 42, basta abrir na página dela.

No álbum	No `std::set`
Cada número só tem um espaço	Sem repetidos: inserir um valor que já existe não faz nada
Folhear do começo ao fim	Percorrer: sai em ordem crescente
"Tenho a 42?"	`album.contains(42)`
Quantas diferentes eu tenho	`album.size()`

1. Criar e inserir

#include <iostream>
#include <set>

int main() {
    std::set<int> album;

    album.insert(17);
    album.insert(3);
    album.insert(42);
    album.insert(3);
    album.insert(17);

    std::cout << "Figurinhas diferentes: " << album.size() << '\n';
    for (int f : album) {
        std::cout << f << ' ';
    }
    std::cout << '\n';
}

#include <set>: O cabeçalho do std::set (e do std::multiset).
std::set<int> album;: Um conjunto de inteiros, vazio. Um tipo só, entre <>: não há valor, só a "chave".
album.insert(17);: Põe o 17 no conjunto. O set não tem push_back: ele não tem "fim", porque decide sozinho o lugar de cada valor (a ordem).
album.insert(3); (a segunda vez): O 3 já está lá: nada acontece. Nenhum erro, nenhuma cópia.

$ g++ -std=c++23 -Wall -Wextra figurinhas.cpp -o figurinhas
$ ./figurinhas
Figurinhas diferentes: 3
3 17 42                  « em ordem crescente, não na ordem de inserção

Cinco insert, três figurinhas. Também dá para criar já com valores: std::set<int> album{3, 17, 42, 3}; (o segundo 3 é descartado).

2. O `insert` conta se era novo

Igual ao do map, o insert devolve uma dupla: um iterador para o valor e um bool que diz se ele entrou agora (true) ou já estava (false). Perfeito para separar as figurinhas novas das repetidas:

#include <iostream>
#include <set>

int main() {
    std::set<int> album{3, 17, 42};
    int pacotinho[] = {8, 17, 3, 25};

    for (int f : pacotinho) {
        auto [pos, inseriu] = album.insert(f);
        if (inseriu) {
            std::cout << f << ": nova! colei no álbum\n";
        } else {
            std::cout << f << ": repetida, vai para a troca\n";
        }
    }
    std::cout << "Álbum: " << album.size() << " figurinhas\n";
}

$ g++ -std=c++23 -Wall -Wextra inseriu.cpp -o inseriu
$ ./inseriu
8: nova! colei no álbum
17: repetida, vai para a troca
3: repetida, vai para a troca
25: nova! colei no álbum
Álbum: 5 figurinhas

auto [pos, inseriu] = album.insert(f);: Desmonta a dupla devolvida em duas variáveis (structured bindings, aula pair, tuple e Desestruturação). pos aponta o valor no conjunto; inseriu é o bool.
if (inseriu): Numa linha só, você insere e descobre se era novo, sem procurar duas vezes.

Este exemplo não usa o pos, e o g++ não reclama: variáveis de structured bindings não usadas não geram aviso.

3. Perguntar, apagar e o primeiro da ordem

#include <iostream>
#include <set>
#include <string>

int main() {
    std::set<std::string> convidados{"Ana", "Bruno", "Carla"};

    std::cout << std::boolalpha;
    std::cout << "Bruno vem? " << convidados.contains("Bruno") << '\n';
    std::cout << "Davi vem? " << convidados.contains("Davi") << '\n';
    std::cout << "count(\"Ana\") = " << convidados.count("Ana") << '\n';

    convidados.erase("Bruno");
    auto it = convidados.find("Bruno");
    if (it == convidados.end()) {
        std::cout << "Bruno saiu da lista\n";
    }
    std::cout << "Primeiro em ordem: " << *convidados.begin() << '\n';
}

$ g++ -std=c++23 -Wall -Wextra perguntar.cpp -o perguntar
$ ./perguntar
Bruno vem? true
Davi vem? false
count("Ana") = 1
Bruno saiu da lista
Primeiro em ordem: Ana

Escrita	O que faz
`s.contains(x)` C++20	`true` se `x` está no conjunto. A forma mais clara.
`s.count(x)`	0 ou 1 (num `set` não há repetidos). A forma antiga de perguntar.
`s.find(x)`	Iterador para `x`, ou `s.end()`.
`s.erase(x)`	Tira `x`; devolve quantos tirou (0 ou 1).
`*s.begin()`	O menor valor (só se o conjunto não estiver vazio). O maior é `*s.rbegin()`.

Diferente do map, o set não tem []: não há "valor" para ler, e não existe "a figurinha da posição 0". Também não dá para mudar um valor que já está lá dentro, porque isso bagunçaria a ordem. Para "trocar" o 17 por 18: erase(17) e insert(18). Os erros reais estão em "Quando dá errado".

Missão: o caderno de visitas da lojinha tem nomes repetidos. Ponha os nomes num std::set<std::string> e mostre quantos visitantes diferentes houve e os nomes em ordem. Saída esperada: Visitantes diferentes: 3 e, na linha de baixo, Ana Bruno Carla.

#include <iostream>
#include <set>
#include <string>
#include <vector>

int main() {
    std::vector<std::string> visitas{"Bruno", "Ana", "Carla", "Ana", "Bruno", "Ana"};

    // ponha as visitas num set e mostre o resultado
}

#include <iostream>
#include <set>
#include <string>
#include <vector>

int main() {
    std::vector<std::string> visitas{"Bruno", "Ana", "Carla", "Ana", "Bruno", "Ana"};

    std::set<std::string> pessoas;
    for (const auto& nome : visitas) {
        pessoas.insert(nome);
    }

    std::cout << "Visitantes diferentes: " << pessoas.size() << '\n';
    for (const auto& nome : pessoas) {
        std::cout << nome << ' ';
    }
    std::cout << '\n';
}

4. Tirar os repetidos de um `vector`

É um dos usos mais comuns do set. Há dois jeitos:

#include <algorithm>
#include <iostream>
#include <set>
#include <vector>

int main() {
    std::vector<int> notas{7, 9, 7, 10, 9, 7, 4};

    std::set<int> unicas(notas.begin(), notas.end());
    std::vector<int> sem_repetidos(unicas.begin(), unicas.end());

    for (int n : sem_repetidos) {
        std::cout << n << ' ';
    }
    std::cout << '\n';

    std::sort(notas.begin(), notas.end());
    notas.erase(std::unique(notas.begin(), notas.end()), notas.end());
    for (int n : notas) {
        std::cout << n << ' ';
    }
    std::cout << '\n';
}

$ g++ -std=c++23 -Wall -Wextra sem-repetidos.cpp -o sem-repetidos
$ ./sem-repetidos
4 7 9 10
4 7 9 10

Jeito	Como funciona	Quando usar
Passar por um `set`	`std::set<int> unicas(v.begin(), v.end());` cria o conjunto com todos os itens da faixa (os repetidos caem fora). Depois, `std::vector<int> r(unicas.begin(), unicas.end());` volta para um vetor, já em ordem.	O mais fácil de ler. Bom quando você vai continuar usando o conjunto (para perguntar "tem?").
`sort` + `unique` + `erase`	Ordena (repetidos ficam vizinhos); o `std::unique` junta os diferentes no começo e devolve onde a parte "útil" termina; o `erase` corta o resto. Explicado em Algoritmos.	Mais rápido e sem memória extra. Bom com muitos itens.

Os dois jeitos ordenam o resultado. Se você precisa manter a ordem original (a primeira aparição de cada um), use o insert que conta se era novo (seção 2): percorra o vetor e guarde num vetor novo só os valores em que inseriu deu true.

5. `std::unordered_set`: sem ordem, mais rápido em média

Assim como existe o unordered_map, existe o std::unordered_set (cabeçalho <unordered_set>): a mesma ideia de "sem repetidos", mas guardado numa tabela de espalhamento (aula std::unordered_map). Ele usa a mesma interface do set, só que sem ordem:

#include <iostream>
#include <set>
#include <string>
#include <unordered_set>

int main() {
    std::set<std::string> s{"pera", "uva", "maçã", "kiwi", "banana"};
    std::unordered_set<std::string> u{"pera", "uva", "maçã", "kiwi", "banana"};

    for (const auto& f : s) std::cout << f << ' ';
    std::cout << '\n';
    for (const auto& f : u) std::cout << f << ' ';
    std::cout << '\n';
    std::cout << std::boolalpha << u.contains("uva") << '\n';
}

$ g++ -std=c++23 -Wall -Wextra unordered-set.cpp -o unordered-set
$ ./unordered-set
banana kiwi maçã pera uva
banana kiwi maçã uva pera     « quase em ordem, por acaso: repare no uva antes do pera
true

Aqui a ordem do unordered_set saiu quase alfabética, por coincidência das gavetas. Não confie nisso: com outras palavras, ou noutra biblioteca, sai outra coisa. No editor do guia, por exemplo, a segunda linha sai kiwi banana uva maçã pera. A escolha entre os dois segue a mesma regra do map: precisa de ordem, set; só quer saber "tem ou não tem", com muitos itens, unordered_set.

6. `std::multiset`: só para conhecer

Às vezes você quer a ordem automática, mas com repetidos. Para isso existe o std::multiset (no mesmo cabeçalho <set>):

$ ./multiset              « std::multiset<int> notas{7, 9, 7, 10, 7};
5 notas, 3 vezes o 7
7 7 7 9 10

Nele o count pode passar de 1 e o insert sempre insere. Da mesma família existem o std::multimap (uma chave com vários valores) e as versões unordered_multiset/unordered_multimap. São bem menos usados; quando precisar, você já sabe que existem.

Formas diferentes de "guardar sem repetidos", e qual usar

Container	Repetidos?	Ordem	Use quando…
`std::set<T>`	Não	Crescente	Precisa de ordem, ou do menor/maior valor.
`std::unordered_set<T>`	Não	Nenhuma	Só "tem ou não tem", com muitos itens.
`std::multiset<T>`	Sim	Crescente	Quer manter tudo ordenado automaticamente, com repetidos.
`std::map<K, V>`	Chaves não	Por chave	Cada item tem um valor ligado a ele (nome → quantidade).
`std::vector<T>` + `std::find`	Você controla	A de inserção	Poucos itens (algumas dezenas) e a ordem de chegada importa.

Quando dá errado

error: no match for ‘operator[]’ (operand types are ‘std::set<int>’ and ‘int’)

$ g++ -std=c++23 -Wall -Wextra colchete.cpp -o colchete
colchete.cpp: In function ‘int main()’:
colchete.cpp:6:23: error: no match for ‘operator[]’ (operand types are ‘std::set<int>’ and ‘int’)
    6 |     std::cout << album[0] << '\n';
      |                       ^

O que significa: o set não tem [], nem por posição, nem por valor. No Clang: type 'std::set<int>' does not provide a subscript operator.

Como consertar: para perguntar se um valor existe, contains; para o menor, *album.begin(); para percorrer, for.

error: assignment of read-only location ‘it.std::_Rb_tree_const_iterator<int>::operator*()’

$ g++ -std=c++23 -Wall -Wextra mudar.cpp -o mudar      « auto it = album.find(17);  *it = 18;
mudar.cpp: In function ‘int main()’:
mudar.cpp:6:9: error: assignment of read-only location ‘it.std::_Rb_tree_const_iterator<int>::operator*()’
    6 |     *it = 18;
      |     ~~~~^~~~

O que significa: você tentou mudar um valor dentro do set. Os iteradores do set são sempre const (repare no _Rb_tree_const_iterator: "iterador constante de árvore rubro-negra", a estrutura por dentro do set). Se o 17 virasse 18 no lugar, a ordem poderia quebrar.

Como consertar: album.erase(17); album.insert(18);.

"Inseri 5 valores e o size() deu 3"

O que significa: não é erro: havia repetidos, e o set os descartou. Se você precisa guardar repetidos, use vector ou multiset.

Referência rápida

Escrita	O que faz
`std::set<T> s;` / `std::set<T> s{a, b, c};`	Cria vazio / com valores (`<set>`)
`std::set<T> s(v.begin(), v.end());`	Cria com os valores de outro container, sem repetidos
`s.insert(x)`	Insere se não existe; devolve `{iterador, inseriu}`
`s.contains(x)` C++20, `s.count(x)`, `s.find(x)`	Perguntar se existe
`s.erase(x)`	Tira `x` (devolve 0 ou 1)
`s.begin()`, `s.rbegin()`	Menor e maior valor
`s.size()`, `s.empty()`, `s.clear()`	Quantos, se está vazio, apagar tudo
`std::unordered_set<T>`	Mesma interface, sem ordem (`<unordered_set>`)
`std::multiset<T>`	Ordenado, com repetidos (`<set>`)

Exercícios

1. Criar

Complete para criar um conjunto de textos chamado tags:

std:: tags;

2. Tem?

Complete para perguntar se o 42 está no conjunto album (C++20):

if (album.(42)) { … }

3. Depois de std::set<int> s{5, 1, 5, 3, 1};, o que mostra for (int x : s) std::cout << x << ' ';?

5 1 5 3 1 1 3 5 5 1 3 1 1 3 5 5

4. O que auto [pos, inseriu] = s.insert(7); guarda em inseriu quando o 7 já estava no conjunto?

true O número 7 Quantas vezes o 7 aparece false

5. Como "trocar" o valor 17 por 18 num std::set?

s.erase(17); s.insert(18); *s.find(17) = 18; s[17] = 18; Não dá para tirar valores de um set

Missão final: a primeira letra repetida

Missão: descubra a primeira letra que aparece pela segunda vez na palavra "programa". Percorra as letras, insira cada uma num std::set<char> e use o bool do insert: quando ele disser false, a letra já estava lá. Mostre Primeira letra repetida: r e pare o laço com break.

#include <iostream>
#include <set>
#include <string>

int main() {
    std::string palavra = "programa";
    std::set<char> vistas;

    for (char letra : palavra) {
        // insira a letra e confira se era nova
    }
}

#include <iostream>
#include <set>
#include <string>

int main() {
    std::string palavra = "programa";
    std::set<char> vistas;

    for (char letra : palavra) {
        auto [pos, inseriu] = vistas.insert(letra);
        if (!inseriu) {
            std::cout << "Primeira letra repetida: " << letra << '\n';
            break;
        }
    }
}

Resumo

std::set<T> guarda valores sem repetidos e sempre em ordem crescente (<set>).
insert devolve {iterador, inseriu}: inseriu é false se o valor já estava.
Perguntar: contains C++20, count, find. Apagar: erase. Não há [] e não dá para mudar um valor no lugar.
Tirar repetidos de um vector: passar por um set, ou sort + unique + erase.
std::unordered_set: sem ordem, mais rápido em média. std::multiset: ordenado, com repetidos.
Próximo passo: stack e queue.