mappa_non ordinata è un contenitore associato che memorizza elementi formati dalla combinazione di un valore chiave e un valore mappato. Il valore della chiave viene utilizzato per identificare in modo univoco l'elemento e il valore mappato è il contenuto associato alla chiave. Sia la chiave che il valore possono essere di qualsiasi tipo, predefinito o definito dall'utente. In termini semplici, un mappa_non ordinata è come una struttura dati di tipo dizionario che memorizza gli elementi in sé. Contiene coppie successive (chiave, valore), che consentono il recupero rapido di un singolo elemento in base alla sua chiave univoca.
Shilpa Shetty età
Internamente unordered_map viene implementato utilizzando Hash Table, la chiave fornita per mappare viene hash negli indici di una tabella hash, motivo per cui le prestazioni della struttura dati dipendono molto dalla funzione hash ma, in media, il costo di cercare, inserire ed eliminare dalla tabella hash è O(1).
Nota: Nel peggiore dei casi, la sua complessità temporale può andare da O(1) a O(n), soprattutto per grandi numeri primi. In questa situazione, è altamente consigliabile utilizzare invece una mappa per evitare di ricevere un errore TLE (Time Limit Exceeded).
Sintassi:
sintassi unordered_map
Di seguito è riportato il programma C++ per dimostrare una mappa non ordinata:
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>mappa; // inserendo valori utilizzando l'operatore [] umap['techcodeview.com'] = 10; umap['Pratica'] = 20; umap['Contribuisci'] = 30; // Attraversamento di una mappa non ordinata per (auto x: umap) cout<< x.first << ' ' << x.second << endl; }> |
>
>Produzione
Contribute 30 Practice 20 techcodeview.com 10>
Risultato non ordinato_map
Spiegazione: La cosa specifica che questo output giustifica è che il valore del risultato di unordered_map viene prodotto in modo casuale chiave-valore mentre la mappa visualizza valore e chiave in modo ordinato.
unordered_map vs unordered_set
| Mappa_non ordinata | Insieme_non ordinato |
|---|---|
| Unordered_map contiene elementi solo sotto forma di coppie (chiave-valore). | Unordered_set non contiene necessariamente elementi sotto forma di coppie chiave-valore, queste vengono utilizzate principalmente per vedere la presenza/assenza di un set. |
| Operatore ' []' per estrarre il valore corrispondente di una chiave presente nella mappa. | La ricerca di un elemento viene effettuata utilizzando a Trovare () funzione. Quindi non è necessario un operatore[]. |
Nota: Consideriamo ad esempio il problema del conteggio delle frequenze delle singole parole. Non possiamo utilizzare unordered_set (o set) poiché non possiamo memorizzare i conteggi mentre possiamo utilizzare unordered_map.
unordered_map vs mappa
| Mappa_non ordinata | Carta geografica |
|---|---|
| La chiave unordered_map può essere memorizzata in qualsiasi ordine. | La mappa è una sequenza ordinata di chiavi univoche |
| Unordered_Map implementa una struttura ad albero sbilanciata per cui non è possibile mantenere l'ordine tra gli elementi | La mappa implementa una struttura ad albero equilibrata, motivo per cui è possibile mantenere l'ordine tra gli elementi (attraverso l'attraversamento specifico dell'albero) |
| La complessità temporale delle operazioni unordered_map è in media O(1). | La complessità temporale delle operazioni sulla mappa è O(log n) |
Metodi su unordered_map
Sono disponibili molte funzioni che funzionano su unordered_map. I più utili sono:
- operatore = operatore [] dimensione vuota per la capacità di inizio e fine per l'iteratore. trovare e contare per la ricerca. inserire e cancellare per la modifica.
La tabella seguente mostra l'elenco completo dei metodi di un unordered_map:
| Metodi/Funzioni | Descrizione |
|---|---|
| A() | Questa funzione in C++ unordered_map restituisce il riferimento al valore con l'elemento come chiave k |
| inizio() | Restituisce un iteratore che punta al primo elemento nel contenitore nel contenitore unordered_map |
| FINE() | Restituisce un iteratore che punta alla posizione dopo l'ultimo elemento nel contenitore nel contenitore unordered_map |
| secchio() | Restituisce il numero del bucket in cui si trova l'elemento con la chiave k nella mappa |
| bucket_count | Bucket_count viene utilizzato per contare il numero totale. di bucket in unordered_map. Non è richiesto alcun parametro da passare a questa funzione |
| secchio_dimensione | Restituisce il numero di elementi in ciascun bucket di unordered_map |
| contare() | Conta il numero di elementi presenti in una unordered_map con una determinata chiave |
| intervallo_uguale | Restituisce i limiti di un intervallo che include tutti gli elementi nel contenitore con una chiave che risulta uguale a k |
| Trovare() | Restituisce l'iteratore all'elemento |
| vuoto() | Controlla se il contenitore è vuoto nel contenitore unordered_map |
| cancellare() | Cancella gli elementi nel contenitore nel contenitore unordered_map |
La libreria C++11 fornisce anche funzioni per visualizzare il conteggio dei bucket utilizzati internamente, la dimensione dei bucket, nonché la funzione hash utilizzata e varie policy hash, ma sono meno utili nelle applicazioni reali. Possiamo scorrere tutti gli elementi di unordered_map utilizzando 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 = { //inserimento elemento direttamente nella mappa {'Uno', 1}, {'Due', 2}, {'Tre', 3} }; // inserendo valori utilizzando l'operatore [] umap['PI'] = 3.14; umap['root2'] = 1.414; umap['root3'] = 1.732; umap['log10'] = 2.302; umap['loge'] = 1.0; // inserimento del valore tramite la funzione di inserimento umap.insert(make_pair('e', 2.718)); chiave stringa = 'PI'; // Se la chiave non viene trovata nell'iteratore della mappa // viene restituito to end 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>::iteratore itr; cout<< '
All Elements :
'; for (itr = umap.begin(); itr != umap.end(); itr++) { // itr works as a pointer to // pair type // itr->per prima cosa memorizza la parte chiave e // itr->secondo memorizza la parte valore cout ' '<< itr->secondo<< endl; } }> |
>
>Produzione
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>
Trova le frequenze delle singole parole
Data una stringa di parole, il compito è trovare le frequenze delle singole parole:
Ingresso: str = geek per geek pratica del quiz geek qa per;
Produzione: Le frequenze delle singole parole sono
(pratica, 1)
(per, 2)
(qa, 1)
(quiz, 1)
(geek, 3)
Di seguito è riportato il programma C++ per implementare l'approccio di cui sopra:
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>parolaFreq; // suddivide l'input in parole utilizzando // string stream // Utilizzato per suddividere le parole stringstream ss(str); // Per memorizzare singole parole string word; while (ss>> parola) parolaFreq[parola]++; // ora itera su word, freq coppia // e li stampa nel formato unordered_mapint>:: iterator p; for (p = parolaFreq.begin(); p != parolaFreq.end(); p++) cout<< '(' ', ' << p->secondo<< ')
'; } // Driver code int main() { string str = 'geeks for geeks geeks quiz ' 'practice qa for'; printFrequencies(str); return 0; }> |
>
funzione freccia dattiloscritta
>Produzione
(practice, 1) (for, 2) (qa, 1) (quiz, 1) (geeks, 3)>
Articoli recenti su unordered_map