map과 unordered_map, 그리고 map과 value 정렬

 

map과 unordered_map의 차이 요약

 

	map	unordered_map
시간복잡도	O(logN)	O(1)
데이터 정렬	레드블랙 트리 (Red-Black Tree) -> 중복허용 X, Key를 기준으로 오름차순 자동정렬	해시테이블 (Hash Table) -> 중복허용 X, 정렬되지 않음
권장하는 사용법	1. 데이터 양이 보다 적을때 권장 2. Key를 이용하여 정렬을 해야할때 권장	대량의 데이터를 저장할때 권장

 

* 레드블랙트리 : 이진탐색트리의 일종

* 해시테이블 : 키 값을 주소로 사용

 

 

map활용 예시 : 사용된 영어 단어들을 1. 빈도순 2. 문자순으로 정렬

 

예를들어 사용된 단어들이 1. 많이 사용됐을수록, 2. 사전순으로 앞에 올수록 더 앞에 위치하게 정렬을 한다고 가정해보자. map을 사용하면 해결이 될 것 같지만 map은 key값을 기준으로 오름차순으로 정렬된다. 또한, 사전순으로 앞에 올 수록이라는 조건까지 추가되어 단순히 map만으로는 정렬이 쉽지 않을 것 같다.

 

이럴경우 먼저 다음과 같은 로직으로 구현을 하면 된다.

 

1. map에 사용된 영어단어들과 빈도수를 저장

2. map의 값들을 vector에 저장

3. vector를 사용자의 편의에 맞춰 정렬

 

 

[예시 코드]

#include <iostream>
#include <algorithm>
#include <vector>
#include <unordered_map>

using namespace std;

bool comp(pair<string,int> &a, pair<string,int> &b) {
    if (a.second == b.second) return a.first < b.first;
    return a.second > b.second;
}

int main() {
    ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
    unordered_map<string, int> mp; // "abc", "acb", "ade", "abcccccccc", "abdddddddd";
    mp["abdddddddd"]+=2;
    mp["abcccccccc"]++;
    mp["ade"]++;
    mp["acb"] += 2;
    mp["abc"] += 2;
    vector<pair<string, int>> v(mp.begin(), mp.end());
    sort(v.begin(), v.end(), comp);
    for (auto i : v) cout << i.first << " " << i.second << "\n";
    return 0;
}

 

[결과]

목표대로 1. 많이 사용될수록 2. 사전순으로 앞에 올수록 정렬이 되었다.