Em complemento às discussões anteriores sobre contêineres sequenciais e associativos da STL, esta seção se aprofunda nos contêineres não ordenados. Diferentemente dos contêineres associativos, que mantêm os elementos em ordem, os contêineres não ordenados utilizam estruturas de dados baseadas em hashing para armazenar elementos sem uma ordem predefinida.

1. unordered_set

O std::unordered_set é um contêiner associativo não ordenado que implementa uma tabela de hash. Cada chave é mapeada para um índice na tabela de hash, resultando em inserções que geralmente ocorrem em posições aleatórias. Em média, as operações em um unordered_set possuem complexidade de tempo constanet O(1). Contudo, no pior caso, a complexidade pode degradar para O(n), dependendo da qualidade da função de hash. Na prática, eles oferecem um desempenho excelente, com buscas frequentemente realizadas em tempo constante.

Um unordered_set pode armazenar chaves de qualquer tipo, sejam elas pré-definidas ou tipos definidos pelo usuário. Uma característica fundamental é que todas as chaves dentro do conjunto devem ser únicas. A sintaxe básica para declarar um unordered_set é:

std::unordered_set<tipo_de_dado> nome_do_conjunto;

Métodos Comuns

• size() e empty(): Retornam o número de elementos e indicam se o conjunto está vazio, respectivamente.
• find(): Busca por uma chave específica.
• insert() e erase(): Adicionam ou removem elementos do conjunto.

Exemplo de Uso

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

int main() {
    std::unordered_set<std::string> palavras;

    palavras.insert("codigo");
    palavras.insert("em");
    palavras.insert("c++");
    palavras.insert("é");
    palavras.insert("rápido");

    std::string chave = "lento";

    // Verifica se a chave existe
    if (palavras.find(chave) == palavras.end()) {
        std::cout << chave << " não encontrado." << std::endl;
    } else {
        std::cout << "Encontrado: " << chave << std::endl;
    }

    chave = "c++";
    if (palavras.find(chave) == palavras.end()) {
        std::cout << chave << " não encontrado." << std::endl;
    } else {
        std::cout << "Encontrado: " << chave << std::endl;
    }

    std::cout << "\nTodos os elementos: ";
    // Itera sobre os elementos
    for (const std::string& elem : palavras) {
        std::cout << elem << ' ';
    }
    std::cout << std::endl;

    return 0;
}

A saída demonstrará que a ordem dos elementos não é garantida, refletindo a natureza não ordenada do contêiner.

Quando uma chave não é encontrada, a função find() retorna um iterador para o final do conjunto (end()). Caso contrário, retorna um iterador apontando para a posição da chave. O operador * pode ser usado para desreferenciar o iterador e acessar o valor da chave.

Problema Prático: Identificando Duplicatas em um Array

Dado um array de inteiros, como identificar todos os elementos que aparecem mais de uma vez?

#include <iostream>
#include <unordered_set>
#include <vector>

void imprimirDuplicatas(const int arr[], int n) {
    std::unordered_set<int> vistos;
    std::unordered_set<int> duplicatas;

    for (int i = 0; i < n; ++i) {
        // Se o elemento já foi visto, adiciona ao conjunto de duplicatas
        if (vistos.count(arr[i])) {
            duplicatas.insert(arr[i]);
        } else {
            // Marca o elemento como visto
            vistos.insert(arr[i]);
        }
    }

    std::cout << "Itens duplicados: ";
    for (int dup : duplicatas) {
        std::cout << dup << " ";
    }
    std::cout << std::endl;
}

int main() {
    int array_numeros[] = {1, 5, 2, 1, 4, 3, 1, 7, 2, 8, 9, 5};
    int tamanho = sizeof(array_numeros) / sizeof(array_numeros[0]);
    imprimirDuplicatas(array_numeros, tamanho);
    return 0;
}

Outros Métodos Relevantes para unordered_set

• insert(): Insere um novo elemento.
• begin()/end(): Retornam iteradores para o início e o fim do contêiner.
• count(): Retorna o número de ocorrências de um elemento específico.
• clear(): Remove todos os elementos.
• erase(): Remove um ou mais elementos.
• size(): Retorna o número de elementos.
• swap(): Troca o conteúdo de dois conjuntos.
• emplace(): Insere um elemento construído no local.
• empty(): Verifica se o conjunto está vazio.
• bucket_size(): Retorna o número de elementos em um bucket específico.
• hash_function(): Retorna o objeto da função de hash utilizada.
• load_factor(): Calcula o fator de carga (relação entre elementos e buckets).
• rehash(): Ajusta o número de buckets.

2. unordered_map

O std::unordered_map é um contêiner associativo que armazena pares de chave-valor. As chaves são únicas e utilizadas para identificar os valores associados. Assim como o unordered_set, ele utiliza uma tabela de hash internamente, proporcionando, em média, complexidade O(1) para operações de busca, inserção e remoção.

Uso Básico

#include <iostream>
#include <unordered_map>
#include <string>

int main() {
    std::unordered_map<std::string, int> mapa_dados;

    // Inserção de elementos
    mapa_dados["GeeksforGeeks"] = 10;
    mapa_dados["Pratica"] = 20;
    mapa_dados["Contribua"] = 30;

    // Iteração e impressão dos elementos
    for (const auto& par : mapa_dados) {
        std::cout << par.first << "=" << par.second << ' ';
    }
    std::cout << std::endl;

    return 0;
}

Métodos Principais

• at(key): Retorna uma referência ao valor associado à chave. Lança exceção se a chave não existir.
• begin()/end(): Retornam iteradores.
• count(key): Retorna o número de elementos com a chave especificada (0 ou 1).
• find(key): Busca um elemento pela chave.
• empty(): Verifica se o mapa está vazio.
• erase(key): Remove elementos pela chave.
• bucket(key): Retorna o número do bucket onde a chave se encontra.
• bucket_count(): Retorna o número total de buckets.

Exemplo Detalhado

#include <iostream>
#include <unordered_map>
#include <string>

int main() {
    // Inicialização com lista de inicialização
    std::unordered_map<std::string, double> mapa_numeros =
    {
        {"Um", 1.0},
        {"Dois", 2.0},
        {"Tres", 3.0}
    };

    // Inserções adicionais
    mapa_numeros["PI"] = 3.14;
    mapa_numeros["raiz2"] = 1.414;
    mapa_numeros.insert(std::make_pair("e", 2.718)); // Outra forma de inserção

    std::string chave = "PI";

    // Verificando a existência de chaves
    if (mapa_numeros.find(chave) == mapa_numeros.end()) {
        std::cout << chave << " não encontrado." << std::endl;
    } else {
        std::cout << "Encontrado: " << chave << std::endl;
    }

    chave = "lambda";
    if (mapa_numeros.find(chave) == mapa_numeros.end()) {
        std::cout << chave << " não encontrado." << std::endl;
    } else {
        std::cout << "Encontrado: " << chave << std::endl;
    }

    std::cout << "\nTodos os elementos do mapa:" << std::endl;
    for (const auto& par : mapa_numeros) {
        std::cout << par.first << ": " << par.second << std::endl;
    }

    return 0;
}

Exemplo: Contagem de Frequência de Palavras

#include <iostream>
#include <unordered_map>
#include <string>
#include <sstream>

void imprimirFrequencias(const std::string& texto) {
    std::unordered_map<std::string, int> frequencia_palavras;
    std::stringstream ss(texto);
    std::string palavra;

    // Processa o texto para contar a frequência de cada palavra
    while (ss >> palavra) {
        frequencia_palavras[palavra]++;
    }

    std::cout << "Frequência das palavras:" << std::endl;
    for (const auto& par : frequencia_palavras) {
        std::cout << "(" << par.first << ", " << par.second << ")" << std::endl;
    }
}

int main() {
    std::string frase = "geeks for geeks geeks quiz practice qa for";
    imprimirFrequencias(frase);
    return 0;
}

3. unordered_multiset

O std::unordered_multiset é similar ao unordered_set, com a distinção principal de que permite a presença de múltiplos elementos com o mesmo valor (chave). Os elementos ainda são armazenados de forma não ordenada através de hashing, mas elementos duplicados podem aparecer juntos.

A sintaxe de declaração é a mesma do unordered_set.

Exemplo de Uso

#include <iostream>
#include <unordered_set>
#include <vector>

// Helper function to print the contents of the multiset
void imprimirMultiset(const std::unordered_multiset<int>& ums) {
    for (int val : ums) {
        std::cout << val << " ";
    }
    std::cout << std::endl;
}

int main() {
    std::unordered_multiset<int> ms1;
    std::unordered_multiset<int> ms2 = {1, 3, 1, 7, 2, 3, 4, 1, 6};

    ms1 = {2, 7, 2, 5, 0, 3, 7, 5};

    if (ms1.empty()) {
        std::cout << "Multiset 1 está vazio." << std::endl;
    } else {
        std::cout << "Multiset 1 não está vazio." << std::endl;
    }

    std::cout << "Tamanho do Multiset 2: " << ms2.size() << std::endl;

    std::cout << "Multiset 1: ";
    imprimirMultiset(ms1);

    ms1.insert(7); // Insere outro 7
    std::cout << "Multiset 1 após inserir 7: ";
    imprimirMultiset(ms1);

    int valor = 3;
    // Verifica a presença de um elemento
    if (ms1.count(valor)) {
        std::cout << "Multiset 1 contém " << valor << std::endl;
    } else {
        std::cout << "Multiset 1 não contém " << valor << std::endl;
    }

    valor = 5;
    // Conta ocorrências de um elemento
    int contagem = ms1.count(valor);
    std::cout << valor << " aparece " << contagem << " vezes no Multiset 1." << std::endl;

    valor = 9;
    if (ms1.count(valor)) {
        std::cout << "Multiset 1 contém " << valor << std::endl;
    } else {
        std::cout << "Multiset 1 não contém " << valor << std::endl;
    }

    // Usando equal_range para encontrar o intervalo de elementos iguais a um valor
    valor = 1;
    auto range_it = ms2.equal_range(valor);
    if (range_it.first != range_it.second) {
        std::cout << valor << " apareceu pelo menos uma vez no Multiset 2." << std::endl;
    }

    std::cout << "Multiset 2: ";
    imprimirMultiset(ms2);

    // Removendo todas as ocorrências de um valor
    valor = 1;
    ms2.erase(valor); // Remove todas as ocorrências de 1
    std::cout << "Multiset 2 após remover todas as ocorrências de " << valor << ": ";
    imprimirMultiset(ms2);

    ms1.clear();
    ms2.clear();

    if (ms1.empty()) {
        std::cout << "Multiset 1 agora está vazio." << std::endl;
    }

    return 0;
}

Diferença Chave: unordered_set vs. unordered_multiset

A principal diferença reside em como as duplicatas são tratadas. No unordered_multiset, a função erase(valor) remove *todas* as ocorrências de um valor. Para remover apenas uma ocorrência, é necessário usar find() para obter um iterador para a primeira instância e, em seguida, chamar erase(iterador).

Removendo uma Única Ocorrência

#include <iostream>
#include <unordered_set>
#include <vector>

// Helper function to print the contents of the multiset
void imprimirMultiset(const std::unordered_multiset<int>& ums) {
    for (int val : ums) {
        std::cout << val << " ";
    }
    std::cout << std::endl;
}

// Função para remover uma única ocorrência de um valor
void removerUmaOcorrencia(std::unordered_multiset<int>& ums, int valor) {
    auto it = ums.find(valor); // Encontra a primeira ocorrência
    if (it != ums.end()) {
        ums.erase(it); // Remove apenas essa ocorrência
    }
}

int main() {
    std::unordered_multiset<int> ms = {1, 3, 1, 7, 2, 3, 4, 1, 6};

    std::cout << "Multiset original: ";
    imprimirMultiset(ms);

    int valor_para_remover = 1;
    removerUmaOcorrencia(ms, valor_para_remover);

    std::cout << "Multiset após remover uma ocorrência de " << valor_para_remover << ": ";
    imprimirMultiset(ms);

    return 0;
}

Métodos Comuns para unordered_multiset

• insert(): Insere novos elementos.
• begin()/end(): Retornam iteradores.
• empty(): Verifica se o contêiner está vazio.
• find(key): Retorna um iterador para uma ocorrência do elemento.
• equal_range(val): Retorna um par de iteradores delimitando o intervalo de elementos com valor igual a val.
• erase(val): Remove todas as ocorrências de val.
• count(val): Retorna o número de ocorrências de val.
• size(): Retorna o número de elementos.
• clear(): Remove todos os elementos.
• bucket(): Retorna o bucket de um elemento.
• load_factor(): Retorna o fator de carga atual.
• rehash(): Ajusta o número de buckets.

4. unordered_multimap

O std::unordered_multimap é um contêiner associativo que armazena pares de chave-valor, permitindo que múltiplas chaves idênticas existam, cada uma associada a um valor. Ele é construído sobre uma tabela de hash, oferecendo desempenho médio O(1) para suas operações.

Exemplo de Uso

#include <iostream>
#include <unordered_map>
#include <string>
#include <vector>

// Função auxiliar para imprimir o conteúdo do multimap
void imprimirMultimap(const std::unordered_multimap<std::string, int>& umm) {
    for (const auto& par : umm) {
        std::cout << "<" << par.first << ", " << par.second >> " ";
    }
    std::cout << std::endl;
}

int main() {
    // Inicialização com lista de inicialização
    std::unordered_multimap<std::string, int> umm2 =
    {
        { "apple", 1 }, { "ball", 2 }, { "apple", 10 },
        { "cat", 7 }, { "dog", 9 }, { "cat", 6 }, { "apple", 1 }
    };

    // Copiando para outro multimap
    std::unordered_multimap<std::string, int> umm1 = umm2;

    std::cout << "Conteúdo de umm1:" << std::endl;
    imprimirMultimap(umm1);

    if (umm2.empty()) {
        std::cout << "Multimap 2 está vazio." << std::endl;
    } else {
        std::cout << "Multimap 2 não está vazio." << std::endl;
    }

    std::cout << "Tamanho de umm1: " << umm1.size() << std::endl;

    // Buscando uma chave
    std::string chave = "apple";
    auto it = umm1.find(chave);
    if (it != umm1.end()) {
        std::cout << "\nChave '" << chave << "' encontrada." << std::endl;
        // Acessando um dos valores associados à chave
        std::cout << "Um dos valores associados a '" << chave << "' é " << it->second << std::endl;
    } else {
        std::cout << "\nChave '" << chave << "' não encontrada." << std::endl;
    }

    // Contando o número de valores associados a uma chave
    int contagem = umm1.count(chave);
    std::cout << "Total de valores associados a '" << chave << "': " << contagem << std::endl;

    std::cout << "\nConteúdo de umm2 antes da inserção:" << std::endl;
    imprimirMultimap(umm2);

    // Inserções
    umm2.insert({"dog", 11});
    umm2.insert({{"alpha", 12}, {"beta", 33}});
    std::cout << "\nApós inserções:" << std::endl;
    imprimirMultimap(umm2);

    // Removendo todas as ocorrências de uma chave
    umm2.erase("apple");
    std::cout << "\nApós remover a chave 'apple':" << std::endl;
    imprimirMultimap(umm2);

    umm1.clear();
    umm2.clear();

    if (umm2.empty()) {
        std::cout << "\nMultimap 2 agora está vazio." << std::endl;
    }

    return 0;
}

Considerações Importantes sobre unordered_multimap

• O operador [] não está disponível, pois não é possível garantir qual dos múltiplos valores associados a uma chave seria acessado ou modificado.
• A função erase(chave) remove *todos* os pares chave-valor associados à chave fornecida.
• A função find(chave) retorna um iterador para *uma* das ocorrências do par chave-valor.

Acessando/Removendo um Valor Específico

Para verificar a existência ou remover um valor específico associado a uma chave, é necessário iterar sobre os elementos e verificar manualmente o valor. Se encontrado, um iterador para essa posição pode ser usado com erase(iterador) para remover apenas essa ocorrência específica.

#include <iostream>
#include <unordered_map>
#include <string>
#include <vector>

// Função auxiliar para imprimir o conteúdo do multimap
void imprimirMultimap(std::unordered_multimap<std::string, int>& umm) {
    for (const auto& par : umm) {
        std::cout << "<" << par.first << ", " << par.second >> " ";
    }
    std::cout << std::endl;
}

int main() {
    std::unordered_multimap<std::string, int> umm =
    {
        { "apple", 1 }, { "ball", 2 }, { "apple", 10 },
        { "cat", 7 }, { "dog", 9 }, { "cat", 6 },
        { "apple", 1 } // Duplicata de valor para 'apple'
    };

    std::cout << "Multimap original:" << std::endl;
    imprimirMultimap(umm);

    int valor_desejado = 1;
    auto it = umm.begin();
    // Itera para encontrar a primeira ocorrência do valor desejado
    while (it != umm.end()) {
        if (it->second == valor_desejado) {
            break; // Encontrou o valor
        }
        ++it;
    }

    // Remove a ocorrência encontrada se ela existir
    if (it != umm.end()) {
        umm.erase(it);
        std::cout << "\nApós remover uma ocorrência do valor " << valor_desejado << ":" << std::endl;
        imprimirMultimap(umm);
    } else {
        std::cout << "\nValor " << valor_desejado << " não encontrado." << std::endl;
    }

    return 0;
}

Os métodos disponíveis para unordered_multimap são amplamente semelhantes aos do unordered_multiset, cobrindo operações de inserção, busca, remoção, gerenciamento de buckets e fatores de carga.