[C++] STL unordered_map

일반 map

• 균형 이진 트리인 레드-블랙 트리 사용
• 삽입, 삭제, 검색: O(logN)

unordered_map

• 해시 테이블 기반의 구현 제공
• 평균적으로 상수 $O(1)$ 시간복잡도 → 많은 양을 저장했을 때의 장점
  
• 적은 데이터 : 메모리 낭비, 검색 시 오버헤드 → 수 천 이상의 자료 저장시 Good!
  
• 많은 자료 저장, 빠른 검색, 빈번한 삽입삭제 X
• 키값 : 해시 가능 → int, double, char
  
• 키-값 쌍이 특정 순서로 정렬 X

1. 선언

#include <unordered_map>
unordered_map<string, int> h;

2. 삽입

h.insert({"one", 1});
h["two"] = 2;

unordered_map<int, float> h2;
h2.insert(h.begin(), h.end());

3. 순회

for (auto it = h.begin(); it != h.end(); ++it) {
    cout << it -> first << " " << it -> second << '\n';
}

4. 참조

h.at("one");
h.at("three");   //존재X, 예외 발생

h["two"];
h["three"];   //존재X, 삽입 후 기본 값 반환

5. 검색

auto res = h.find("four");
if (res != h.end()) cout << res -> second << '\n';
else cout << "Not found" << '\n';

6. 제거

h.clear();   //모든 원소 제거
h.erase("two");   //특정 원소 제거

7. 원소 개수

h.empty();   //비어있는지 확인

h.count("five");   //특정 키를 가진 원소 개수 반환 (0, 1)