[C++] map & unordered_map

0. 참고자료

 

(24) C++ map헤더의 map 사용법

 

[C++] pair, map, tuple 완정 정복 (20/7/9 수정)

pair로 map을 구현했다는 것을 알 수 있다.

 

---

2. map

 

가. 예제 1

#include<iostream>
#include<map>
using namespace std;

map<string, int> mp;
string a[]={"가나다", "마바사", "아자차"};
int main(){
    mp.insert({a[0], 1});
    mp.insert(make_pair("마바사", 2)); //pair의 문법. map과 pair의 관계
    mp[a[2]] = 3;

    for(auto it = mp.begin(); it !=  mp.end(); it++){
        cout << "(*it) " << (*it).first << " : " << (*it).second << endl;
    }
    //해당 값이 없으면 0으로 초기화
    cout << "size of map "<< mp.size() << endl; //size of map
    cout << "카타파는? " << mp["카타파"] << endl;
    cout << "카타파 추가 "<<  mp.size() << endl; //size of map

    auto it = mp.find("카타파"); //map<string, int>::iterator it
    if(it != mp.end()) {
        cout << "(*it) " << (*it).first << " : " << (*it).second << endl; 
    }

    mp.erase("카타파");    
    it = mp.find("카타파");
    if(it == mp.end()) cout << "not found"  << endl;

    //pair으로 순회
    for(pair<string, int> i : mp){
        cout << "(pair) " << (i).first << " : " << (i).second << endl; 
    }

    //iterator로 순회
    for(map<string, int>::iterator it = mp.begin(); it != mp.end(); it++){
        cout << "(*it) " << (*it).first << " : " << (*it).second << endl;
    }

    mp.clear();
    return 0;
}

/*
(*it) 가나다 : 1
(*it) 마바사 : 2
(*it) 아자차 : 3
size of map 3
카타파는? 0
카타파 추가 4
(*it) 카타파 : 0
not found
(pair) 가나다 : 1
(pair) 마바사 : 2
(pair) 아자차 : 3
(*it) 가나다 : 1
(*it) 마바사 : 2
(*it) 아자차 : 3
*/

• #include<map>, map<string, int> mp; : map 선언

 

1) insert()

...    
mp.insert({a[0], 1});
mp.insert(make_pair("마바사", 2)); //pair의 문법. map과 pair의 관계
mp[a[2]] = 3;

 

2) size()

...
cout << "size of map "<< mp.size() << endl; //size of map
cout << "카타파는? " << mp["카타파"] << endl; //해당 값이 없으면 0으로 초기화
cout << "카타파 추가 "<<  mp.size() << endl; //size of map
/*
size of map 3
카타파는? 0
카타파 추가 4
*/

 

3) find()

...
    auto it = mp.find("카타파"); //map<string, int>::iterator it
    if(it != mp.end()) {
        cout << "(*it) " << (*it).first << " : " << (*it).second << endl; 
    }
//(*it) 카타파 : 0

못 찾을 경우 mp.end()에 해당하는 iterator를 반환한다.

 

map의 경우 해당 인덱스에 참조만 해도 맵에 값이 생기며 맵의 요소가 생기게 된다.

 

int형 같은 경우 0으로. string 같은 경우 빈문자열로 들어가게 된다.

 

find()를 사용하면 예방할 수 있다.

 

4) erase()

...
    mp.erase("카타파");    
    it = mp.find("카타파");
    if(it == mp.end()) cout << "not found"  << endl;
//not found

 

5) pair, iterator로 순회

...
    //pair으로 순회
    for(pair<string, int> i : mp){
        cout << "(pair) " << (i).first << " : " << (i).second << endl; 
    }

    //iterator로 순회
    for(map<string, int>::iterator it = mp.begin(); it != mp.end(); it++){
        cout << "(*it) " << (*it).first << " : " << (*it).second << endl;
    }

• it != mp.end(); : iterator는 대소를 비교할 수 없음.

 

6) clear()

...
    mp.clear();

 

---

나. 예제 2

#include<iostream>
#include<map>
using namespace std;

map<int, int> mp;
map<string, string> mp2;

int main(){
    cout << "mp[1] : " << mp[1] << endl;
    cout << "mp2[\"aaa\"] : " << mp2["aaa"] << endl;
    for(auto i : mp) cout << i.first << " : " << i.second << endl;
    for(auto i : mp2) cout << i.first << " : " << i.second << endl;
    mp.clear();
    mp2.clear();
    return 0;
}
/*
mp[1] : 0
mp2["aaa"] : 
1 : 0
aaa : 
*/

• cout << "mp[1] : " << mp[1] << endl; : map이 비어 있으므로 0 출력
• cout << "mp2[\"aaa\"] : " << mp2["aaa"] << endl; : map이 비어 있으므로 “” 출력

 

---

다. 예제 3

#include<iostream>
#include<map>
using namespace std;

map<int, int> mp;
int main(){
    if(mp.find(1)==mp.end()){
        mp[1]=2;
    }
    for(auto i : mp) cout << i.first << " : " << i.second << endl;
    mp.clear();
    return 0;
}
// 1 : 2

만약 map mp에서 키 1을 찾지 못했다면 (find 메서드가 end를 반환했다면), mp[1]을 2로 설정하라는 것.

 

---

라. 맵을 쓸 때 주의할 점

 

1. key는 unique 해야 한다. 중복된 key를 사용하여 입력하면 덮어 써진다. 중복된 key를 사용해야 하면 multimap을 살펴보자.
2. map의 경우 해당 인덱스에 참조만 해도 맵에 값이 생기며 맵의 요소가 생기게 된다. int형 같은 경우 0으로. string 같은 경우 빈문자열로 들어가게 된다. find()를 사용하면 예방할 수 있다.
3. 데이터를 정렬하는 map의 특성상 key 값의 분포가 고르지 못하면 balancing에 대한 비용으로 성능이 저하될 수 있다. 이때는 오히려 hash table을 기반으로 하는 unordered_map이 유리할 수 있다.

 

---

2. unordered_map

 

unordered_map은 정렬이 되지 않은 map이며 메서드는 map과 동일합니다.

 

단, map은 레드블랙트리를 기반으로 정렬이 된 상태다.

 

탐색, 삽입, 삭제에 O(logN)의 시간복잡도가 보장된다.

 

반면 unordered_map은 해시테이블 기반으로 정렬이 안된 상태다.

 

탐색, 삽입, 삭제에 평균적으로 O(1), 가장 최악의 경우 O(N)의 시간복잡도를 가진다.

 

#include<iostream>
#include<unordered_map>
using namespace std;

unordered_map<string, int> umap;
int main(){
    umap["bbb"] = 1;
    umap["aaa"] = 2;
    umap["ccc"] = 3;
    for(auto i : umap){
        cout << i.first << " : " << i.second << '\n';
    }
}
/*
ccc : 3
aaa : 2
bbb : 1
*/

• umap["bbb"] = 1;, umap["aaa"] = 2;, umap["ccc"] = 3; : 키-값 추가.

 

---