Predpoklad: std::map , std::unordered_map
Čo sa týka efektivity, medzi mapami a neusporiadanými mapami je obrovský rozdiel.
Musíme poznať vnútorné fungovanie oboch, aby sme sa rozhodli, ktorý z nich použijeme.
Rozdiel :
| 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) ->Priemer | | O(n) -> Čas vloženia najhoršieho prípadu | log(n) + Vyrovnanie | Rovnaké ako vyhľadávanie Čas vymazania | log(n) + Vyrovnanie | Rovnaké ako vyhľadávanie>
Keď použijete std::map
- Potrebujete objednané údaje.
- Údaje by ste museli vytlačiť/sprístupniť (v zoradenom poradí).
- Potrebujete predchodcu/nástupcu prvkov.
- Pozrite si výhody BST oproti Hash Tabl e pre viac prípadov.
CPP
modifikačné klávesy
reťazec poľa v c
// CPP program to demonstrate use of std::map> #include> int> main()> {> >// Ordered map> >std::map<>int>,>int>>objednávka;> >// 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 << ' : ' '
'; } }> |
>
>Výkon
1 : 1 3 : 500 5 : 10 20 : 100>
Keď použijete std::unordered_map
- Niektoré údaje (Príklad – reťazce) je potrebné dodržať a nie je potrebné žiadne objednávanie.
- Potrebujete prístup k jednému prvku, t. j. žiadne prechádzanie.
CPP
registrovať pamäť
// CPP program to demonstrate use of> // std::unordered_map> #include> int> main()> {> >// Unordered map> >std::unordered_map<>int>,>int>>objednávka;> >// 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 << ' : ' '
'; } }> |
>
dĺžka poľa v jazyku Java
>Výkon
1 : 1 20 : 100 3 : 500 5 : 10>
Pozrime sa na rozdiely v tabuľkovej forme -:
| mapa | unordered_map | |
| 1. | mapa je definovaná v #include hlavičkovom súbore | unordered_map je definovaná v #include hlavičkovom súbore |
| 2. | Realizuje sa tým červeno-čierny strom . | Je implementovaný pomocou hash tabuľky. |
| 3. | Je to pomalé. | Je to rýchle. |
| 4. | Časová zložitosť pre operácie je O (log N) | Časová zložitosť operácií je O(1) |
| 5. | mapa sa používa na ukladanie prvkov ako párov kľúč, hodnota v poradí zoradenom podľa kľúča. | unordered_map sa používa na ukladanie prvkov ako párov kľúč, hodnota v nezoradenom poradí. |