Containers Unordered no C++ STL

No C++ Standard Template Library, as classes unordered_map e unordered_set fornecem containers associativos baseados em tabelas hash. Ao contrário de map e set, que usam árvores rubro-negras e mantêm os elementos ordenados, estes containers não garantem ordem na iteração, mas oferecem complexidade média O(1) para inserção, remoção e busca.

unordered_set

Conceito e Parâmetros Template

O unordered_set armazena elementos únicos. Seu primeiro parâmetro template é o tipo da chave (Key), com valores padrão para a função de hash e o comparador de igualdade. Caso o tipo da chave não suporte conversão para inteiro ou comparação direta, é possível fornecer funções hash personalizadas e comparadores. A estrutura subjacente é uma tabela hash com encadeamento (hash buckets), resultando em eficiência média O(1) para as operações principais.

Iteradores e Interfaces

Os iteradores são unidirecionais (forward iterators), sem suporte para iteração reversa. A travessia dos elementos ocorre em ordem não determinada. Funções como find, count e equal_range possuem semântica semelhante à do set ordenado. Além disso, há funções relacionadas a buckets (como bucket_count), devido à implementação por hash.

O insert retorna um pair<iterator, bool>, indicando sucesso e a posição do elemento.

Exemplo de Código Modificado

#include <iostream>
#include <unordered_set>

using namespace std;

int main() {
    unordered_set<string> conjunto_frases;
    conjunto_frases.insert("algoritmo");
    conjunto_frases.insert("estrutura");
    conjunto_frases.insert("compilador");
    conjunto_frases.insert("desempenho");
    conjunto_frases.insert("memoria");

    // Iteração com iterador explícito
    for (auto iter = conjunto_frases.begin(); iter != conjunto_frases.end(); ++iter) {
        cout << *iter << " ";
    }
    cout << endl;

    // Remoção de elementos e iteração com range-based for
    conjunto_frases.erase("compilador");
    conjunto_frases.erase("algoritmo");
    for (const auto& frase : conjunto_frases) {
        cout << frase << " ";
    }
    cout << endl;

    return 0;
}

A saída do programa exibirá as frases em ordem não previsível devido à natureza hash.

unordered_map

Modelo Chave-Valor

O unordered_map implemetna um mapeamento de chaves para valores. Seus parâmetros template incluem o tipo da chave (Key) e o tipo do valor (T), além dos mesmos parâmetros opcionais de hash e igualdade do unordered_set. Está disponível através do cabeçalho <unordered_map>.

Operações Específicas

Além das interfaces comuns, unordered_map fornece o operador operator[] e a função at. O operador [] permite inserção (se a chave não existir) e acesso/modificação de valores. Os iteradores seguem a mesma lógica do unordered_set: unidirecionais e sem ordem.

It's important to note that range-based for loops are supported, as they are syntactic sugar for iterator usage.

Exemplo com Diferentes Dados

#include <iostream>
#include <unordered_map>

using namespace std;

int main() {
    unordered_map<int, string> dicionario_numeros;
    dicionario_numeros.insert({100, "cem"});
    dicionario_numeros.insert({200, "duzentos"});
    
    // Inserção e modificação via operator[]
    dicionario_numeros[300];
    dicionario_numeros[400] = "quatrocentos";
    dicionario_numeros[300] = "trezentos";
    
    // Iteração manual com iterador
    auto it = dicionario_numeros.begin();
    while (it != dicionario_numeros.end()) {
        cout << it->first << " -> " << it->second << endl;
        ++it;
    }
    cout << endl;
    
    // Remoção e iteracao com range-based for
    dicionario_numeros.erase(200);
    for (const auto& par : dicionario_numeros) {
        cout << par.first << " -> " << par.second << endl;
    }
    
    return 0;
}

O operador -> do iterador retorna um ponteiro para o pair<const Key, T>, facilitando o acesso aos membros first e second.