1. Containers sequenciais versus associativos

Na STL, cotnainers como std::vector, std::list, std::deque e std::array são classificados como sequenciais, pois seus elementos são organizados de forma linear e acessados por posição. Trocar dois elementos de lugar não altera a natureza do container.

Já os containers associativos — std::set, std::map, std::unordered_set e std::unordered_map — organizam os dados com base em uma chave. Nesse caso, a ordem interna depende diretamente dos valores armazenados; alterar uma chave pode invalidar a estrutura subjacente.

Tanto std::set quanto std::map são geralmente implementados com uma árvore rubro-negra, que é uma árvore de busca balanceada. O std::set modela o cenário de busca apenas por chave (key), enquanto o std::map trabalha com pares chave/valor (key/value).

2. Uso do std::set

2.1 Visão geral da classe

A classe std::set é um template que recebe, no mínimo, o tipo da chave:

template <class T, class Compare = std::less<T>, class Alloc = std::allocator<T> >
class set;

• T: tipo da chave armazenada.
• Compare: objeto de comparação (padrão é std::less<T>, ou seja, ordenação crescente).
• Alloc: alocador de memória.

Na prática, raramente é necessário alterar os dois últimos parâmetros. Como a implementação subjacente é uma árvore rubro-negra, as operações de inserção, remoção e busca possuem custo O(log N), e a travessia por iteradores produz os elementos em ordem crescente.

2.2 Construtores e iteradores

std::set oferece iteradores bidirecionais e reversos. A travessia padrão percorre a árvore em in-ordem, de forma ordenada. Importante: tanto iterator quanto const_iterator impedem a modificação do valor da chave, para que a estrutura da árvore não seja corrompida.

Exemplos de construção:

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

int main() {
    // Construtor padrão
    std::set<int> s1;

    // Construtor por intervalo
    std::vector<int> v = {5, 3, 5, 1, 4};
    std::set<int> s2(v.begin(), v.end()); // {1, 3, 4, 5}

    // Construtor por lista de inicialização (C++11)
    std::set<int> s3 = {9, 2, 7, 2, 9};

    for (auto it = s3.begin(); it != s3.end(); ++it) {
        // *it = 0; // erro de compilação: chave é imutável
        std::cout << *it << " ";
    }
    return 0;
}

2.3 Modificadores

insert

Insere um elemento, mantendo a ordenação e garantindo unicidade. Elementos repetidos são ignorados.

#include <iostream>
#include <set>

int main() {
    std::set<int> valores;
    valores.insert(10);
    valores.insert(5);
    valores.insert(20);
    valores.insert(5); // duplicado, será descartado

    for (int v : valores) {
        std::cout << v << " "; // 5 10 20
    }
    return 0;
}

erase

Remove elementos por chave, por iterador ou por intervalo.

int main() {
    std::set<int> valores = {10, 20, 30, 40, 50};

    valores.erase(30); // remove pela chave

    auto it = valores.find(40);
    if (it != valores.end()) {
        valores.erase(it); // remove pelo iterador
    }

    valores.erase(valores.begin(), valores.end()); // remove faixa [begin, end)
    std::cout << valores.size(); // 0
    return 0;
}

swap e clear

int main() {
    std::set<int> a = {1, 2, 3};
    std::set<int> b = {7, 8, 9};

    a.swap(b); // troca apenas ponteiros internos: O(1)

    a.clear();
    std::cout << std::boolalpha << a.empty(); // true
    return 0;
}

emplace e emplace_hint

emplace constrói o elemento diretamente no container, evitando cópias desnecessárias. emplace_hint recebe uma dica de posição que pode acelerar a inserção.

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

int main() {
    std::set<std::pair<int, std::string>> registros;

    registros.emplace(42, "resposta");
    registros.insert(std::make_pair(7, "sorte"));

    auto it = registros.find({7, "sorte"});
    registros.emplace_hint(it, 8, "infinito");

    for (const auto& item : registros) {
        std::cout << item.first << " = " << item.second << "\n";
    }
    return 0;
}

2.4 find

O método membro find busca um elemento com custo O(log N), aproveitando a ordenação da árvore. Ele deve ser preferido ao std::find da biblioteca de algoritmos, que realiza busca linear (O(N)).

#include <iostream>
#include <set>

int main() {
    std::set<int> valores = {1, 2, 3, 4, 5};

    auto it = valores.find(3);
    if (it != valores.end()) {
        std::cout << "Encontrado: " << *it << "\n";
    }

    if (valores.find(10) == valores.end()) {
        std::cout << "Valor 10 nao existe\n";
    }
    return 0;
}

2.5 key_comp e value_comp

Em std::set, os conceitos de chave e valor coincidem. Ambos os métodos retornam o objeto de comparação usado para ordenar os elementos. Isso é útil quando se define um comparador customizado.

#include <iostream>
#include <set>
#include <functional>

int main() {
    std::set<int, std::greater<int>> valores = {1, 2, 3};

    auto comp = valores.key_comp();

    std::cout << std::boolalpha << comp(2, 1) << "\n"; // false, pois 2 > 1
    std::cout << std::boolalpha << comp(1, 2) << "\n"; // true, pois 1 > 2

    return 0;
}

2.6 count

Como std::set não permite chaves repetidas, count retorna apenas 0 ou 1. Sua utilidade prática é verificar existência de forma semântica clara.

#include <iostream>
#include <set>

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

    std::cout << valores.count(3) << "\n"; // 1
    std::cout << valores.count(99) << "\n"; // 0

    return 0;
}

2.7 lower_bound e upper_bound

Esses métodos retornam, respectivamente, o primeiro elemento não menor que a chave (>=) e o primeiro elemento maior que a chave (>). Ambos têm custo O(log N).

#include <iostream>
#include <set>

int main() {
    std::set<int> valores = {2, 4, 6, 8, 10};

    int chave = 6;
    auto lb = valores.lower_bound(chave); // aponta para 6
    auto ub = valores.upper_bound(chave); // aponta para 8

    std::cout << "lower_bound: " << *lb << "\n";
    std::cout << "upper_bound: " << *ub << "\n";

    return 0;
}

3. Diferenças entre std::set e std::multiset

std::multiset é declarado no mesmo cabeçalhoro <set> e possui interface muito semelhante à de std::set. A diferença fundamental é que std::multiset permite chaves repetidas.

#include <iostream>
#include <set>

int main() {
    std::set<int> s = {1, 2, 2, 3};
    std::multiset<int> ms = {1, 2, 2, 3};

    std::cout << "set size: " << s.size() << "\n";         // 3
    std::cout << "multiset size: " << ms.size() << "\n"; // 4

    std::cout << "count 2 in set: " << s.count(2) << "\n";     // 1
    std::cout << "count 2 in multiset: " << ms.count(2) << "\n"; // 2

    return 0;
}

4. Aplicações práticas

4.1 Detectando ciclo em lista encadeada

Uma forma alternativa ao algoritmo de ponteiro lento/rápido é usar um std::set para registrar os nós já visitados. A primeira repetição indica o início do ciclo. Essa abordagem possui custo espacial O(N).

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(nullptr) {}
 * };
 */
class Solution {
public:
    ListNode* detectCycle(ListNode* head) {
        std::set<ListNode*> visitados;
        ListNode* atual = head;

        while (atual != nullptr) {
            if (visitados.count(atual) > 0) {
                return atual;
            }
            visitados.insert(atual);
            atual = atual->next;
        }
        return nullptr;
    }
};

4.2 Interseção de dois arrays

Para obter a interseção, basta armazenar os elementos de um dos arrays em um std::set e verificar quais elementos do outro array existem nele.

class Solution {
public:
    std::vector<int> intersection(std::vector<int>& numsA, std::vector<int>& numsB) {
        std::set<int> conjuntoA(numsA.begin(), numsA.end());
        std::vector<int> resultado;

        for (int x : numsB) {
            if (conjuntoA.count(x) > 0) {
                resultado.push_back(x);
                conjuntoA.erase(x); // evita duplicatas no resultado
            }
        }
        return resultado;
    }
};

Esse algoritmo tem complexidade O(N log N) devido às operações na árvore. É possível reduzir para O(N) usando dois ponteiros após ordenar os dados, embora isso exija mais código.