mapa_desordenado es un contenedor asociado que almacena elementos formados por la combinación de un valor clave y un valor mapeado. El valor clave se utiliza para identificar de forma única el elemento y el valor asignado es el contenido asociado con la clave. Tanto la clave como el valor pueden ser de cualquier tipo predefinido o definido por el usuario. En términos simples, una mapa_desordenado Es como una estructura de datos de tipo diccionario que almacena elementos en sí misma. Contiene pares sucesivos (clave, valor), lo que permite una recuperación rápida de un elemento individual en función de su clave única.
clase abstracta vs interfaz
Internamente, unordered_map se implementa utilizando Hash Table, la clave proporcionada para mapear se divide en índices de una tabla hash, razón por la cual el rendimiento de la estructura de datos depende mucho de la función hash, pero en promedio, el costo de buscar, insertar y eliminar de la tabla hash es O(1).
Nota: En el peor de los casos, su complejidad temporal puede ir de O(1) a O(n), especialmente para números primos grandes. En esta situación, es muy recomendable utilizar un mapa para evitar recibir un error TLE (límite de tiempo excedido).
Sintaxis:
sintaxis de mapa_desordenado
A continuación se muestra el programa C++ para demostrar un mapa desordenado:
C++
// C++ program to demonstrate> // functionality of unordered_map> #include> #include> using> namespace> std;> > // Driver code> int> main()> {> >// Declaring umap to be of> >// type key> >// will be of STRING type> >// and mapped VALUE will> >// be of int type> >unordered_mapint>mapa; // insertando valores usando el operador [] umap['techcodeview.com'] = 10; umap['Práctica'] = 20; umap['Contribuir'] = 30; // Atravesando un mapa desordenado para (auto x: umap) cout<< x.first << ' ' << x.second << endl; }> |
>
>Producción
Contribute 30 Practice 20 techcodeview.com 10>
Unordered_map Salida
Explicación: Lo específico que justifica este resultado es que el valor del resultado de unordered_map se produce de forma aleatoria de clave a valor, mientras que el mapa muestra el valor y la clave de forma ordenada.
mapa_desordenado vs conjunto_desordenado
| mapa_desordenado | conjunto_desordenado |
|---|---|
| Unordered_map contiene elementos solo en forma de pares (clave-valor). | Unordered_set no contiene necesariamente elementos en forma de pares clave-valor, estos se utilizan principalmente para ver la presencia/ausencia de un conjunto. |
| Operador ' []’ para extraer el valor correspondiente de una clave que está presente en el mapa. | La búsqueda de un elemento se realiza mediante un encontrar () función. Entonces no es necesario un operador []. |
Nota: Por ejemplo, considere el problema de contar las frecuencias de palabras individuales. No podemos usar unordered_set (o set) ya que no podemos almacenar recuentos mientras podemos usar unordered_map.
mapa_desordenado vs mapa
| mapa_desordenado | Mapa |
|---|---|
| La clave unordered_map se puede almacenar en cualquier orden. | El mapa es una secuencia ordenada de claves únicas. |
| Unordered_Map implementa una estructura de árbol desequilibrada debido a que no es posible mantener el orden entre los elementos | Map implementa una estructura de árbol equilibrada, por lo que es posible mantener el orden entre los elementos (mediante un recorrido de árbol específico) |
| La complejidad temporal de las operaciones unordered_map es O(1) en promedio. | La complejidad temporal de las operaciones de mapas es O (log n) |
Métodos en unordered_map
Hay muchas funciones disponibles que funcionan en unordered_map. Los más útiles de ellos son:
- operador = operador [] tamaño vacío para el inicio y fin de la capacidad del iterador. buscar y contar para la búsqueda. insertar y borrar para modificar.
La siguiente tabla muestra la lista completa de los métodos de un unordered_map:
| Métodos/Funciones | Descripción |
|---|---|
| en() | Esta función en C++ unordered_map devuelve la referencia al valor con el elemento como clave k |
| comenzar() | Devuelve un iterador que apunta al primer elemento del contenedor en el contenedor unordered_map |
| fin() | Devuelve un iterador que apunta a la posición más allá del último elemento del contenedor en el contenedor unordered_map |
| balde() | Devuelve el número del depósito donde se encuentra el elemento con la clave k en el mapa. |
| cuenta_cubos | Bucket_count se utiliza para contar el número total. de depósitos en unordered_map. No se requiere ningún parámetro para pasar a esta función |
| tamaño_cubo | Devuelve el número de elementos en cada depósito de unordered_map |
| contar() | Cuente el número de elementos presentes en un mapa_desordenado con una clave determinada |
| rango_igual | Devuelve los límites de un rango que incluye todos los elementos en el contenedor con una clave que se compara igual a k |
| encontrar() | Devuelve el iterador al elemento. |
| vacío() | Comprueba si el contenedor está vacío en el contenedor unordered_map |
| borrar() | Borrar elementos en el contenedor en el contenedor unordered_map |
La biblioteca C++ 11 también proporciona funciones para ver el recuento de depósitos utilizados internamente, el tamaño de los depósitos y también la función hash utilizada y varias políticas de hash, pero son menos útiles en aplicaciones reales. Podemos iterar sobre todos los elementos de unordered_map usando Iterator.
C++
// C++ program to demonstrate> // Initialization, indexing,> // and iteration> #include> #include> using> namespace> std;> > // Driver code> int> main()> {> >// Declaring umap to be of> >// type key> >// will be of string type and> >// mapped value will be of double type> >unordered_mapdouble>umap = { //insertando elemento directamente en el mapa {'Uno', 1}, {'Dos', 2}, {'Tres', 3} }; // insertando valores usando el operador [] umap['PI'] = 3.14; umap['raíz2'] = 1,414; umap['raíz3'] = 1,732; umap['log10'] = 2,302; umap['loge'] = 1,0; // insertando valor mediante la función de inserción umap.insert(make_pair('e', 2.718)); clave de cadena = 'PI'; // Si la clave no se encuentra en el iterador del mapa // se devuelve al final if (umap.find(key) == umap.end()) cout<< key << ' not found
'; // If key found then iterator to that // key is returned else cout << 'Found ' << key << '
'; key = 'lambda'; if (umap.find(key) == umap.end()) cout << key << ' not found
'; else cout << 'Found ' << key << endl; // iterating over all value of umap unordered_mapdouble>::iterador itr; corte<< '
All Elements :
'; for (itr = umap.begin(); itr != umap.end(); itr++) { // itr works as a pointer to // pair type // itr->primero almacena la parte clave y // itr->segundo almacena la parte de valor cout ' '<< itr->segundo<< endl; } }> |
>
>Producción
Found PI lambda not found All Elements : e 2.718 loge 1 log10 2.302 Two 2 One 1 Three 3 PI 3.14 root2 1.414 root3 1.732>
Encuentra frecuencias de palabras individuales.
Dada una cadena de palabras, la tarea es encontrar las frecuencias de las palabras individuales:
Aporte: str = geeks para geeks geeks prueba práctica qa para;
Producción: Las frecuencias de palabras individuales son
(práctica, 1)
(para 2)
(qa, 1)
(cuestionario, 1)
(frikis, 3)
A continuación se muestra el programa C++ para implementar el enfoque anterior:
tutorial de c#
C++
// C++ program to find freq> // of every word using unordered_map> #include> using> namespace> std;> > // Prints frequencies of> // individual words in str> void> printFrequencies(>const> string &str)> {> >// declaring map of type,> >// each word is mapped to its frequency> >unordered_mapint>frecuencia de palabra; // dividir la entrada en palabra usando // string stream // Usado para dividir palabras stringstream ss(str); // Para almacenar palabras individuales string word; mientras (ss>> palabra) palabraFreq[palabra]++; // ahora iterando sobre palabra, par de frecuencia // e imprimiéndolos en formato unordered_mapint>:: iterator p; para (p = frecuenciapalabra.begin(); p != frecuenciapalabra.end(); p++) cout<< '(' ', ' << p->segundo<< ')
'; } // Driver code int main() { string str = 'geeks for geeks geeks quiz ' 'practice qa for'; printFrequencies(str); return 0; }> |
>
>Producción
(practice, 1) (for, 2) (qa, 1) (quiz, 1) (geeks, 3)>
Artículos recientes sobre unordered_map