Contenedores asociativos no ordenados (C++)

En C++ , los contenedores asociativos no ordenados o colecciones asociativas no ordenadas son un grupo de plantillas de clase en la biblioteca estándar de C++ que implementan variantes de tablas hash . Al ser plantillas , se pueden usar para almacenar elementos arbitrarios, como enteros o clases personalizadas. Al igual que todos los demás componentes de la biblioteca estándar, residen en el espacio de nombresstd .

Los siguientes contenedores están definidos en la revisión actual del estándar C++:

• std::unordered_set<T>
• std::unordered_map<K, V>
• std::unordered_multiset<T>
• std::unordered_multimap<K, V>.

Cada uno de estos contenedores se diferencia únicamente en las restricciones impuestas a sus elementos.

std::unordered_sety std::unordered_multisetse declaran en el encabezado <unordered_set>, mientras que std::unordered_mapy std::unordered_multimapse declaran en el encabezado <unordered_map>.

También existen versiones de estas colecciones en el espacio de nombres std::pmr(para recursos de memoria polimórficos). Estas versiones especifican el parámetro de plantilla opcional Allocatorcomo std::pmr::polymorphic_allocator.

Los contenedores asociativos no ordenados son similares a los contenedores asociativos de la biblioteca estándar de C++, pero presentan restricciones diferentes. Como su nombre indica, los elementos de los contenedores asociativos no ordenados no están ordenados . Esto se debe al uso de funciones hash para almacenar los objetos. Aun así, se puede iterar sobre ellos como sobre un contenedor asociativo convencional.

std::unordered_mapy std::unordered_setson esencialmente (respectivamente) equivalentes a java.util.HashMapy java.util.HashSetde Java , System.Collections.Generic.Dictionaryy System.Collections.Generic.HashSetde .NET , o std::collections::HashMapy std::collections::HashSetde Rust .

La primera implementación ampliamente utilizada de tablas hash en el lenguaje C++ fueron hash_maplas plantillas hash_setde hash_multimapclase hash_multisetde la Biblioteca de Plantillas Estándar ( STL) de Silicon Graphics (SGI). ^{[ 1 ]} Debido a su utilidad, posteriormente se incluyeron en varias otras implementaciones de la Biblioteca Estándar de C++ (por ejemplo, la libstdc++ de la Colección de Compiladores GNU (GCC) ^{[ 2 ]} y la biblioteca estándar de Visual C++ (MSVC).

Las hash_*plantillas de clase se propusieron en el Informe Técnico 1 de C++ (C++ TR1) y se aceptaron con los nombres unordered_*. ^{[ 3 ]} Posteriormente, se incorporaron a la revisión C++11 del estándar C++. ^{[ 4 ]} También hay una implementación disponible en las bibliotecas Boost C++ como <boost/unordered_map.hpp>. ^{[ 5 ]}

Los contenedores se definen en encabezados que llevan el nombre de los contenedores, por ejemplo, unordered_setse define en el encabezado <unordered_set>. Todos los contenedores satisfacen los requisitos del concepto de Contenedor , lo que significa que tienen los métodos , , , , , y .begin()end()size()max_size()empty()swap()

Para usar objetos personalizados en std::unordered_map, se debe definir un hash personalizado. Esta función toma una referencia constante al tipo personalizado y devuelve un size_t.

importar std ;using std :: hash ; struct Vector3 { int i ; int j ; int k ; };struct HashVector3 { size_t operator ()( const Vector3 & x ) const { return hash < int > ()( x . i ) ^ hash < int > ()( x . j ) ^ hash < int > ()( x . k ); } };

La función definida por el usuario se puede usar tal cual std::unordered_map, pasándola como parámetro de plantilla.

unordered_map < Vector3 , int , HashVector3 > myPointToIntMap ;

O se puede establecer como la función hash predeterminada especializándola std::hash:

espacio de nombres std { plantilla <> clase hash < Vector3 > { público : size_t operador ()( const Vector3 & x ) const { return hash < int > ()( x . i ) ^ hash < int > ()( x . j ) ^ hash < int > ()( x . k ); } }; }//... unordered_map < Vector3 , int > myPointToIntMap ;

• Contenedor de secuencia (C++)
• Contenedores asociativos (C++)