[C++] map, unordered_map with Cpp

 

1. map

 

정의

• 고유한 키를 기반으로 키 - 값 (key-value) 쌍으로 이루어져 있는 정렬된(삽입할 때마다 자동 정렬) 연관 컨테이너 
• 레드 - 블랙트리로 구현
  • 균형 이진 검색 트리 

 

시간복잡도

• 레드 - 블랙트리로 구현되어 있어서
• 삽입, 삭제, 수정, 탐색 -> O(logN) 

 

특징

• 고유한 키를 갖기 때문에 하나의 키에 중복된 값 xxx
• 자동으로 오름차순 정렬되기 때문에 넣은 순서대로 map을 탐색하는 것이 아닌 아스키코드순으로 정렬된 값들을 기반으로 탐색 
• 대괄호 연산자 [] 로 해당 키로 직접 참조 가능
• 키와 value는 string이나 int 뿐만 아니라 다양한 값이 가능
• iterator로 순회 가능

 

예시 코드

#include <bits/stdc++.h>
using namespace std;
map<string, int> mp;
string a[] = {"천", "현", "태"};
int main(){
    for(int i = 0; i < 3; i++){
        mp.insert({a[i], i + 1});
        mp[a[i]] = i + 1;
    }
    // mp에 해당 키가 없다면 0으로 초기화 되어 할당됨.(int의 경우)
    // 만약 mp에 해당 키가 없는지 확인하고 싶고
    // 초깃값으로 0으로 할당되지 않아야 되는 상황이라면
    // find를 써야 함.
    cout << mp["hyeontae"] << '\n';
    // 대괄호로 수정가능
    mp["hyeontae"] = 4;
    cout << mp.size() << '\n';
    mp.erase("hyeontae");
    
    auto it = mp.find("hyeontae");
    if(it == mp.end()){
        cout << "존재하지 않음\n";
    }
    mp["hyeontae"] = 100;
    
    it = mp.find("hyeontae");
    if(it != mp.end()){
        cout << (*it).first << " : " << (*it).second << '\n';
    }
    for(auto it : mp){
    	cout << (it).first << " : " << (it).second << '\n';
    }
    for(auto it = mp.begin(); it != mp.end(); it++){
    	cout << (*it).first << " : " << (*it).second << '\n';
    }
    mp.clear();
    return 0;
}

/*
0
4
존재하지 않음
hyeontae : 100
hyeontae : 100
천 : 1
태 : 3
현 : 2
hyeontae : 100
천 : 1
태 : 3
현 : 2
*/

 

method

 

• insert({key : value})
  • map에다 {key, value}를 집어 넣는다.
• [key] = value
  • 대괄호[]를 통해 key에 해당하는 value를 할당
• [key]
  • 대괄호[]를 통해 key를 기반으로 map에 있는 요소 참조
  • 만약 map에 해당 키에 해당하는 요소가 없다면 0 또는 빈문자열로 초기화가 되어 할당
  • 할당되고 싶지 않아도 대괄호[]로 참조할 경우 자동으로 할당되기 때문에 조심
• size()
  • map에 있는 요소들의 개수 반환
• erase(key)
  • 해당 키에 해당하는 요소를 지운다.
• find(key)
  • map에서 해당 key를 가진 요소를 찾아 해당 이터레이터를 반환
  • 만약 못찾을 경우 mp.end() -> 해당 map의 end() 이터레이터를 반환
• clear()
  • map에 있는 요소 다 제거

 

주의할 점

• 아래 코드처럼 map의 경우 해당 인덱스에 참조만 해도 맵에 값이 생기며 맵의 요소가 생긴다.
• int 형 같은 경우 0, string 또는 char의 경우 빈 문자열

#include <bits/stdc++.h>
using namespace std;
map<int, int> mp;
map<string, string> mp2;
int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);
    cout << mp[1] << '\n';
    cout << mp2["aaa"] << '\n';
    for(auto i : mp) cout << i.first << " " << i.second;
    cout << '\n';
    for(auto i : mp2) cout << i.first << " " << i.second;
    return 0;
}
/*
0

1 0
aaa 
*/

 

따라서, 아래 코드처럼 "맵에 요소가 있는지 없는지"를 확인하고 맵에 데이터를 할당하는 부분의 로직을 구축할 수 있다.

#include <bits/stdc++.h>
using namespace std;
map<int, int> mp;
map<string, string> mp2;
int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);
    if(mp[1] == 0){
        mp[1] = 2;
    }
    for(auto i : mp) cout << i.first << " " << i.second;
    
    return 0;
}

/*
1 2
*/

 

• 다만 위의 코드는 문제에서 해당 키값에 0이 아닌 값이 들어갈 때 활용 가능
• 만약 문제에서 키에 0이 들어가는 경우 위 코드는 활용 불가능
• 이미 if문 안에 mp[1] == 0 을 해버린 순간 이미 mp[1] = 0이 할당되어버리기 때문

 

만약 문제에서 맵의 키 - 값에서 값에 0이 들어가는 경우 아래 코드를 쓰는게 좋다.

또한 이런걸 비교하기 귀찮다면 아래 코드 기반 작성하면 된다.

 

#include <bits/stdc++.h>
using namespace std;
map<int, int> mp;
map<string, string> mp2;
int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL(;
    if(mp.find(1) == mp.end()){
        mp[1] = 2;
    }
    for(auto i : mp) cout << i.first << " " << i.second;
    
    return 0;
}

/*
1 2
*/

 

---

2. unordered_map

• 앞서 본 map의 경우 자동 정렬
• unordered_map은 정렬이 되지 않은 map이며
• method는 동일

 

map과 unordered_map 비교

• map
  
  • 정렬이 됨
  • 레드 블랙 트리 기반
  • 탐색, 삽입, 삭제 -> O(logN)
• unordered_map
  
  • 정렬이 안됨
  • 해시테이블 기반
  • 탐색, 삽입, 삭제 -> 평균 O(1), 최악 O(N) 

 

예시 코드

 

#include<bits/stdc++.h>
using namespace std;
unordered_map<string, int> umap;
int main(){
    umap["bcd"] = 1;
    umap["aaa"] = 1;
    umap["aba"] = 1;
    for(auto it : umap){
    	cout << it.first << " : " << it.second << '\n';
    }
}
/*
정렬이 되지 않는다.
aba : 1
aaa : 1
bcd : 1
*/

 

• 정렬이 필요하지 않은 문제에는 unordered_map을 써야할 것 같지만 시간 초과가 나기도 한다
  • 가장 최악의 경우 O(N)이기 때문
  • 그냥 되도록 map을 쓰는 것을 권장