[C++] map, unordered_map

map

• Binary Search Tree로 구현되어 O(log n)의 탐색 시간 복잡도를 가지는 자료구조
• Red-Black로 구현이 되어있어 문자열 비교에 유리함
• key 값을 기준으로 오름차순 정렬이 되어있음
• m.insert({key, value}) == m[key]=value
• m.find(key) ==m.end() key 존재 유무 판별
• m.count(key) 를 사용해도 동일한 시간복잡도 O(logn)만에 key 존재 유무를 판별할 수 있음
• 해당 key가 존재하면 1을 반환 or 없다면 0을 반환

• unordered_map을 사용하면 O(1)만에 찾을 수 있음

iterator 사용법

for(auto it = m.begin(); it != m.end(); it++)
	printf("key: %d, value: %d\n", it->first, it->second);

// or

for(auto it: m)
	printf("key: %d, value: %d\n", it.first, it.second);

 

 

unordered_map

• hash_map으로 쓰이다 표준으로 정의되며 STL에는 unordered_map으로 성능을 보장한 버전이 포함됨 (hash_map은 성능이 보장되지 않기 때문)
• 입력되는 데이터를 해시 함수를 통해서 해시 테이블에 저장하며 이론적으론 O(1)의 탐색 시간 복잡도를 가짐
• 따라서 map보다 빠른 탐색을 지원하며 C++에서 #include<unordered_map>을 선언하여 사용 가능
• 순서대로 자료를 보관하지 않으며 map과 마찬가지로 중복된 데이터를 허용하지 않고, 데이터가 많을 수록 map보다 월등히 좋은 성능을 보임

• 하지만 저장하는 데이터가 적을 때, 메모리 낭비나 key가 유사한 데이터가 많을 시엔 해시 충돌로 인해 오버헤드라는 문제가 생겨 vector나 list, map이 더 빠를 수 있음
• 문자열을 key로 사용할 경우 map이 탐색 성능의 우위를 지님
• 많은 데이터(수 천 이상)를 저장하며 검색 속도가 빨라야 할 때, 자주 데이터를 삽입, 삭제하지 않을 때 사용해야 함