Condiție prealabilă: std::hartă , std::unordered_map
Când vine vorba de eficiență, există o diferență uriașă între hărți și hărți neordonate.
Trebuie să cunoaștem funcționarea internă a ambelor pentru a decide care dintre ele va fi folosit.
Diferență :
| map | unordered_map --------------------------------------------------------- Ordering | increasing order | no ordering | of keys(by default) | Implementation | Self balancing BST | Hash Table | like Red-Black Tree | search time | log(n) | O(1) ->Medie | | O(n) -> Timp de inserare în cel mai rău caz | log(n) + Reechilibrare | La fel ca și căutarea Timp de ștergere | log(n) + Reechilibrare | La fel ca search>
Folosiți std::map când
- Ai nevoie de date comandate.
- Ar trebui să imprimați/accesați datele (în ordinea sortată).
- Ai nevoie de predecesor/succesor al elementelor.
- Vedeți avantajele BST față de Hash Tabl e pentru mai multe cazuri.
CPP
list nodul în java
// CPP program to demonstrate use of std::map> #include> int> main()> {> >// Ordered map> >std::map<>int>,>int>>comanda;> >// Mapping values to keys> >order[5] = 10;> >order[3] = 500;> >order[20] = 100;> >order[1] = 1;> >// Iterating the map and> >// printing ordered values> >for> (>auto> i = order.begin(); i> >!= order.end(); i++) {> >std::cout << ' : ' '
'; } }> |
liste în java
>
>Ieșire
verificați nul în java
1 : 1 3 : 500 5 : 10 20 : 100>
Folosiți std::unordered_map când
- Trebuie să țineți cont de unele date (Exemplu – șiruri de caractere) și nu este necesară nicio ordine.
- Aveți nevoie de acces la un singur element, adică fără traversare.
CPP
funcții în c
// CPP program to demonstrate use of> // std::unordered_map> #include> int> main()> {> >// Unordered map> >std::unordered_map<>int>,>int>>comanda;> >// Mapping values to keys> >order[5] = 10;> >order[3] = 500;> >order[20] = 100;> >order[1] = 1;> >// Iterating the map and> >// printing unordered values> >for> (>auto> i = order.begin();> >i != order.end(); i++)> >{> >std::cout << ' : ' '
'; } }> |
>
>Ieșire
1 : 1 20 : 100 3 : 500 5 : 10>
Să vedem diferențele într-o formă tabelară -:
| Hartă | hartă_neordonată | |
| 1. | harta este definită în fișierul antet #include | unordered_map este definită în fișierul antet #include |
| 2. | Este implementat de copac roșu-negru . | Este implementat folosind tabelul hash. |
| 3. | Este lent. | E rapid. |
| 4. | Complexitatea timpului pentru operații este O(log N) | Complexitatea timpului pentru operații este O(1) |
| 5. | harta este folosită pentru a stoca elemente ca perechi cheie, valoare în ordine sortate după cheie. | unordered_map este folosit pentru a stoca elemente ca perechi cheie, valoare în ordine nesortată. |