[C++ STL] unordered_map

 

1. 말 그대로 정렬되지 않은 map 임

2. hashtable 사용. 해시함수로 원소 찾음

3. map의 특성을 그대로 가지고 가지만 정렬만 안되어있을 뿐임

 

4. 중복 허용X

 

5. 일반 map보다 탐색속도가 빠름

map O(logN)

unordered_map O(1)

 

보통 이럴때쓴다

 

1. 데이터를 받아야하는데 정렬이 필요없이 pair 객체로 받아야할때

// key값 int value도 int
unordered_map<int, int> um;

 

2. 특정 key값의 원소들을 vector에 다 같이 저장하고 싶을때

// key값 int
// value값 int 저장하는 vector
unordered_map<int, vector<int>> group;

// key값 int 
// value값 pair객체를 저장하는 vector
unordered_map<int, vector<pair<int, int>>> group;

 

 

---

[unordered_map 의 특징] 

1. map과 동일하게 pair 객체를 (key value) 한 쌍으로 하여 저장

2. 중복을 허용하지 않음

operator[ ] 사용 시 : value 업뎃 O

insert 사용 시 : value 업뎃 X

 

3. 정렬 없이 저장한다 (자료 저장 시 자동정렬 X)

4. key 값을 해시테이블의 해시 저장한다

그래서 탐색속도가 O(1)임

 

---

[unorderd_map functions]

 

#include <unordered_map>

 

일반 map보다 더 빠른 탐색을 하기 위한 자료구조

 

unordered_map은 중복된 데이터를 허용하지 않고

map에 비해 데이터가 많을 시 월등히 좋은 성능을 보임

 

operator [KEY] (탐색용) O(1)

1) KEY 값 있으면 VALUE 값 반환

2) KEY 값 없으면 0 반환

 

operator[KEY] (추가용) O(1)

없으면 0으로 세팅

있으면 VALUE 업뎃

 

그래서 이런 코드가 가능함

	unordered_map<string, int> m;

	for (int k = 0; k < N; k++) {
		cin >> str;
		m[str]++;
	}

 

operator[KEY] = VALUE (추가용) O(1)

{ KEY, VALUE } pair 객체 생성

만약 해당 KEY 값이 있었다면 VALUE 값 업데이트

 

insert( {key, value} )

얘도 map과 같이 key가 있다면 아무런 일도 일어나지 않는다

operator [ ] 와 달리 value 업뎃이 없다!

 

erase( key )

특정 position의 pair 삭제, key를 통해 삭제, 범위 삭제

 

---

[unordered_map 순회]

 

당연히 index로 접근할 수 없고 iterator로 접근해야하는데

iterator로 하는건 느리다

그래서 vector로 치환해서 index로 순회하는게 훨씬 나음

 

  // unordered_map을 vector<pair<char, int>>로 변환
vector<pair<char, int>> temp(umap.begin(), umap.end());

// 정렬 (예제: 빈도수가 높은 순서대로 정렬)
sort(temp.begin(), temp.end(), [](const pair<char, int>& a, const pair<char, int>& b) {
	return a.second > b.second;
});