알고리즘 / unordered_map

C++ STL 중 해쉬 맵 unordered_map을 설명한다.

특징

• map보다 더 빠른 탐색을 하기 위한 자료구조이다. 
• unordered_map은 해쉬테이블로 구현한 자료구조로 탐색 시간복잡도는 O(1)이다.
• map은 Binary Search Tree로 탐색 시간 복잡도는 O(log n)이다.
• unordered_map을 사용하기 위해서는 #include< unordered_map> 을 선언해야 한다. 
• unordered_map은 중복된 데이터를 허용하지 않고 map에 비해 데이터가 많을 시 월등히 좋은 성능을 보인다.
• 하지만, key가 유사한 데이터가 많을 시 해시 충돌로 인해 성능이 떨어질 수도 있다.
• index로 접근할 수 없고 iterator로 접근해야 한다. 
• 데이터가 많은 경우에는 unordered_map 이 map 보다 성능면에서 유리하다.
• 문자열을 키로 사용하는 경우 문자열이 길어질 수록 unordered_map 이 map에 비해 더 성능이 떨어질 수 있다. 
• 유사도가 높은 문자열 집합을 키로 사용하는 경우에 map 의 성능이 떨어질 수 있다. 
• 
  
  

출처 : https://math-coding.tistory.com/31 

 

함수

• empty( ) : 맵이 비어있는지 확인하는 함수이다.
• size( ) : 맵의 크기를 반환하는 함수이다.
• operator[ ] : 맵에서 key를 통해 value를 지정한다. 
• find(key) : key에 해당하는 원소를 찾는 함수이다.
• count(key) : key에 해당하는 원소의 갯수를 반환하는 함수이다.
• insert( {key, value} ) : 맵에 pair<key, value> 를 추가하는 함수이다.
• erase(key) : key에 해당하는 원소를 제거하는 함수이다.
• clear( ) : 맵을 초기화하는 함수이다.