CKTIS / C++
std::unordered_set — um conjunto de chaves únicas
std::unordered_set armazena chaves únicas através de hashing. Permite verificar a presença, inserir e remover elementos sem garantir a ordem de iteração. As operações comuns têm complexidade média constante, mas linear no pior caso.
Versão: C++23; repository compiler flag, production runtime not attested
Sintaxe
#include <unordered_set>
std::unordered_set<Key, Hash, Pred, Allocator> values;
// Defaults: Hash = std::hash<Key>, Pred = std::equal_to<Key>,
// Allocator = std::allocator<Key>std::unordered_set, de <unordered_set>, é um contentor associativo não ordenado: cada elemento é também a sua chave, e o conjunto contém, no máximo, um elemento de cada classe de equivalência. Os parâmetros Hash e Pred definem o hashing e a equivalência; por predefinição, são std::hash<Key> e std::equal_to<Key>. As chaves equivalentes têm de ter o mesmo hash; hashes iguais não significam que as chaves sejam equivalentes.
insert(value).second indica se foi adicionado um elemento. contains(value) verifica se está presente, find(value) devolve um iterador ou end(), e erase(value) devolve o número de elementos removidos: neste caso, 0 ou 1. A pesquisa, a inserção de um único elemento e a remoção por chave têm complexidade média O(1) e complexidade O(n) no pior caso.
A ordem de iteração não é especificada. Não é possível alterar chaves através de iteradores; em vez disso, remove-se a chave antiga e insere-se uma nova. Um rehash invalida iteradores, mas não ponteiros nem referências aos elementos. Uma inserção pode desencadear um rehash; reserve(n) prepara baldes suficientes para n elementos com o fator de carga máximo atual e também pode invalidar iteradores. A remoção de um elemento invalida os respetivos iteradores, ponteiros e referências.
O exemplo não apresenta os elementos por iteração, pelo que o resultado esperado não depende da sua ordem. Esta entrada destina-se a C++23; uma opção do compilador no repositório não certifica o ambiente de produção. O projeto de trabalho fornecido é atualizado ao longo do tempo e pode conter funcionalidades posteriores a C++23.
Exemplos
#include <iostream>
#include <unordered_set>
int main() {
std::unordered_set<int> values{3, 1, 3};
const bool inserted = values.insert(1).second;
std::cout << std::boolalpha;
std::cout << "inserted: " << inserted << '\n';
std::cout << "contains 3: " << values.contains(3) << '\n';
std::cout << "erased: " << values.erase(3) << '\n';
std::cout << "size: " << values.size() << '\n';
}
Resultado
inserted: false contains 3: true erased: 1 size: 1
O código apresentado e o resultado declarado foram verificados num ambiente isolado pelo método registado na prova de verificação desta versão exata.