mapa_desordenat és un contenidor associat que emmagatzema elements formats per la combinació d'un valor clau i un valor mapa. El valor de la clau s'utilitza per identificar de manera única l'element i el valor assignat és el contingut associat a la clau. Tant la clau com el valor poden ser de qualsevol tipus predefinits o definits per l'usuari. En termes senzills, an mapa_desordenat és com una estructura de dades de tipus diccionari que emmagatzema elements en si mateix. Conté parells successius (clau, valor), que permeten recuperar ràpidament un element individual en funció de la seva clau única.
cadena de matriu c
Internament, unordered_map s'implementa mitjançant Hash Table , la clau proporcionada per mapejar es resumeix en índexs d'una taula hash, per això el rendiment de l'estructura de dades depèn molt de la funció hash, però de mitjana, el cost de cercar, inserir i eliminar de la taula hash és O(1).
Nota: En el pitjor dels casos, la seva complexitat temporal pot anar de O(1) a O(n), especialment per als nombres primers grans. En aquesta situació, és molt recomanable utilitzar un mapa per evitar un error TLE (Time Limit Exceeded).
Sintaxi:
sintaxi del mapa_desordenat
A continuació es mostra el programa C++ per demostrar un mapa no ordenat:
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>umap; // inserint valors mitjançant l'operador [] umap['techcodeview.com'] = 10; umap['Pràctica'] = 20; umap['Contribueix'] = 30; // Travessant un mapa no ordenat per a (auto x : umap) cout<< x.first << ' ' << x.second << endl; }> |
>
>Sortida
Contribute 30 Practice 20 techcodeview.com 10>
Unordered_map Sortida
Explicació: L'específic que aquesta sortida justifica és que el valor del resultat de unordered_map es produeix de manera aleatòria clau a valor, mentre que el mapa mostra valor i clau de manera ordenada.
unordered_map vs unordered_set
| Unordered_map | Conjunt_no ordenat |
|---|---|
| Unordered_map conté elements només en forma de parells (clau-valor). | Unordered_set no conté necessàriament elements en forma de parells clau-valor, aquests s'utilitzen principalment per veure la presència/absència d'un conjunt. |
| Operador ' []’ per extreure el valor corresponent d'una clau que està present al mapa. | La cerca d'un element es fa mitjançant a trobar () funció. Per tant, no cal cap operador[]. |
Nota: Per exemple, considereu el problema de comptar les freqüències de paraules individuals. No podem utilitzar unordered_set (o set) ja que no podem emmagatzemar els recomptes mentre podem utilitzar unordered_map.
unordered_map vs map
| Unordered_map | Mapa |
|---|---|
| La clau unordered_map es pot emmagatzemar en qualsevol ordre. | El mapa és una seqüència ordenada de claus úniques |
| Unordered_Map implementa una estructura d'arbre desequilibrada a causa de la qual no és possible mantenir l'ordre entre els elements | Map implementa una estructura d'arbre equilibrada, per això és possible mantenir l'ordre entre els elements (mitjançant un recorregut específic de l'arbre) |
| La complexitat temporal de les operacions unordered_map és O(1) de mitjana. | La complexitat temporal de les operacions del mapa és O(log n) |
Mètodes a unordered_map
Hi ha moltes funcions disponibles que funcionen a unordered_map. Els més útils d'ells són:
- operador = operador [] mida buida per a l'inici i el final de la capacitat per a l'iterador. trobar i comptar per a la cerca. inserir i esborrar per modificar-lo.
La taula següent mostra la llista completa dels mètodes d'un mapa_desordenat:
| Mètodes/Funcions | Descripció |
|---|---|
| a() | Aquesta funció en C++ unordered_map retorna la referència al valor amb l'element com a clau k |
| començar () | Retorna un iterador que apunta al primer element del contenidor del contenidor unordered_map |
| final() | Retorna un iterador que apunta a la posició més enllà de l'últim element del contenidor del contenidor unordered_map |
| cubell() | Retorna el número de cub on es troba l'element amb la clau k al mapa |
| bucket_count | Bucket_count s'utilitza per comptar el número total. de cubs al mapa_desordenat. No cal cap paràmetre per passar a aquesta funció |
| mida_cubeta | Retorna el nombre d'elements de cada cub del mapa_desordenat |
| comptar () | Compteu el nombre d'elements presents en un mapa_desordenat amb una clau determinada |
| rang_igual | Retorna els límits d'un rang que inclou tots els elements del contenidor amb una clau que es compara igual a k |
| trobar () | Retorna l'iterador a l'element |
| buit() | Comprova si el contenidor està buit al contenidor unordered_map |
| esborra () | Esborra els elements del contenidor del contenidor unordered_map |
La biblioteca C++11 també ofereix funcions per veure el recompte de cubs utilitzats internament, la mida del cub, i també la funció hash utilitzada i diverses polítiques hash, però són menys útils en aplicacions reals. Podem iterar sobre tots els elements de unordered_map utilitzant 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 = { //inserint element directament al mapa {'Un', 1}, {'Dos', 2}, {'Tres', 3} }; // inserint valors mitjançant l'operador [] umap['PI'] = 3.14; umap['arrel2'] = 1.414; umap['arrel3'] = 1,732; umap['log10'] = 2,302; umap['loge'] = 1.0; // inserint valor mitjançant la funció d'inserció umap.insert(make_pair('e', 2.718)); clau de cadena = 'PI'; // Si la clau no es troba a l'iterador de mapes // al final es retorna si (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; cout<< '
All Elements :
'; for (itr = umap.begin(); itr != umap.end(); itr++) { // itr works as a pointer to // pair type // itr->primer emmagatzema la part clau i // itr->segon emmagatzema la part de valor cout ' '<< itr->segon<< endl; } }> |
>
>Sortida
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>
Cerca freqüències de paraules individuals
Donada una cadena de paraules, la tasca és trobar les freqüències de les paraules individuals:
Entrada: str = geeks for geeks geeks quiz practice qa for;
Sortida: Les freqüències de paraules individuals són
(pràctica, 1)
(per a, 2)
(qa, 1)
(qüestionari, 1)
(frikis, 3)
A continuació es mostra el programa C++ per implementar l'enfocament anterior:
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>wordFreq; // dividint l'entrada en paraula utilitzant // string stream // S'utilitza per dividir paraules stringstream ss(str); // Per emmagatzemar paraules individuals string word; mentre que (ss>> paraula) wordFreq[paraula]++; // ara iterant sobre word, freq pair // i imprimint-los en format unordered_mapint>:: iterator p; for (p = wordFreq.begin(); p != wordFreq.end(); p++) cout<< '(' ', ' << p->segon<< ')
'; } // Driver code int main() { string str = 'geeks for geeks geeks quiz ' 'practice qa for'; printFrequencies(str); return 0; }> |
>
>Sortida
connectivitat java
(practice, 1) (for, 2) (qa, 1) (quiz, 1) (geeks, 3)>
Articles recents a unordered_map