En informática, los contenedores asociativos se refieren a un grupo de plantillas de clase en la biblioteca estándar del lenguaje de programación C ++ que implementan matrices asociativas ordenadas . [1] Al ser plantillas , se pueden usar para almacenar elementos arbitrarios, como enteros o clases personalizadas. Los contenedores siguientes se definen en la versión actual de la C ++ estándar: set
, map
, multiset
, multimap
. Cada uno de estos contenedores difiere solo en las restricciones impuestas a sus elementos.
Los contenedores asociativos son similares a los contenedores asociativos desordenados en la biblioteca estándar de C ++ , la única diferencia es que los contenedores asociativos no ordenados, como su nombre lo indica, no ordenan sus elementos.
Diseño
Caracteristicas
- Unicidad de la clave : en
map
yset
cada clave debe ser única.multimap
ymultiset
no tiene esta restricción. - Composición del elemento : en
map
ymultimap
cada elemento se compone de una clave y un valor mapeado. Enset
ymultiset
cada elemento es clave; no hay valores mapeados. - Orden de los elementos: los elementos siguen un orden estricto y débil [1]
Los contenedores asociativos están diseñados para ser especialmente eficientes en el acceso a sus elementos por su clave, en contraposición a los contenedores secuenciales que son más eficientes en el acceso a los elementos por su posición. [1] Los contenedores asociativos están garantizados para realizar operaciones de inserción, eliminación y comprobación de si un elemento está en él, en tiempo logarítmico - O (log n ). Como tales, normalmente se implementan utilizando árboles de búsqueda binarios autoequilibrados y admiten la iteración bidireccional. Los iteradores y referencias no se invalidan por las operaciones de inserción y de borrado, a excepción de los iteradores y referencias a borrado elements.The característica definitoria de contenedores asociativos es que los elementos se insertan en un orden predefinido, tal como ascendente ordenada.
Los contenedores asociativos se pueden agrupar en dos subconjuntos: mapas y conjuntos. Un mapa, a veces denominado 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 puede contener claves que representan cada palabra única en un texto y valores que representan el número de veces que esa palabra aparece en el texto. Un conjunto es simplemente un contenedor ascendente de elementos únicos.
Tanto el mapa como el conjunto solo permiten insertar una instancia de una clave o elemento en el contenedor. Si se requieren varias instancias de elementos, use multimap o multiset.
Tanto los mapas como los conjuntos admiten iteradores bidireccionales. Para obtener más información sobre iteradores, consulte Iteradores.
Si bien no es oficialmente parte del estándar STL, hash_map y hash_set se usan comúnmente para mejorar los tiempos de búsqueda. Estos contenedores almacenan sus elementos como una tabla hash, y cada entrada de la tabla contiene una lista de elementos enlazados bidireccionalmente. Para garantizar los tiempos de búsqueda más rápidos, asegúrese de que el algoritmo 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:
Operación | Complejidad |
---|---|
Buscando un elemento | O (log n) |
Insertar un nuevo elemento | O (log n) |
Incrementar / decrementar un iterador | O (log n) (amortizado O (1) si solo se realizan incrementos o solo disminuciones) |
Eliminar un solo elemento | O (log n) |
Resumen de funciones
Los contenedores se definen en encabezados nombrados después de los nombres de los contenedores, por ejemplo, set
se define en el encabezado
. Todos los recipientes cumplen los requisitos de la Container concepto , que significa que tienen begin()
, end()
, size()
, max_size()
, empty()
, y swap()
métodos.
set | map | multiset | multimap | Descripción | |
---|---|---|---|---|---|
(constructor) | (constructor) | (constructor) | (constructor) | Construye el contenedor a partir de una variedad de fuentes. | |
(incinerador de basuras) | (incinerador de basuras) | (incinerador de basuras) | (incinerador de basuras) | Destruye el conjunto y los elementos contenidos | |
operator= | operator= | operator= | operator= | Asigna valores al contenedor | |
get_allocator | get_allocator | get_allocator | get_allocator | Devuelve el asignador utilizado para asignar memoria para los elementos. | |
Acceso a elementos | N / A | at | N / A | N / A | Accede al elemento especificado con comprobación de límites. |
N / A | operator[] | N / A | N / A | Accede al elemento especificado sin comprobar los límites. | |
Iteradores | begin | begin | begin | begin | Devuelve un iterador al comienzo del contenedor. |
end | end | end | end | Devuelve un iterador al final del contenedor. | |
rbegin | rbegin | rbegin | rbegin | Devuelve un iterador inverso al principio inverso del contenedor. | |
rend | rend | rend | rend | Devuelve un iterador inverso al final inverso del contenedor | |
Capacidad | empty | empty | empty | empty | Comprueba si el contenedor está vacío |
size | size | size | size | Devuelve el número de elementos del contenedor. | |
max_size | max_size | max_size | max_size | Devuelve el número máximo posible de elementos en el contenedor. | |
Modificadores | clear | clear | clear | clear | Borra el contenido. |
insert | insert | insert | insert | Inserta elementos. | |
emplace | emplace | emplace | emplace | Construye elementos in situ ( C ++ 11 ) | |
emplace_hint | emplace_hint | emplace_hint | emplace_hint | Construye elementos en el lugar usando una pista ( C ++ 11 ) | |
erase | erase | erase | erase | Borra elementos. | |
swap | swap | swap | swap | Intercambia el contenido con otro recipiente. | |
Buscar | count | count | count | count | Devuelve el número de elementos que coinciden con una clave específica. |
find | find | find | find | Encuentra un elemento con clave específica. | |
equal_range | equal_range | equal_range | equal_range | Devuelve un rango de elementos que coinciden con una clave específica. | |
lower_bound | lower_bound | lower_bound | lower_bound | Devuelve un iterador al primer elemento con una clave no menor que el valor dado. | |
upper_bound | upper_bound | upper_bound | upper_bound | Devuelve un iterador al primer elemento con una clave mayor que cierto valor. | |
Observadores | key_comp | key_comp | key_comp | key_comp | Devuelve la función de comparación de teclas. |
value_comp | value_comp | value_comp | value_comp | Devuelve la función de comparación de valores. En set y multiset esta función es equivalente a key_comp , ya que los elementos están compuestos solo por una clave. |
Uso
El siguiente código muestra cómo utilizar map
para contar las apariciones de palabras. Utiliza la palabra como clave y el recuento como valor.
#include #include #include int main () { std :: map < std :: string , int > recuentos de palabras ; std :: string s ; while ( std :: cin >> s && s ! = "end" ) ++ wordcounts [ s ]; while ( std :: cin >> s && s ! = "end" ) std :: cout << s << '' << wordcounts [ s ] << '\ n' ; }
Cuando se ejecuta, el usuario escribe primero una serie de palabras separadas por espacios y una palabra "fin" para indicar el final de la entrada; luego, el usuario puede ingresar palabras para consultar cuántas veces ocurrió cada palabra en la serie anterior.
El ejemplo anterior también demuestra que el operador [] inserta nuevos objetos (usando el constructor predeterminado) en el mapa si no hay uno asociado con la clave. Entonces, los tipos integrales se inicializan en cero, las cadenas se inicializan en cadenas vacías, etc.
El siguiente ejemplo ilustra la inserción de elementos en un mapa usando la función de inserción y la búsqueda de una clave usando un iterador de mapa y la función de búsqueda:
#include #include #include // make_pairint main () { typedef std :: map < char , int > MapType ; MapType my_map ; // inserta elementos usando la función insert my_map . insert ( std :: pair < char , int > ( 'a' , 1 )); my_map . insert ( std :: pair < char , int > ( 'b' , 2 )); my_map . insert ( std :: pair < char , int > ( 'c' , 3 )); my_map . insert ( MapType :: value_type ( 'd' , 4 )); // todos los contenedores estándar proporcionan este typedef my_map . insert ( std :: make_pair ( 'e' , 5 )); // también puede utilizar la función de utilidad make_pair my_map . insertar ({ 'f' , 6 }); // usando la lista de inicializadores de C ++ 11 // las claves del mapa se ordenan automáticamente de menor a mayor. // Entonces, my_map.begin () apunta al valor de clave más bajo, no a la clave que se insertó primero. MapType :: iterador iter = my_map . comenzar (); // borra el primer elemento usando la función borrar my_map . borrar ( iter ); // muestra el tamaño del mapa std :: cout << "Tamaño de my_map:" << my_map . tamaño () << '\ n' ; std :: cout << "Introduzca una clave para buscar:" ; char c ; std :: cin >> c ; // find devolverá un iterador al elemento coincidente si se encuentra // o al final del mapa si no se encuentra la clave iter = my_map . encontrar ( c ); if ( iter ! = my_map . end () ) std :: cout << "El valor es:" << iter -> second << '\ n' ; else std :: cout << "La clave no está en my_map" << '\ n' ; // borra las entradas en el mapa my_map . claro (); }
En el ejemplo anterior, se ingresan seis elementos usando la función de inserción y luego se elimina el primer elemento. Luego, se emite el tamaño del mapa. A continuación, se le pide al usuario que busque una clave. Usando el iterador, la función de búsqueda 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 da como resultado que no se pudo encontrar la clave. Finalmente se borran todos los elementos del árbol.
Iteradores
Los mapas pueden usar iteradores para señalar elementos específicos en el contenedor. Un iterador puede acceder tanto a la clave como al valor mapeado de un elemento: [1]
map < Key , T > :: iterador it ; // declara un iterador de mapa it -> first ; // el valor de la clave es -> segundo ; // el valor mapeado ( * it ); // el "valor del elemento", que es de tipo: par
A continuación se muestra un ejemplo de cómo recorrer un mapa para mostrar todas las claves y valores usando iteradores:
#include #include #include int main () { std :: map < std :: string , int > data { { "Puntaje de Bobs" , 10 }, { "Puntaje de Martys" , 15 }, { "Puntaje de Mehmets" , 34 }, { "Puntaje de Rockys " , 22 }, { " Puntuación de Rockys " , 23 } / * sobrescribe el 22 ya que las teclas son idénticas * / }; // Itere sobre el mapa e imprima todos los pares clave / valor. for ( const auto & element : data ) { std :: cout << "Quién (clave = primero):" << elemento . primero ; std :: cout << "Puntuación (valor = segundo):" << elemento . segundo << '\ n' ; } return 0 ; }
Para compilar el ejemplo anterior en el compilador GCC, debe usar el indicador de selección estándar específico.
g ++ - std = c ++ 11 fuente . cpp - o src
Esto generará las claves y valores de todo el mapa, ordenados por claves.
Referencias
- ^ a b c d ISO / IEC 14882: 2011 borrador de especificación (PDF) . pag. 797, párrafo 23.4.4.
Ver también
- Contenedor (tipo de datos abstracto)
- Biblioteca de plantillas estándar # contenedores