map, multimap, unordered-map lý thuyết trong c++

map, multimap, unordered-map lý thuyết cơ bản trong c++

1. 28TECH
Become A Better Developer

4

Leddy
WR

MAP, MULTIMAP,
UNORDERED_MAP

LU

4

4

1 28TECH.COM.VN Ein

2. 28TECH

Become A Bete Developer 1. MAP:

Map là container giúp luu cdc phan ttr theo cap key, value (khóa - gia tri). MÓi
gia tri cúa key sé anh xa sang möt value tuong ting. So véi Set thi Map tham
chi con manh mé va giái quyét duoc nhiéu van dé hon.

Cac key trong map lá nhüng Các cap phan tütrongmap Môi phan tú trong map thuc
gia tri riéng biét, khöng có 2 duoc sáp xép theo thú ty Chât lá mot pair, vói first luu
key náo có giá tri gióng nhau, táng dán cúa key. key vá second luu value.
value thi có thé trüng nhau.

28TECH.COM.VN Ein

3. 28TECH

Become A Better Developer

<key_data_type, value_data_type> map_name;

Cac bai toán lien quan tdi tan suát

cúa các phan tu.

Cac bai toán cán tim kiém, thém, xóa
mót cach nhanh chong.

Dung map thay cho các bai toän su dung
mang dánh dau khi di liêu khóng dep.

4. 28TECH nas ar im
Become A Better Developer MOT SO HAM TRONG MAP

<bits/stdc++.h>

Them möt phan tú vao trong map: N
« Dung ham insert mp.insert({1,
2 2 2 mp.insert({2,
« Dung ct phäp mp.insert({1,
néu key chua tón tai trong map, me mee
hoác sé thay dôi value néu key ”

SERIE D O mp = {(1,2), (2,5), (3,10)}

28TECH.COM.UN 5

5. 28TECH ua m re
Become A Better Developer MOT SO HAM TRONG MAP

int main(){
map<int, int> mp;
mp.insert({1, 2}); //Thém cap (1, 2)
> Pores ae A mp.insert({2, 4}); //Thém cap (2, 4)
Ham size: tra vé sö lugng phan mp.insert({1, 3}); //Thém cap (1, 3)
trong map. ee //nhung khóng thém dugc
mp[3] = 10; // thém cap (3, 10)
mp[2] = 5; //Thay dôi cap (2, 4)
//thanh (2, 5)
cout << mp.size() << endl;

OUTPUT: 3

y

28TECH.COMN Sc}

6. 28TECH

Become A Better Developer

kiém tra map róng, néu
rong tra vé true, nguroc lai tra vé false.

xóa moi phan tú trong map.

#include
using namespace std;

int

{
map<int, int> mp;
UL 2);
({2, 43);
UL 3;

({2, 5);

(3, 6});
cout << << endl;
if( ) cout << "Empty\n";
else cout << "Not empty\n";

if( ) cout << "Empty\n";
else cout << "Not empty\n";

3
Not empty !

7. 28TECH

Become A Better Developer

{(1,2), (254), (3,6)}

for(pair<int, int> it : mp){
cout << it.first << ' ' << it.second << endl;

}

for(auto it : mp){
cout << it.first << '

}

for(auto it : mp){
int key = it.first;
cout << key << ' *

* << it.second << endl;

<< mp[key] << endl;

8. 28TECH

Become A Better Developer MOT só HAM TRONG MAP
Duyét bang iterator:

Duyét map ; E t>:: rp it = mp.begin(); it !=

; Hit){

cout << (*it).first << ' ' << (*it).second << endl;
mp = {(1,2), (2,4), (3,6)} }

//Thay bang auto cho tién
for(auto it = mp.begin(); it .end(); ++it){
(*it).first << ' ' << (*it).second << endl;

28TECH.COMN Sc}

9. 28TECH nas ar im
Become A Better Developer MOT SO HAM TRONG MAP

Ham find: Tim kiém su xuát hién cúa möt key nao
dé trong map. Dó phúc tap là O(logN).

Ham nay tra vé iterator tói cap phan tú néu nó tim
thay, nguoc lai nó tra vé iterator end() cúa map khi
gia tri key tim kiém khóng tón tai trong map. eee

<bits/stdc++.h>

main(){
map mp;
mp.insert({1, 2}); //Thém cap (1,
mp.insert({2, 4}); //Thém cap (2,
mp.insert({3, 6}); //Thém cap (3,
auto it = mp.find(1);
if(it == mp.end()){

cout << "NOT FOUND KEY\n";
}
elsef

cout << (*it).first << ' "

(*it).second << endl;

}
y
OUTPUT: 12

28TECH.COM.UN 5

10. 28TECH

Become A Better Developer

Ham nay dung dé dém só lán xuat
hién cúa 1 key nao dé trong map. Dôi vói map ham

count tra vé O hoác 1, có thé str dung ham nay dé
thay cho ham find. D6 phúc tap O(logN). ee

#include
using namespace std;

int main(){
map<int, int>
mp.insert({1,
mp.insert({2, 4
mp.insert({3,
cout < (1) << endl;
cout << (5) << endl;

1
0

28TECH.COM.VN E

11. 28TECH

Become A Better Developer

#include
using namespace std;

TA BE int {
Xóa mét phan tu khôi map voi dó map<int, int> mp;
phúc tap lá O(logN), truóc khi str dung ham erase mp.insert({1, 2});

hay dam bdo phan tú ban can xóa ton tai trong map me ere ae

neu khöng sé xay ra löi runtime error. ee a);
for(auto it : mp){
cout << it.first <<‘ '
it.second << endl;

}
}

12. 28TECH nas ar im
Become A Better Developer MOT SO HAM TRONG MAP

Xóa thóng qua iterator
<bits/stdc++.h>

main(){
> = = y > ae en map- mp;
Ham erase: Xóa möt phan tú khöi map vói dé mp.insert({1, 2}); //T
phúc tap la O(logN), truóc khi str dung ham erase mp-insert({2) 4})3\//7
hay dam bao phan tú ban can xéa tón tai trong map ee a fn
néu khóng sé xay ra lói runtime error. e... if(it I= pena) ?
mp.erase(it);

for(auto it : mp){
cout << it. first. << "
it.second << endl;

} OUTPUT: 12

}
24

12 28TECH.COM.VN Ein

13. 13

28TECH

Become A Better Developer

Du doán output cua mót só chuong trinh sau

Quiz 1 Quiz 2

<bits/stdc++.h> <bits/stdc++.h>

main(){ main(){
map mp5 map
mp[1]++; mp[1]++; mp[1]++; cout << mp[1]
mp[2] = 3; mp.insert({1,
mp[2] = 4; mp.insert({1,
for(auto it : mp){ mp.insert({1,

cout << it.first << ' ' mp[1] = 5;

it.second << endl; cout << mp[1]
}

5

mp;
<< endl;
2});
3});
45

<< endl;

28TECH.COM.UN 5

14. 14

28TECH

Become A Better Developer

Du doán output cua mót só chuong trinh sau

Quiz 3 Quiz 4

<bits/stdc++.h> <bits/stdc++.h>

main(){ main(){
map mp; map mp;
mp.insert({1, 2}); int alll) = 12,4 lo de EN Le Ey ly 1};
mp.insert({1, 3}); for(int x : a){
mp.insert({1, 4}); mp[x1++;
mp[2] = 3; mp[3] = 4; mp[3]++; y
auto it = mp.find(3); for(auto it : mp){
=r it; cout << it.first << ' ' << it.second <<
cout << (*it).first << ' "
(*it).second << endl;

y

28TECH.COM.UN 5

15. 28TECH

Become A Better Developer 2 . M U LTI M A P:

Multimap tuong tu nhu map có diéu khác biét lá trong
multimap cé thé tôn tai nhiéu key có cing gid tri. Cac

tinh chat nhu key duc sap xép tang dan hay dó phúc
tap, cach str dung ham thi tuong tu nhu map. Có 3 ham (Ele

có su khác biét so véi map là : find, count, erase.

Chú y: Trong multimap ban không thé truy cap value
thóng qua key, hoäc gan theo cu pháp maplkey] = value.

28TECH.COM.VN Ein

16. 28TECH

Become A Better Developer

Vi trong multimap có nhiéu key có cling
gia tri nén néu ta tim kiém gia tri cua 1 key nao do

nö sé tra vé vi tri xuát hién dau tién cúa key dé trong
multimap. O

#include
using namespace std;

int
multimap<int, int> mp;
mp.insert({1, 2});
mp.insert({1, 3});
mp.insert({1, 4});
mp.insert({2, 5});
auto it = a);
cout << (*it).first <<

(*it).second << endl;

} 12

28TECH.COM.VN E

17. 28TECH

Become A Better Developer

#include
using namespace std

int §
multimap<int, int> mp

mp.insert({1, 2});
mp.insert({1, 3});
mp.insert({1, 4});
mp.insert({2, 5});
cout << (1) << endl;
cout << (2) << endl;

28TECH.COM.VN E

18. 28TECH

Become A Better Developer

ttinclude <bits/stdc++.h>
using namespace std;

int main(){
_ A E we multimap<int, int> mp;
Xóa thong qua gia tri sé xóa tat ca mp.insert({1, 2});

các key tuong ting. ee mp.insert({1, 3));
mp.insert({1, 4});
mp.insert({2, 5});
mp.insert({2, 6));
mp.erase(1);
for(auto it : mp){
cout << it.first <<
<< it.second << endl;

25)
26

}

28TECH.COM.VN $;

19. 28TECH = wot
Become Baterbevelper MÔT SÓ HAM TRONG MULTIMAP

Xóa báng iterator
<bits/stdc++.h>

main(){
multimap
. : mp.insert({1, 2});
Ham erase: Xóa thóng qua iterator sé xóa phan tú mp.insert({1, 3});

ma iterator do chi vao. eco mp.insert({1, 4});
mp.insert({2, 5});
mp.insert({2, 6});

mp;

OUTPUT: 13
14
25

auto it = mp.find(1); 26

mp.erase(it);
for(auto it : mp){

cout << it.first <<

<< it.second << endl;
}
D
19

28TECH.COM.UN 5

20. 28TECH

Become A Better Developer

#include
using namespace std;

int {
unordered_map<int, int> mp;
insert({1, 4});

mp.
Unordered_map ciing nhu map mp.insert({1, 2});

nhung trong unordered_map mp.insert({1, 3});

mp.insert({2, 5});

mp.insert({2, 6});

mp.insert({3, 5});

for(auto it : mp){
cout << it.first <<

<< it.second << endl;

y

nhu map vá multimap.

}

21. 28TECH

Become A Better Developer 3. UNORDERED_MAP

Su khac biét

Unordered_map khác vói map vá multimap 6 tôc dö

cúa các ham phd bién nhu count, find, vá erase. Con

cach str dung thi khóng có gi khác biét so vói map.

+ Omap vá multimap cdc ham có dó phúc tap lá O(logN).

+ O unordered_map tóc dó cúa cdc ham trong truöng hop
tôt nhát lá O(1) cón té nhát có thé lén dén O(N).

28TECH.COM.VN Ein