unordered_map je pridružený kontajner, ktorý ukladá prvky tvorené kombináciou hodnoty kľúča a namapovanej hodnoty. Hodnota kľúča sa používa na jedinečnú identifikáciu prvku a namapovaná hodnota je obsah spojený s kľúčom. Kľúč aj hodnota môžu byť ľubovoľného typu preddefinovaného alebo definovaného používateľom. Zjednodušene povedané, an unordered_map je ako dátová štruktúra typu slovníka, ktorá v sebe ukladá prvky. Obsahuje po sebe nasledujúce dvojice (kľúč, hodnota), čo umožňuje rýchle vyhľadanie jednotlivého prvku na základe jeho jedinečného kľúča.
1 z 1000
Interne unordered_map je implementovaná pomocou Hash Table , kľúč poskytnutý na mapovanie je hašovaný do indexov hašovacej tabuľky, čo je dôvod, prečo výkon dátovej štruktúry veľa závisí od hašovacej funkcie, ale v priemere sú náklady na hľadať, vkladať a mazať z hašovacej tabuľky je O(1).
Poznámka: V najhoršom prípade sa jeho časová zložitosť môže pohybovať od O(1) po O(n), najmä pre veľké prvočísla. V tejto situácii je veľmi vhodné použiť namiesto toho mapu, aby ste sa vyhli chybe TLE (Prekročený časový limit).
Syntax:
unordered_map syntax
Nižšie je uvedený program C++ na demonštráciu neusporiadanej mapy:
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; // vkladanie hodnôt pomocou operátora [] umap['techcodeview.com'] = 10; umap['Cvičenie'] = 20; umap['Prispejte'] = 30; // Prechádzanie neusporiadanej mapy pre (auto x : umap) cout<< x.first << ' ' << x.second << endl; }> |
>
>Výkon
Contribute 30 Practice 20 techcodeview.com 10>
unordered_map výstup
Vysvetlenie: Špecifická vec, ktorú tento výstup ospravedlňuje, je, že hodnota výsledku unordered_map sa vytvára náhodným spôsobom kľúč k hodnote, zatiaľ čo mapa zobrazuje hodnotu a kľúč usporiadaným spôsobom.
unordered_map vs unordered_set
| Unordered_map | Unordered_set |
|---|---|
| Unordered_map obsahuje prvky iba vo forme párov (kľúč-hodnota). | Unordered_set nemusí nevyhnutne obsahovať prvky vo forme párov kľúč-hodnota, tieto sa používajú hlavne na zobrazenie prítomnosti/neprítomnosti množiny. |
| Operátor []' extrahovať zodpovedajúcu hodnotu kľúča, ktorý sa nachádza na mape. | Hľadanie prvku sa vykonáva pomocou a Nájsť () funkcia. Takže nie je potrebný operátor[]. |
Poznámka: Zamyslime sa napríklad nad problémom počítania frekvencií jednotlivých slov. Nemôžeme použiť unordered_set (alebo set), pretože nemôžeme ukladať počty, zatiaľ čo môžeme použiť unordered_map.
unordered_map vs mapa
| Unordered_map | Mapa |
|---|---|
| Kľúč unordered_map môže byť uložený v ľubovoľnom poradí. | Mapa je usporiadaná postupnosť jedinečných kľúčov |
| Unordered_Map implementuje nevyváženú stromovú štruktúru, kvôli ktorej nie je možné udržiavať poriadok medzi prvkami | Mapa implementuje vyváženú stromovú štruktúru, vďaka čomu je možné udržiavať poriadok medzi prvkami (konkrétnym prechodom cez strom) |
| Časová zložitosť operácií unordered_map je v priemere O(1). | Časová zložitosť mapových operácií je O(log n) |
Metódy na unordered_map
K dispozícii je veľa funkcií, ktoré fungujú na unordered_map. Najužitočnejšie z nich sú:
- operator = operator [] prázdna veľkosť pre začiatok a koniec kapacity iterátora. nájsť a spočítať na vyhľadanie. vložiť a vymazať na úpravu.
Nasledujúca tabuľka zobrazuje úplný zoznam metód unordered_map:
| Metódy/Funkcie | Popis |
|---|---|
| v () | Táto funkcia v C++ unordered_map vracia odkaz na hodnotu s prvkom ako kľúč k |
| začať() | Vráti iterátor ukazujúci na prvý prvok v kontajneri v kontajneri unordered_map |
| koniec() | Vráti iterátor ukazujúci na pozíciu za posledným prvkom v kontajneri v kontajneri unordered_map |
| vedro() | Vráti číslo segmentu, kde sa na mape nachádza prvok s kľúčom k |
| bucket_count | Bucket_count sa používa na počítanie celkového počtu. z vedier v unordered_map. Na prechod do tejto funkcie nie je potrebný žiadny parameter |
| bucket_size | Vráti počet prvkov v každom segmente unordered_map |
| počítať () | Spočítajte počet prvkov prítomných v unordered_map s daným kľúčom |
| rovnaký_rozsah | Vráti hranice rozsahu, ktorý zahŕňa všetky prvky v kontajneri, s kľúčom, ktorý sa porovnáva rovným k |
| Nájsť() | Vráti iterátor prvku |
| prázdne () | Skontroluje, či je kontajner prázdny v kontajneri unordered_map |
| vymazať() | Vymažte prvky v kontajneri v kontajneri unordered_map |
Knižnica C++11 tiež poskytuje funkcie na zobrazenie počtu interne používaných segmentov, veľkosti segmentov a tiež použitej hašovacej funkcie a rôznych hašovacích politík, ale v reálnych aplikáciách sú menej užitočné. Pomocou Iterátora môžeme iterovať cez všetky prvky unordered_map.
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 = { //vloženie prvku priamo do mapy {'Jeden', 1}, {'Dva', 2}, {'Tri', 3} }; // vkladanie hodnôt pomocou operátora [] umap['PI'] = 3.14; umap['root2'] = 1,414; umap['root3'] = 1,732; umap['log10'] = 2,302; umap['loge'] = 1,0; // vloženie hodnoty pomocou funkcie vloženia umap.insert(make_pair('e', 2.718)); kľúč reťazca = 'PI'; // Ak sa kľúč nenájde v iterátore mapy // do konca sa vráti 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>::iterator itr; cout<< '
All Elements :
'; for (itr = umap.begin(); itr != umap.end(); itr++) { // itr works as a pointer to // pair type // itr->najprv uloží kľúčovú časť a // itr->druhý uloží hodnotu časť cout ' '<< itr->druhý<< endl; } }> |
>
>Výkon
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>
Nájdite frekvencie jednotlivých slov
Pri danom reťazci slov je úlohou nájsť frekvenciu jednotlivých slov:
Vstup: str = geeks for geeks geeks quiz practice qa for;
Výkon: Frekvencie jednotlivých slov sú
(cvičenie, 1)
(pre, 2)
(qa, 1)
(kvíz, 1)
(geekovia, 3)
Nižšie je uvedený program C++ na implementáciu vyššie uvedeného prístupu:
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; // rozdelenie vstupu do slova pomocou // string stream // Používa sa na rozdelenie slov stringstream ss(str); // Na uloženie jednotlivých slov string word; while (ss>> slovo) wordFreq[slovo]++; // teraz iterujeme cez word, freq pair // a tlačíme ich vo formáte unordered_mapint>:: iterator p; for (p = wordFreq.begin(); p != wordFreq.end(); p++) cout<< '(' ', ' << p->druhý<< ')
'; } // Driver code int main() { string str = 'geeks for geeks geeks quiz ' 'practice qa for'; printFrequencies(str); return 0; }> |
>
>
shweta tiwariVýkon
(practice, 1) (for, 2) (qa, 1) (quiz, 1) (geeks, 3)>
Najnovšie články na unordered_map