ongeordende_kaart is een bijbehorende container waarin elementen worden opgeslagen die worden gevormd door de combinatie van een sleutelwaarde en een toegewezen waarde. De sleutelwaarde wordt gebruikt om het element uniek te identificeren en de toegewezen waarde is de inhoud die aan de sleutel is gekoppeld. Zowel de sleutel als de waarde kunnen van elk vooraf gedefinieerd of door de gebruiker gedefinieerd type zijn. In eenvoudige bewoordingen: een ongeordende_kaart is als een datastructuur van het woordenboektype die elementen in zichzelf opslaat. Het bevat opeenvolgende paren (sleutel, waarde), waardoor een individueel element snel kan worden opgehaald op basis van zijn unieke sleutel.
recursie in Java
Intern unordered_map wordt geïmplementeerd met behulp van Hash Table, de sleutel die wordt verstrekt om in kaart te brengen wordt gehasht in indices van een hashtabel. Daarom zijn de prestaties van de datastructuur sterk afhankelijk van de hashfunctie, maar gemiddeld zijn de kosten van zoeken, invoegen en verwijderen uit de hashtabel is O(1).
Opmerking: In het ergste geval kan de tijdscomplexiteit gaan van O(1) naar O(n), vooral voor grote priemgetallen. In deze situatie is het zeer raadzaam om in plaats daarvan een kaart te gebruiken om te voorkomen dat u een TLE-fout (Time Limit Exceeded) krijgt.
Syntaxis:
unordered_map-syntaxis
Hieronder staat het C++-programma om een ongeordende kaart te demonstreren:
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; // waarden invoegen met behulp van [] operator umap['techcodeview.com'] = 10; umap['Oefenen'] = 20; umap['Bijdragen'] = 30; // Een ongeordende kaart doorkruisen voor (auto x: umap) cout<< x.first << ' ' << x.second << endl; }> |
>
>Uitvoer
Contribute 30 Practice 20 techcodeview.com 10>
unordered_map Uitvoer
Uitleg: Het specifieke dat deze uitvoer rechtvaardigt, is dat de waarde van de uitkomst van unordered_map op een willekeurige sleutel-naar-waarde-manier wordt geproduceerd, terwijl de kaart waarde en sleutel op een geordende manier weergeeft.
ongeordende_kaart versus ongeordende_set
| Ongeordende_kaart | Ongeordende_set |
|---|---|
| Unordered_map bevat alleen elementen in de vorm van (sleutel-waarde)paren. | Unordered_set bevat niet noodzakelijkerwijs elementen in de vorm van sleutel-waardeparen; deze worden voornamelijk gebruikt om de aan-/afwezigheid van een set te zien. |
| Exploitant ‘ []' om de corresponderende waarde te extraheren van een sleutel die aanwezig is op de kaart. | Het zoeken naar een element gebeurt met behulp van a vinden () functie. Er is dus geen operator[] nodig. |
Opmerking: Denk bijvoorbeeld eens aan het probleem van het tellen van de frequenties van individuele woorden. We kunnen unordered_set (of set) niet gebruiken omdat we geen tellingen kunnen opslaan, terwijl we unordered_map wel kunnen gebruiken.
ongeordende_kaart versus kaart
| Ongeordende_kaart | Kaart |
|---|---|
| De unordered_map-sleutel kan in elke volgorde worden opgeslagen. | De kaart is een geordende reeks unieke sleutels |
| Unordered_Map implementeert een ongebalanceerde boomstructuur waardoor het niet mogelijk is om de volgorde tussen de elementen te handhaven | Kaart implementeert een gebalanceerde boomstructuur, waardoor het mogelijk is om de volgorde tussen de elementen te behouden (door specifieke boombewegingen) |
| De tijdscomplexiteit van unordered_map-bewerkingen is gemiddeld O(1). | De tijdscomplexiteit van kaartbewerkingen is O(log n) |
Methoden op unordered_map
Er zijn veel functies beschikbaar die werken op unordered_map. De nuttigste daarvan zijn:
- operator = operator [] lege grootte voor capaciteitsbegin en -einde voor de iterator. zoeken en tellen voor opzoeken. invoegen en wissen voor wijziging.
De onderstaande tabel toont de volledige lijst met methoden van een unordered_map:
| Methoden/Functies | Beschrijving |
|---|---|
| bij() | Deze functie in C++ unordered_map retourneert de verwijzing naar de waarde met het element als sleutel k |
| beginnen() | Retourneert een iterator die verwijst naar het eerste element in de container in de container unordered_map |
| einde() | Retourneert een iterator die verwijst naar de positie voorbij het laatste element in de container in de container unordered_map |
| emmer() | Geeft het bucketnummer terug waar het element met de sleutel k zich op de kaart bevindt |
| bucket_count | Bucket_count wordt gebruikt om het totale aantal te tellen. aantal emmers in de unordered_map. Er is geen parameter vereist om deze functie door te geven |
| emmer_grootte | Retourneert het aantal elementen in elke bucket van de unordered_map |
| graaf() | Tel het aantal elementen dat aanwezig is in een unordered_map met een bepaalde sleutel |
| gelijk_bereik | Retourneert de grenzen van een bereik dat alle elementen in de container omvat, met een sleutel die gelijk is aan k |
| vinden() | Retourneert iterator naar het element |
| leeg() | Controleert of de container leeg is in de unordered_map container |
| wissen() | Wis elementen in de container in de unordered_map container |
De C++11-bibliotheek biedt ook functies om het aantal intern gebruikte buckets, de bucketgrootte, en ook de gebruikte hash-functie en verschillende hash-beleidsregels te bekijken, maar deze zijn minder nuttig in echte toepassingen. We kunnen alle elementen van unordered_map herhalen met behulp van 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 = { //element rechtstreeks in de kaart invoegen {'Eén', 1}, {'Twee', 2}, {'Drie', 3} }; // waarden invoegen met behulp van [] operator umap['PI'] = 3.14; umap['root2'] = 1.414; umap['root3'] = 1.732; umap['log10'] = 2.302; umap['loge'] = 1,0; // waarde invoegen door functie umap.insert(make_pair('e', 2.718)); stringsleutel = 'PI'; // Als de sleutel niet wordt gevonden in de kaartiterator // wordt het einde geretourneerd als (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; uit<< '
All Elements :
'; for (itr = umap.begin(); itr != umap.end(); itr++) { // itr works as a pointer to // pair type // itr->slaat eerst het sleutelgedeelte op en // itr->tweede slaat het waardegedeelte op cout ' '<< itr->seconde<< endl; } }> |
>
>Uitvoer
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>
Vind frequenties van individuele woorden
Gegeven een reeks woorden, is het de taak om de frequenties van de afzonderlijke woorden te vinden:
Invoer: str = nerds voor nerds nerds quiz oefenen qa voor;
Uitgang: Frequenties van individuele woorden zijn
(oefenen, 1)
(voor 2)
(qa, 1)
(quiz, 1)
(nerds, 3)
Hieronder vindt u het C++-programma om de bovenstaande aanpak te implementeren:
C++
scripts uitvoeren onder Linux
// 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>woordFreq; // invoer in woorden opsplitsen met // string stream // Gebruikt voor het opsplitsen van woorden stringstream ss(str); // Om individuele woorden op te slaan; while (ss>> woord) wordFreq[woord]++; // nu itererend over word, freq pair // en ze afdrukken in formaat unordered_mapint>:: iterator p; for (p = wordFreq.begin(); p != wordFreq.end(); p++) cout<< '(' ', ' << p->seconde<< ')
'; } // Driver code int main() { string str = 'geeks for geeks geeks quiz ' 'practice qa for'; printFrequencies(str); return 0; }> |
>
>Uitvoer
(practice, 1) (for, 2) (qa, 1) (quiz, 1) (geeks, 3)>
Recente artikelen over unordered_map