hartă_neordonată este un container asociat care stochează elemente formate din combinația dintre o valoare cheie și o valoare mapată. Valoarea cheii este utilizată pentru a identifica în mod unic elementul, iar valoarea mapată este conținutul asociat cheii. Atât cheia, cât și valoarea pot fi de orice tip predefinite sau definite de utilizator. În termeni simpli, an hartă_neordonată este ca o structură de date de tip dicționar care stochează elemente în sine. Conține perechi succesive (cheie, valoare), care permite recuperarea rapidă a unui element individual pe baza cheii sale unice.
scrieți json în fișierul python
Intern unordered_map este implementat folosind Hash Table , cheia furnizată pentru mapare este hashing în indici ai unui tabel hash, motiv pentru care performanța structurii de date depinde foarte mult de funcția hash, dar, în medie, costul căutați, inserați și ștergeți din tabelul hash este O(1).
Notă: În cel mai rău caz, complexitatea sa de timp poate merge de la O(1) la O(n), în special pentru numere prime mari. În această situație, este foarte recomandabil să folosiți o hartă pentru a evita obținerea unei erori TLE (Time Limit Exceeded).
Sintaxă:
sintaxă neordonată_map
Mai jos este programul C++ pentru a demonstra o hartă neordonată:
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; // inserarea valorilor folosind operatorul [] umap['techcodeview.com'] = 10; umap['Practice'] = 20; umap['Contribuie'] = 30; // Parcurgerea unei hărți neordonate pentru (auto x : umap) cout<< x.first << ' ' << x.second << endl; }> |
>
>Ieșire
Contribute 30 Practice 20 techcodeview.com 10>
Unordered_map Ieșire
Explicaţie: Lucrul specific pe care îl justifică această ieșire este că valoarea rezultatului nonordered_map este produsă într-o manieră aleatorie de la cheie la valoare, în timp ce harta afișează valoarea și cheia într-o manieră ordonată.
unordered_map vs unordered_set
| Hartă_neordonată | Unordered_set |
|---|---|
| Unordered_map conține elemente numai sub formă de perechi (cheie-valoare). | Unordered_set nu conține neapărat elemente sub formă de perechi cheie-valoare, acestea fiind folosite în principal pentru a vedea prezența/absența unui set. |
| operator’ []' pentru a extrage valoarea corespunzătoare a unei chei care este prezentă pe hartă. | Căutarea unui element se face folosind a găsi () funcția. Deci nu este nevoie de un operator[]. |
Notă: De exemplu, luați în considerare problema numărării frecvențelor cuvintelor individuale. Nu putem folosi unordered_set (sau set), deoarece nu putem stoca contoare în timp ce putem folosi unordered_map.
unordered_map vs map
| Hartă_neordonată | Hartă |
|---|---|
| Cheia unordered_map poate fi stocată în orice ordine. | Harta este o secvență ordonată de chei unice |
| Unordered_Map implementează o structură arborescentă dezechilibrată din cauza căreia nu este posibilă menținerea ordinii între elemente | Harta implementează o structură arborescentă echilibrată, motiv pentru care este posibilă menținerea ordinii între elemente (prin traversarea specifică a arborelui) |
| Complexitatea de timp a operațiunilor neordonate_map este O(1) în medie. | Complexitatea temporală a operațiunilor cu hărți este O(log n) |
Metode de pe harta_nordonată
Sunt disponibile o mulțime de funcții care funcționează pe unordered_map. Cele mai utile dintre ele sunt:
- operator = operator [] dimensiune goală pentru începutul și sfârșitul capacității pentru iterator. găsiți și numărați pentru căutare. introduceți și ștergeți pentru modificare.
Tabelul de mai jos arată lista completă a metodelor unei hărți neordonate:
| Metode/Funcții | Descriere |
|---|---|
| la() | Această funcție din C++ unordered_map returnează referința la valoarea cu elementul ca cheie k |
| ÎNCEPE() | Returnează un iterator care indică primul element din containerul din containerul unordered_map |
| Sfârşit() | Returnează un iterator care indică poziția dincolo de ultimul element din containerul din containerul unordered_map |
| găleată() | Returnează numărul compartimentului în care se află elementul cu cheia k în hartă |
| bucket_count | Bucket_count este folosit pentru a număra numărul total. de găleți în harta_neordonată. Nu este necesar niciun parametru pentru a trece în această funcție |
| bucket_size | Returnează numărul de elemente din fiecare găleată a hărții_neordonate |
| numara() | Numărați numărul de elemente prezente într-o hartă neordonată cu o cheie dată |
| interval_egal | Returnează limitele unui interval care include toate elementele din container cu o cheie care se compară egală cu k |
| găsi() | Returnează iteratorul la element |
| gol() | Verifică dacă containerul este gol în containerul unordered_map |
| şterge() | Ștergeți elementele din container din containerul unordered_map |
Biblioteca C++11 oferă, de asemenea, funcții pentru a vedea numărul de compartimente utilizate intern, dimensiunea compartimentului și, de asemenea, funcția hash utilizată și diverse politici hash, dar sunt mai puțin utile în aplicațiile reale. Putem repeta peste toate elementele unordered_map folosind 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 = { //inserând elementul direct în harta {'Unu', 1}, {'Doi', 2}, {'Trei', 3} }; // inserarea valorilor folosind operatorul [] umap['PI'] = 3.14; umap['root2'] = 1,414; umap['root3'] = 1,732; umap['log10'] = 2,302; umap['loge'] = 1.0; // inserarea valorii prin funcția de inserare umap.insert(make_pair('e', 2.718)); cheie șir = 'PI'; // Dacă cheia nu a fost găsită în iteratorul hărții // la final este returnată dacă (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>::iterator itr; cout<< '
All Elements :
'; for (itr = umap.begin(); itr != umap.end(); itr++) { // itr works as a pointer to // pair type // itr->mai întâi stochează partea cheie și // itr->al doilea stochează partea de valoare cout ' '<< itr->al doilea<< endl; } }> |
>
>Ieșire
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>
Găsiți frecvențele cuvintelor individuale
Având în vedere un șir de cuvinte, sarcina este de a găsi frecvențele cuvintelor individuale:
Intrare: str = geeks for geeks geeks quiz practice qa for;
Ieșire: Frecvențele cuvintelor individuale sunt
(practica, 1)
(pentru, 2)
(qa, 1)
(chestionar, 1)
(tocilari, 3)
Mai jos este programul C++ pentru a implementa abordarea de mai sus:
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; // împărțirea introducerii în cuvânt folosind // string stream // Folosit pentru ruperea cuvintelor stringstream ss(str); // Pentru a stoca cuvinte individuale șir de cuvinte; în timp ce (ss>> cuvânt) cuvântFreq[cuvânt]++; // acum iterează peste cuvânt, pereche de frecvențe // și le imprimă în format nonordered_mapint>:: iterator p; pentru (p = wordFreq.begin(); p != wordFreq.end(); p++) cout<< '(' ', ' << p->al doilea<< ')
'; } // Driver code int main() { string str = 'geeks for geeks geeks quiz ' 'practice qa for'; printFrequencies(str); return 0; }> |
verificarea nulă în java
>
>Ieșire
(practice, 1) (for, 2) (qa, 1) (quiz, 1) (geeks, 3)>
Articole recente pe unordered_map