Contenedores asociativos (C++)

En C++ , los contenedores asociativos o colecciones asociativas son un grupo de plantillas de clase en la biblioteca estándar que implementan arreglos asociativos ordenados . ^{[ 1 ]} 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::set<T>
std::map<K, V>
std::multiset<T>
std::multimap<K, V>

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

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.

std::sety std::multisetse declaran en el encabezado <set>, mientras que std::mapy std::multimapse declaran en el encabezado <map>.

Los contenedores asociativos son similares a los contenedores asociativos no ordenados de la biblioteca estándar de C++ , la única diferencia es que los contenedores asociativos no ordenados, como su nombre indica, no ordenan sus elementos.

std::mapy std::setsuelen implementarse como árboles rojo-negro , ^{[ 2 ]} y son esencialmente (respectivamente) equivalentes a java.util.TreeMapy java.util.TreeSetde Java , System.Collections.Generic.SortedDictionaryy System.Collections.Generic.SortedSetde .NET , o std::collections::BTreeMapy std::collections::BTreeSetde Rust .

Diseño

Características

Unicidad de clave : en mapy setcada clave debe ser única. multimapy multisetno tienen esta restricción.
Composición de elementos : en mapy multimapcada elemento está compuesto por una clave y un valor mapeado. En sety multisetcada elemento es clave; no hay valores mapeados.
Ordenación de elementos : los elementos siguen una ordenación débil estricta ^{[ 1 ]}

Los contenedores asociativos están diseñados para ser especialmente eficientes en el acceso a sus elementos por su clave, a diferencia de los contenedores de secuencia que son más eficientes en el acceso a los elementos por su posición. ^{[ 1 ]} Se garantiza que los contenedores asociativos realicen operaciones de inserción, eliminación y comprobación de si un elemento está en ellos, en tiempo logarítmico. $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 ]