Associative containers (C++)

In C++, associative containers or associative collections are a group of class templates in the standard library that implement ordered associative arrays.^[1] Being templates, they can be used to store arbitrary elements, such as integers or custom classes. Like all other standard library components, they reside in namespacestd.

The following containers are defined in the current revision of the C++ standard:

std::set<T>
std::map<K, V>
std::multiset<T>
std::multimap<K, V>

Each of these containers differ only on constraints placed on their elements.

There are also versions of these collections in namespace std::pmr (for polymorphic memory resources). These versions specify the optional template parameter Allocator as std::pmr::polymorphic_allocator.

std::set and std::multiset are declared in header <set>, while std::map and std::multimap are declared in header <map>.

The associative containers are similar to the unordered associative containers in C++ standard library, the only difference is that the unordered associative containers, as their name implies, do not order their elements.

std::map and std::set are usually implemented as red-black trees,^[2] and are essentially (respectively) equivalent to java.util.TreeMap and java.util.TreeSet from Java, System.Collections.Generic.SortedDictionary and System.Collections.Generic.SortedSet from .NET, or std::collections::BTreeMap and std::collections::BTreeSet from Rust.

Design

Characteristics

Key uniqueness: in map and set each key must be unique. multimap and multiset do not have this restriction.
Element composition: in map and multimap each element is composed from a key and a mapped value. In set and multiset each element is key; there are no mapped values.
Element ordering: elements follow a strict weak ordering^[1]

Associative containers are designed to be especially efficient in accessing its elements by their key, as opposed to sequence containers which are more efficient in accessing elements by their position.^[1] Associative containers are guaranteed to perform operations of insertion, deletion, and testing whether an element is in it, in logarithmic time – $O(\log(n))$ Por lo general, se implementan mediante árboles de búsqueda binaria autoequilibrados y admiten iteración bidireccional. Los iteradores y las referencias no se invalidan con las operaciones de inserción y borrado, excepto los iteradores y las referencias a elementos borrados. La característica definitoria de los contenedores asociativos es que los elementos se insertan en un orden predefinido, como por ejemplo, ordenados de forma ascendente.

Los contenedores asociativos se pueden agrupar en dos subconjuntos: mapas y conjuntos. Un mapa, a veces llamado diccionario, consta de un par clave/valor. La clave se usa para ordenar la secuencia y el valor está asociado de alguna manera con esa clave. Por ejemplo, un mapa podría contener claves que representan cada palabra única en un texto y valores que representan la cantidad de veces que esa palabra aparece en el texto. Un conjunto es simplemente un contenedor ascendente de elementos únicos.

Como se indicó anteriormente, mapsolo setse permite insertar una instancia de una clave o elemento en el contenedor. Si se requieren varias instancias de elementos, utilice multimapo multiset.

Tanto los mapas como los conjuntos admiten iteradores bidireccionales. Para obtener más información sobre los iteradores, consulte Iteradores .

Aunque no forman parte oficialmente del estándar STL , hash_mapse hash_setutilizan comúnmente para mejorar los tiempos de búsqueda. Estos contenedores almacenan sus elementos como una tabla hash , donde cada entrada de la tabla contiene una lista enlazada bidireccional de elementos. Para garantizar los tiempos de búsqueda más rápidos ( $O(1)$ ), asegúrese de que el algoritmo de hash para sus elementos devuelva valores hash distribuidos uniformemente.

Actuación

La complejidad asintótica de las operaciones que se pueden aplicar a los contenedores asociativos es la siguiente:

Los conjuntos no ordenados suelen ser más eficientes que los conjuntos ordenados, ya que las operaciones de inserción, eliminación y búsqueda se realizan en $O(n)$ tiempo.

Descripción general de las funciones

Los contenedores se definen en encabezados que llevan el nombre de los contenedores, por ejemplo, setse define en el encabezado <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()

Uso

El siguiente código demuestra cómo usar map<string, int>para contar ocurrencias de palabras. Usa la palabra como keyy el conteo como value.

importar std ;using std :: cin ; using std :: map ; using std :: string ;int main ( int argc , char * argv []) { map < string , int > wordCounts ; string s ;while ( cin >> s && s != "end" ) { ++ wordCounts [ s ]; } while ( cin >> s && s != "end" ) { std :: println ( "{} {}" , s , wordCounts [ s ]); } return 0 ; }

Al ejecutarse, el programa permite al usuario escribir una serie de palabras separadas por espacios y la palabra "fin" para indicar el final de la entrada. A continuación, el usuario puede introducir una palabra para consultar cuántas veces ha aparecido en la serie introducida previamente.

El ejemplo anterior también demuestra que el operador []inserta nuevos objetos (usando el constructor predeterminado) en el mapa si no hay ninguno asociado a la clave. Así, los tipos enteros se inicializan a cero, las cadenas se inicializan como cadenas vacías, etc.

El siguiente ejemplo ilustra cómo insertar elementos en un mapa utilizando la función de inserción y cómo buscar una clave utilizando un iterador de mapa y la función de búsqueda:

importar std ;usando TreeMapOfCharInt = std :: map < char , int > ;using std :: cin ; using std :: pair ;int main () { TreeMapOfCharInt myMap ;// Insertar elementos usando la función de inserción myMap . insert ( pair < char , int > ( 'a' , 1 )); myMap . insert ( pair < char , int > ( 'b' , 2 )); myMap . insert ( pair < char , int > ( 'c' , 3 )); // También puedes insertar elementos de una manera diferente como se muestra a continuación // Usando la función value_type que proporcionan todos los contenedores estándar myMap . insert ( TreeMapOfCharInt :: value_type ( 'd' , 4 )); // Usando la función de utilidad make_pair myMap . insert ( std :: make_pair ( 'e' , 5 )); // Usando la lista de inicialización de C++11 myMap . insert ({ 'f' , 6 }); // Las claves del mapa se ordenan automáticamente de menor a mayor. // Por lo tanto, myMap.begin() apunta al valor de clave más bajo, no a la clave que se insertó primero. TreeMapOfCharInt :: iterator iter = myMap . comenzar ();// Borra el primer elemento usando la función erase myMap . erase ( iter );// Imprime el tamaño del mapa usando la función size std :: println ( " Tamaño de myMap: {}" , myMap.size ());std :: println ( "Ingrese una clave para buscar: " ); char c ; cin >> c ;// find devolverá un iterador al elemento coincidente si se encuentra // o al final del mapa si no se encuentra la clave iter = myMap . find ( c ); if ( iter != myMap . end ()) { std :: println ( "Para la clave {}, el valor es: {}" , iter -> first , iter -> second ); } else { std :: println ( "La clave {} no está en myMap" , iter -> first ); }// Borra las entradas del mapa usando la función clear myMap.clear ( ) ; return 0 ; }

El ejemplo mostrado arriba demuestra el uso de algunas de las funciones proporcionadas por map, como insert()(colocar elemento en el mapa), erase()(eliminar elemento del mapa), find()(verificar la presencia del elemento en el contenedor), etc.

Cuando se ejecuta el programa, se insertan seis elementos usando la insert()función, luego se elimina el primer elemento usando erase()la función y se muestra el tamaño del mapa. A continuación, se le pide al usuario que ingrese una clave para buscar en el mapa. Usando el iterador creado anteriormente, la find()función busca un elemento con la clave dada. Si encuentra la clave, el programa imprime el valor del elemento. Si no lo encuentra, se devuelve un iterador al final del mapa y se muestra que no se pudo encontrar la clave. Finalmente, todos los elementos en el árbol se borran usando clear().

Iteradores

Los mapas pueden usar iteradores para apuntar a elementos específicos en el contenedor. Un iterador puede acceder tanto a la clave como al valor mapeado de un elemento: ^{[ 1 ]}

// Declara un iterador de mapa std :: map < Key , Value >:: iterator it ;// Accede al valor de la clave it -> first ;// Accede al valor mapeado it -> second ;// El "valor" del iterador, que es de tipo std::pair<const Key, Value> ( * it );

A continuación se muestra un ejemplo de cómo recorrer un mapa para mostrar todas las claves y valores utilizando iteradores:

importar std ;using std :: map ; using std :: string ;int main ( int argc , char * argv []) { map < string , int > data { { "Puntuación de Bob" , 10 }, { "Puntuación de Marty" , 15 }, { "Puntuación de Mehmet" , 34 }, { "Puntuación de Rocky" , 22 }, // Los siguientes valores se ignoran porque los elementos con las mismas claves ya están en el mapa { "Puntuación de Rocky" , 23 }, { "Puntuación de Mehmet" , 33 } }; // Iterar sobre el mapa e imprimir todos los pares clave/valor. for ( const auto & [ key , value ] : data ) { std :: println ( "Quién (clave = primero): {}" , key ); std :: println ( "Puntuación (valor = segundo): {}" , value ); } // Si es necesario, puede iterar sobre el mapa usando un iterador. // Tenga en cuenta que el nombre de tipo largo del iterador en este caso se puede reemplazar con la palabra clave auto. for ( map < string , int >:: iterator iter = data . begin (); iter != data . end (); ++ iter ) { std :: println ( "Quién (clave = primero): {}" , iter -> first ); std :: println ( "Puntuación (valor = segundo): {}" , iter -> second ); }devolver 0 ; }

Véase también

Referencias

1 2 3 4 ISO/IEC 14882:2011 borrador de especificación (PDF) . pág. 797, § 23.4.4.
↑ "std::map - cppreference.com" . cppreference.com . Consultado el 2 de septiembre de 2025 .

[std-1] 1 2 3 4 ISO/IEC 14882:2011 borrador de especificación (PDF) . pág. 797, § 23.4.4.

[2] "std::map - cppreference.com" . cppreference.com . Consultado el 2 de septiembre de 2025 .

[1]

[2]