C++ Coleções Intermediário

Containers associativos

Containers associativos em C++ armazenam elementos organizados por chave, permitindo busca eficiente. Os principais são std::map (árvore balanceada, chaves ordenadas) e std::unordered_map (tabela hash, sem ordem definida). Já std::set e std::unordered_set armazenam apenas chaves únicas, sem valores associados.

std::map e std::set oferecem operações de busca, inserção e remoção em tempo O(log n) e mantêm os elementos ordenados. std::unordered_map e std::unordered_set oferecem tempo médio O(1) para essas operações, mas não garantem ordem.

A escolha entre eles depende da necessidade de ordenação e do desempenho. Se a ordem importa, use a versão ordenada (map/set); se a velocidade é prioridade e a ordem não importa, use a versão não ordenada (unordered_map/unordered_set).

A iteração sobre containers associativos percorre pares chave-valor (no caso de mapas) ou apenas chaves (no caso de conjuntos). Em std::map, a iteração segue a ordem crescente das chaves; em std::unordered_map, a ordem é imprevisível.

Pontos-chave

std::map e std::set mantêm elementos ordenados e buscam em O(log n).
std::unordered_map e std::unordered_set usam hash e buscam em O(1) médio.
A busca pode ser feita com find(), count() ou contains() (C++20).
A iteração em std::map é ordenada pela chave; em std::unordered_map não há ordem definida.
Use insert() ou emplace() para adicionar elementos; operator[] só existe para mapas.

associative_containers.cpp

#include <iostream>
#include <map>
#include <unordered_map>
#include <set>
#include <string>

int main() {
    // map ordenado: chaves são strings, valores são inteiros
    std::map<std::string, int> idade;
    idade["Alice"] = 30;
    idade["Bob"] = 25;
    idade.emplace("Carlos", 40);

    // unordered_map: mesma interface, sem ordem
    std::unordered_map<std::string, int> notas;
    notas["Ana"] = 9;
    notas["Bruno"] = 7;

    // set: apenas chaves únicas, ordenadas
    std::set<int> numeros = {5, 2, 8, 2, 1};

    // Busca em map
    auto it = idade.find("Bob");
    if (it != idade.end()) {
        std::cout << "Bob tem " << it->second << " anos.\n";
    }

    // Iteração ordenada no map
    std::cout << "Idades (ordenado):\n";
    for (const auto& [nome, anos] : idade) {
        std::cout << nome << ": " << anos << "\n";
    }

    // Iteração no unordered_map (ordem indefinida)
    std::cout << "Notas (unordered):\n";
    for (const auto& [nome, nota] : notas) {
        std::cout << nome << ": " << nota << "\n";
    }

    // Iteração no set
    std::cout << "Números (set): ";
    for (int n : numeros) std::cout << n << " ";
    std::cout << "\n";

    return 0;
}

Containers associativos

Pontos-chave

Exercícios

Contando palavras com map

Interseção de conjuntos

Cache LRU com unordered_map e list

Continue estudando