CKTIS / C++
std::unordered_set — un conjunto de claves únicas
std::unordered_set almacena claves únicas mediante hashing. Permite comprobar si hay elementos, insertarlos y eliminarlos, sin garantizar el orden de iteración. Las operaciones habituales tienen una complejidad media constante, pero lineal en el peor caso.
Versión: C++23; repository compiler flag, production runtime not attested
Sintaxis
#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>, es un contenedor asociativo no ordenado: cada elemento también es su clave y el conjunto contiene como máximo un elemento de cada clase de equivalencia. Los parámetros Hash y Pred definen el hashing y la equivalencia; sus valores predeterminados son std::hash<Key> y std::equal_to<Key>. Las claves equivalentes deben tener el mismo hash; tener hashes iguales no implica que sean equivalentes.
insert(value).second indica si se añadió un elemento. contains(value) comprueba si está presente, find(value) devuelve un iterador o end(), y erase(value) devuelve el número de elementos eliminados: en este caso, 0 o 1. La búsqueda, la inserción de un solo elemento y la eliminación por clave tienen una complejidad media O(1) y una complejidad O(n) en el peor caso.
El orden de iteración no está especificado. No se pueden modificar las claves mediante iteradores; en su lugar, elimina la clave antigua e inserta una nueva. Un rehash invalida los iteradores, pero no los punteros ni las referencias a los elementos. Una inserción puede provocar un rehash; reserve(n) prepara suficientes cubetas para n elementos con el factor de carga máximo actual y también puede invalidar iteradores. Al eliminar un elemento, se invalidan sus iteradores, punteros y referencias.
El ejemplo no muestra los elementos mediante iteración, así que la salida esperada no depende de su orden. Esta entrada está dirigida a C++23; una opción del compilador del repositorio no acredita el entorno de producción. El borrador de trabajo proporcionado se actualiza con el tiempo y puede incluir funciones posteriores a C++23.
Ejemplos
#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
El código mostrado y el resultado declarado se verificaron en un entorno aislado mediante el método registrado en la evidencia de verificación de esta versión exacta.