<\/p>\n\n\n\n
- Cum folosim Map?<\/li><\/ul>\n\n\n\n
Primul pas este includerea libr\u0103riei <map> \u00een programul nostru:<\/p>\n\n\n\n
\n#include <map><\/pre>\n<\/div><\/div>\n\n\n\n
Al doilea pas este ini\u021bializarea unui map:<\/p>\n\n\n\n
map<key_data_type, value_data_type> m;\n<\/pre>\n\n\n\n
Pentru a vedea concret cum func\u021bioneaz\u0103 structura de date Map, voi lua ca exemplu problema #2268<\/a> de pe pbinfo.ro. \u00cen rezolvarea acesteia, vom folosi un Map. Numele elevilor vor reprezenta c\u00e2te un key value, iar frecven\u021ba fiec\u0103rui nume un mapped value.<\/p>\n\n\n\n
<\/p>\n\n\n\n
#include <iostream>\n#include <map>\n\nusing namespace std;\n\nint n;\nstring nume; \/\/ numele care vor fi citite\nmap <string, int> M; \/\/ map av\u00e2nd key_value<\/strong> de tipul string(nume)<\/strong>, \u0219i mapped_value<\/strong> de tipul int(frecven\u021b\u0103)<\/strong>\nmap <string, int> :: iterator it; \/\/ cu ajutorul lui, vom itera prin map\npair <string, int> elev; \/\/ p\u0103strez elevul cu frecven\u021ba maxim\u0103 \u0219i primul \u00een ordine alfabetic\u0103. elev.first va reprezenta numele elevului, iar elev.second frecven\u021ba acestuia\n\nint main(){\n\n cin >> n;\n for(int i = 1; i <= n; i++){\n \n cin >> nume; \/\/ citesc n<\/strong> nume\n M[nume]++; \/\/ m\u0103resc frecven\u021ba numelui\n \n }\n\n for(it = M.begin(); it != M.end(); it++){\n\n\/\/ aici, it -> first va reprezenta fiecare nume din map, iar it -> second frecven\u021ba acestuia\n \n if(elev.second < it -> second){ \n\/\/ dac\u0103 \u00eent\u0103lnesc un nume cu frecven\u021b\u0103 mai mare, \u00eel p\u0103strez\n \n elev.first = it -> first;\n elev.second = it -> second;\n \n }else if(elev.second == it -> second && elev.first > it -> first){\n \n\/\/ dac\u0103 \u00eent\u0103lnesc un nume cu aceea\u0219i frecven\u021b\u0103, dar care este mai mic lexicografic(adic\u0103, este plasat \u00eenaintea lui elev.first \u00een ordinea alfabetic\u0103) dec\u00e2t ceea ce am deja \u00een variabila elev<\/strong>, \u00eel p\u0103strez \n\n elev.first = it -> first;\n elev.second = it -> second;\n \n }\n }\n\n cout << elev.first << \" \" << elev.second; \/\/ afi\u0219ez elevul cu frecven\u021ba maxim\u0103 \u0219i care este primul \u00een ordine alfabetic\u0103\n\n return 0;\n}<\/pre>\n\n\n\n\u00cen mod asem\u0103n\u0103tor, se rezolv\u0103 \u0219i problema #2217<\/a>. <\/p>\n\n\n\n
\u00centruc\u00e2t mai sus am specificat structura de date unordered_map<\/strong>, v\u0103 voi prezenta diferen\u021bele dintre aceste 2 structuri de date \u0219i c\u00e2nd trebuie s\u0103 le folosim.<\/p>\n\n\n\n
Vom folosi Map atunci c\u00e2nd avem nevoie de date\/informa\u021bii \u00een ordine<\/strong>! Altfel, dac\u0103 ordinea elementelor nu este necesar\u0103, este mai bine s\u0103 folosim unordered_map<\/strong>!<\/p>\n\n\n\n
<\/p>\n\n\n\n
Pentru a folosi unordered_map<\/strong>, avem nevoie de libr\u0103ria <unordered_map> :<\/p>\n\n\n\n
#include <unordered_map><\/pre>\n\n\n\n
Diferen\u021bele majore dintre cele 2 structuri de date sunt:<\/p>\n\n\n\n
- Ordonarea: Map ne asigur\u0103 c\u0103 elementele vor fi mereu \u00een ordine, \u00een schimb, Unordered Map nu ne permite acest lucru (de aici \u0219i numele)<\/li>
- Eficien\u021ba<\/li><\/ol>\n\n\n\n
Map:<\/strong><\/p>\n\n\n\n
- inserare: log(n) + rebalance<\/li>
- \u0219tergere: log(n) + rebalance<\/li>
- c\u0103utare: log(n)<\/li>
- implementare: Self Balancing BST (de exemplu: Red-Black Tree<\/a>)<\/li><\/ul>\n\n\n\n
<\/p>\n\n\n\n
Unordered Map:<\/strong><\/p>\n\n\n\n
- inserare: O(1) \u00een medie sau O(n), \u00een cel mai r\u0103u caz<\/li>
- \u0219tergere: O(1) \u00een medie sau O(n), \u00een cel mai r\u0103u caz<\/li>
- c\u0103utare: O(1) sau O(n)<\/li>
- implementare: Hash Table<\/a><\/li><\/ul>\n\n\n\n
<\/p>\n\n\n\n
![\"\"](\"https:\/\/solinfo.ro\/blog\/wp-content\/uploads\/2021\/12\/pirnog_theodor-1-2-300x300.png\")