Map과 unordered_map, Set과 multiset(C++)(알고리즘)

위 글은 큰돌의 터전 님의 강의자료를 참조해서 정리하고 제가 알고리즘을 풀면서 더 추가적으로 사용할 만한 내용들을 정리한 글입니다.

알고리즘 풀이 강의로 큰돌의 터전님의 강의 강력 추천드립니다.

강의링크

map

map은 고유한 키를 기반으로 키 - 값(key - value) 쌍으로 이루어져 있는 정렬된(삽입할 때마다 자동 정렬된) 연관 컨테이너입니다.

레드 - 블랙트리로 구현됩니다.

레드 - 블랙 트리로 구현되어있기 때문에 삽입, 삭제, 수정, 탐색이 O(logN)의 시간복잡도를 가집니다.

고유한 키를 갖기 때문에 하나의 키에 중복된 값이 들어갈 수 없으며 자동으로 오름차순 정렬되기 때문에 넣은 순서대로 map을 탐색할 수 있는 것이 아닌 아스키코드순으로 정렬된 값들을 기반으로 탐색하게 됩니다.

또한 대괄호 연산자 [] 로 해당 키로 직접 참조할 수 있습니다. 예를 들어서 "이승철" : 1, "김현영" : 2 이런식으로 string : int 형태로 값을 할당해야 할 때 있죠?

그럴 때 map을 씁니다. 맵의 키와 value는 string이나 int 뿐만 아니라 다양한 값이 들어갈 수 있습니다.

• 레드블랙트리 : 균형 이진 검색 트리이며 삽입, 삭제, 수정, 탐색에 O(logN)의 시간복잡도가 보장됨.

#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사용해야한다. 	되어서 출력이 된다. 	
    //대괄호 이용해서 수정 	
    mp["큰돌"] = 4; 	
    cout << mp.size() << '\n'; 	
    mp.erase("큰돌"); //큰돌이라는 key를 가진 걸 삭제한다. 	
    cout << mp["큰돌"] << '\n';//여기선 큰돌에 해당하는 key가 없기 때문에 0이 할당
    auto it = mp.find("큰돌"); 	
    if (it == mp.end()) //find했는데 없다면 map의 end()에 해당하는 이터레이터 반환한다. 	
    	cout << "I can't find 큰돌\n"; 	
    mp["큰돌"] = 100; // 큰돌이라는 key의 value로 100을 준다. 	 	
    it = mp.find("큰돌"); 	
    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 
    I can't find 
    큰돌 
    큰돌 : 100 
    토끼 : 1 
    큰돌 : 100	 
    음바페 : 3 
    거북이 : 2 
    토끼 : 1 
    큰돌 : 100	 
    음바페 : 3 
    거북이 : 2 
    */

메소드

mp.insert({key, value}) : map 에 {key, value} 를 집어 넣는다.

mp.size() : map에 있는 요소들의 개수를 반환합니다.

mp.erase(key); :해당 키에 해당하는 요소를 지웁니다.

mp.find(key)

map에서 해당 key를 가진 요소를 찾아 해당 이터레이터를 반환합니다. 만약 못찾을 경우 mp.end() 해당 map의 end() 이터레이터를 반환합니다.

mp.clear(); : map에 있는 요소들을 다 제거합니다.

map 사용법

[key] = value

대괄호 []를 통해 key에 해당하는 value를 할당합니다.

[key]

대괄호 []를 통해 key를 기반으로 map에 있는 요소를 참조한다.

만약 map에 해당 키에 해당하는 요소가 없다면 0 또는 빈문자열로 초기화가 되어 할당됩니다. (int는 0, string이나 char은 빈 문자열로 할당됩니다.) 할당하고 싶지 않아도 대괄호[]로 참조할경우 자동으로 할당되기 때문에 조심해야 합니다.

for(auto it : mp)

범위기반 for루프로 map에 있는 요소들을 순회합니다. map을 순회할 때는

key는 first, value는 second

로 참조가 가능합니다.

for(auto it = mp.begin(); it != mp.end(); it++)

map은 이터레이터로 순회할 수 있습니다.

주의 사항

map의 경우 index만 참조를 해도 map의 값이 생성되서 빈 문자열이 생기게 됩니다. 따라서 map의 요소가 있는지 없는지 검사를 find를 이용해서 하고 그 값을 넣어주면 된다.

또한 map은 key값을 기준으로 정렬이 된다. 이 것을 염두하고 코드를 작성하는 것이 좋다.

 

 

unorderded_map

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

map과 unordered_map을 비교하면 다음과 같습니다.

• map : 정렬이 됨 / 레드블랙트리기반 / 탐색, 삽입, 삭제에 O(logN)이 걸림

• unordered_map : 정렬이 안됨 / 해시테이블 기반 / 탐색, 삽입, 삭제에 평균적으로 O(1), 가장 최악의 경우 O(N)

unordered_map 은 다음과 같이 씁니다.

#include <unordered_map>

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을 쓰는 것을 권장합니다.

 

 

Set

셋(set)은 고유한 요소만을 저장하는 컨테이너 입니다. 중복을 허용하지 않습니다. map처럼 {key, value}로 집어넣지 않아도 되며 다음 코드처럼 pair나 int형을 집어넣어서 만들 수 있습니다. 중복된 값은 제거 되며 map과 같이 자동 정렬됩니다. 메서드는 map과 같습니다.

#include <bits/stdc++.h> 
using namespace std; 
int main()
{ 	
	set<pair<string, int>> st; 	
    st.insert({"test", 1}); 	
    st.insert({"test", 1}); 	
    st.insert({"test", 1}); 	
    st.insert({"test", 1}); 	
    cout <<st.size() <<"\n"; 	
    set<int> st2; 	
    st2.insert(2); 	
    st2.insert(1); 	
    st2.insert(2); 	
    for(auto it : st2)
    { 		
    	cout << it << '\n'; 	
    } 
 }
 /* 1 1 2 */

 

multiset

multiset은 중복되는 요소도 집어넣을 수 있는 자료구조 입니다. key, value형태로 집어 넣을 필요도 없고 넣으면 자동으로 정렬된다. 메서드는 역시 map과 같습니다.

#include <bits/stdc++.h> 
using namespace std;
multiset<int> s;
int main()
{ 	
	for(int i = 5; i >= 1; i--)
    { 		
        s.insert(i); 		
        s.insert(i); 	
    } 	
    for(int it : s) cout << it << " "; 	
    cout << '\n'; 	
	return 0; 

} /* 1 1 2 2 3 3 4 4 5 5 */

 

Uploaded by

N2T