[STL]map, unordered_map

map

 - map은 red-black Tree로 구현돼 있다. 즉, 균형 트리 형태

#include<map>
std::map<key,value> 변수명 ;

 

unordered_map

 - unordered_map은 hash table로 구현돼 있다.

#include<unordered_map>
std::unordered_map<key,value> 변수명 ;

 

사용법

 - 둘 다 <key,value> 꼴로 데이터를 저장한다.

 - 삽입을 위한 insert, 삭제를 위한 delete, find, count, size, clear 등 사용법은 동일하다.

 

 

차이점

 - map 과 unordered_map의 큰 차이 점은 구현에서 부터 이미 차이가 난다. 

 - map은 탐색연산의 시간복잡도가 O(log N) 인 반면 unordered_map은 O(1) 이다.

 - map은 균형트리에 맞게 항상 정렬하지만, unordered_map은 그렇지 않다.

 

 

결론

 - 정렬을 필요로 하는 경우가 아니라면 연산속도는 unordered_map이 훨씬 유리하다.

 - 일반적으로 key값이 짧고, int형인 경우 unordered_map을 권장한다.

 - key값이 길고 복잡하며, 유사한 값이 많을 경우 unordered_map의 해쉬 충돌로 인해 성능이 저하될 수 있다.

 

 추가적인 map의 사용법은 후에 포스팅 하겠습니다.

 

코딩을 공부하고 있는 학생입니다.

공부한 것을 정리, 공유하기 위해 블로그를 운영하고 있습니다.

포스팅에 틀린 부분이 있다면 과감한 지적, 수정의 한 마디 부탁드립니다! 감사합니다 :)

github.com/holicAZ

holicAZ - Overview