unordered_map är en associerad behållare som lagrar element som bildas av kombinationen av ett nyckelvärde och ett mappat värde. Nyckelvärdet används för att unikt identifiera elementet och det mappade värdet är innehållet som är associerat med nyckeln. Både nyckel och värde kan vara av vilken typ som helst fördefinierad eller användardefinierad. Enkelt uttryckt, en unordered_map är som en datastruktur av ordbokstyp som lagrar element i sig själv. Den innehåller på varandra följande par (nyckel, värde), vilket möjliggör snabb hämtning av ett enskilt element baserat på dess unika nyckel.
huggorm full huggorm
Internt unordered_map implementeras med hjälp av Hash Table , nyckeln som tillhandahålls för att mappa hashas till index för en hashtabell, vilket är anledningen till att datastrukturens prestanda beror mycket på hashfunktionen men i genomsnitt kostnaden för söka, infoga och ta bort från hashtabellen är O(1).
Notera: I värsta fall kan dess tidskomplexitet gå från O(1) till O(n), speciellt för stora primtal. I den här situationen är det mycket lämpligt att använda en karta istället för att undvika att få ett TLE(Time Limit Exceeded)-fel.
Syntax:
unordered_map syntax
Nedan är C++-programmet för att demonstrera en oordnad karta:
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; // infoga värden genom att använda [] operator umap['techcodeview.com'] = 10; umap['Övning'] = 20; umap['Bidra'] = 30; // Gå igenom en oordnad karta för (auto x : umap) cout<< x.first << ' ' << x.second << endl; }> |
>
>Produktion
Contribute 30 Practice 20 techcodeview.com 10>
unordered_map Utdata
Förklaring: Det specifika som denna utdata motiverar är att värdet av resultatet av unordered_map produceras på ett slumpmässigt nyckel-till-värde sätt medan kartan visar värde och nyckel på ett ordnat sätt.
unordered_map vs unordered_set
| Oordnad_karta | Unordered_set |
|---|---|
| Unordered_map innehåller endast element i form av (nyckel-värde) par. | Unordered_set innehåller inte nödvändigtvis element i form av nyckel-värdepar, dessa används främst för att se närvaron/frånvaron av en uppsättning. |
| Operatör ' []' för att extrahera motsvarande värde för en nyckel som finns i kartan. | Sökandet efter ett element görs med hjälp av en hitta () funktion. Så inget behov av en operatör[]. |
Notera: Tänk till exempel på problemet med att räkna frekvenserna för enskilda ord. Vi kan inte använda unordered_set (eller set) eftersom vi inte kan lagra räkningar medan vi kan använda unordered_map.
unordered_map vs karta
| Oordnad_karta | Karta |
|---|---|
| Nyckeln unordered_map kan lagras i valfri ordning. | Kartan är en ordnad sekvens av unika nycklar |
| Unordered_Map implementerar en obalanserad trädstruktur på grund av vilken det inte är möjligt att upprätthålla ordning mellan elementen | Map implementerar en balanserad trädstruktur varför det är möjligt att upprätthålla ordning mellan elementen (genom specifik trädpassering) |
| Tidskomplexiteten för unordered_map-operationer är O(1) i genomsnitt. | Tidskomplexiteten för kartoperationer är O(log n) |
Metoder på unordered_map
Många funktioner finns tillgängliga som fungerar på unordered_map. De mest användbara av dem är:
- operator = operator [] tom storlek för kapacitetens början och slut för iteratorn. hitta och räkna för uppslag. infoga och radera för ändring.
Tabellen nedan visar den fullständiga listan över metoderna för en oordnad_karta:
| Metoder/funktioner | Beskrivning |
|---|---|
| på() | Denna funktion i C++ unordered_map returnerar referensen till värdet med elementet som nyckel k |
| Börja() | Returnerar en iterator som pekar på det första elementet i behållaren i unordered_map-behållaren |
| slutet() | Returnerar en iterator som pekar på positionen förbi det sista elementet i behållaren i unordered_map-behållaren |
| hink() | Returnerar hinknumret där elementet med nyckeln k finns på kartan |
| bucket_count | Bucket_count används för att räkna det totala antalet. av hinkar i unordered_map. Ingen parameter krävs för att gå in i denna funktion |
| hinkstorlek | Returnerar antalet element i varje bucket av unordered_map |
| räkna() | Räkna antalet element som finns i en unordered_map med en given nyckel |
| lika_intervall | Returnera gränserna för ett intervall som inkluderar alla element i behållaren med en nyckel som jämförs med k |
| hitta() | Returnerar iterator till elementet |
| tömma() | Kontrollerar om behållaren är tom i unordered_map-behållaren |
| radera() | Radera element i behållaren i unordered_map-behållaren |
C++11-biblioteket tillhandahåller också funktioner för att se internt använda bucket count, hinkstorlek och även använda hashfunktioner och olika hashpolicyer men de är mindre användbara i verkliga applikationer. Vi kan iterera över alla element i unordered_map med Iterator.
C++
mvc i fjäderram
// 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 = { //infogar element direkt i kartan {'One', 1}, {'Two', 2}, {'Three', 3} }; // infoga värden genom att använda [] operator umap['PI'] = 3.14; umap['root2'] = 1,414; umap['root3'] = 1,732; umap['log10'] = 2.302; umap['loge'] = 1.0; // infogar värde genom att infoga funktionen umap.insert(make_pair('e', 2.718)); strängnyckel = 'PI'; // Om nyckeln inte hittas i kartiteratorn // to end returneras om (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->först lagrar nyckeldelen och // itr->second lagrar värdedelen cout ' '<< itr->andra<< endl; } }> |
>
>Produktion
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>
Hitta frekvenser för enskilda ord
Givet en rad ord är uppgiften att hitta frekvenserna för de enskilda orden:
Inmatning: str = nördar för nördar nördar frågesport öva qa för;
Produktion: Frekvenser för enskilda ord är
(övning, 1)
(för, 2)
(qa, 1)
(quiz, 1)
(nördar, 3)
Nedan är C++-programmet för att implementera ovanstående tillvägagångssätt:
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; // bryta indata till ord med // string stream // Används för att bryta ord stringstream ss(str); // För att lagra enskilda ord strängord; while (ss>> word) wordFreq[ord]++; // itererar nu över word, freq-par // och skriver ut dem i formatet unordered_mapint>:: iterator p; för (p = wordFreq.begin(); p != wordFreq.end(); p++) cout<< '(' ', ' << p->andra<< ')
'; } // Driver code int main() { string str = 'geeks for geeks geeks quiz ' 'practice qa for'; printFrequencies(str); return 0; }> |
>
>Produktion
(practice, 1) (for, 2) (qa, 1) (quiz, 1) (geeks, 3)>
Senaste artiklarna om unordered_map