unordered_map

말 그대로 정렬되지 않은 Map이다.

일반 Map은 이진트리로 정렬되어 저장되지만,

Unordered_map은 Hashtable을 기반으로 정렬되지 않은 key-value 쌍을 관리한다.

 

---

[unordered_map의 특징]

1. key-value 쌍으로 다뤄야할때 사용
2. 정렬 X
3. 중복 허용 X
4. Hashtable을 사용하여 key 값을 찾는다
   • 따라서 조회 속도가 O(1)
5. 추가/삭제/조회 속도가 O(1)
   • 이진트리로 구현되어 O(logN)만큼 걸리는 일반 Map보다 빠르다

 

---

[Hash Table의 활용]

 

key 값을 해시함수를 통해 해시로 저장해두고

해시에 대한 value 값을 저장해둔다.

 

---

[unorderd_map functions]

 

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

 

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

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

 

1. operator [key] (탐색용)
   • key가 있다면 value 값 반환
   • key가 없다면 0 반환
2. operator [key] (추가용)
   • key가 없다면 0으로 세팅
   • key가 있다면 value 업데이트
   • 그래서 아래와 같은 코드가 가능함.

	unordered_map<string, int> m;

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

 

---

[unordered_map 순회]

 

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

iterator로 하는건 느리다

 

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

unordered_map<string,int> map;

vector<pair<string,int>> v(map.begin(), map.end());

 

---

[unordered_map 정렬]

 

정렬은 위와 같이 vector로 치환한 후, sort 함수로 진행하는 것이 가장 직관적이다.

priority_queue를 활용할 수 도 있지만 그냥 vector로 바꾸고 sort 함수 쓰자.

 

bool comp(pair<string, int> p1, pair<string, int> p2)
{
    if (p1.second == p2.second)
    {
        return p1.first < p2.first;
    }

    return p1.second > p2.second;
}

vector<pair<string, int>> v(map.begin(), map.end());
sort(v.begin(), v.end(), comp);