[C++] map과 unordered_map
in Algorithm on Map, Unordered_map
c++에서 Map은 map과 unordered_map 을 주로 사용합니다. 두 자료구조 모두 Key:Value 형태로 저장되지만, 데이터가 저장될 때 자동정렬여부와 탐색속도 등에서 차이가 발생합니다. 아래에 표로 간단히 정리해두었습니다.
map과 unordered_map의 비교
| 항목 | map | unordered_map |
|---|---|---|
| 정렬 | 오름차순 자동정렬 | 정렬 X |
| 중복허용 | X | X |
| 기반 | 레드블랙트리 | hash table 기반 hash container(해싱 가능) |
| 메모리 | 보다 적게 든다 | . |
| 탐색시 시간복잡도 | O(logN) - binary Search기반 | O(1) - hashing |
| 문자열 길이가 길고 데이터가 크지 않을 때 | 보다 유리 | 길이에 그대로 반응하기 때문에 상대적으로 불리(해싱에 소요되는 리소스있음) |
*unordered_map의 경우 해싱이 가능하기 때문에 데이터가 많을 때 탐색이 많이 이루어지는 경우 유용하게 사용될 수 있습니다.(ex. 클래스를 만들어 연결리스트 대용으로도 사용 가능)
unordered_map의 정렬
- key로 정렬
사실 map을 쓰면 key 기준 오름차순으로 자동정렬 해주기 때문에 굳이 unordered_map을 사용해야할까 싶습니다. 하지만 데이터가 많아지면 map은 해싱을 사용하는 unordered_map보다 데이터 탐색시 시간이 오래 걸리기 때문에 map대신에 unordered_map을 사용하고, key값으로 정렬하는 방식을 고려해볼 만합니다. 사실, 기본적으로 map은 binary search로 데이터를 탐색하기 때문에 일반적으로 모든 데이터를 훝는 방식보다는 성능이 좋지만, 혹시라도 unordered_map을 key로 정렬하는 해야할 일이 생긴다면, 다음의,
- value로 정렬
문자열이 여러개 주어지고, 1) 각 문자열이 등장한 빈도수가 높은 순서대로 2) 문자열 기준 사전순으로 unordered_map을 정렬합니다.
#include <vector>
#include <unordered_map>
#include <algorithms>
#include <iostream>
using namespace std;
// 1. 문자열의 빈도로만 정렬(내림차순)
bool cmp_1(pair<string, int>& a, pair<string, int>& b) {
return a.second > b.second;
}
// 2. 문자열의 빈도로 내림차순 정렬하고, 만약 빈도수가 같다면 문자열 기준으로 사전순으로 정렬
bool cmp_2(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() {
unorderd_map<string, int> cnt_map;
// 데이터 저장 -> key(과일이름) : value(빈도수, 임의로 저장)
cnt_map["apple"] = 1;
cnt_map["pineapple"] = 5;
cnt_map["banana"] = 5;
vector<pair<string, int>> vec(cnt_map.begin(), cnt_map.end()); //map -> vector
sort(vec.begin(), vec.end(), cmp_1(or cmp_2)); // 원하는 정렬 조건 넣어서 정렬
}
// result (vector 요소)
// 1. cmp_1로 정렬
// (("pineapple", 5), ("banana", 5), ("apple", 1));
// 2. cmp_2로 정렬
// (("banana", 5), ("pineapple", 5), ("apple", 1));
// pineapple이 먼저 입력되었음에도 banana가 사전순으로 빠르기 때문에 앞선다.(cmp_1과의 차이)
unordered_map 기본 함수 / 연산자
unordered_map<T, T> M: 컨테이너 객체(M) 생성
- M.at(key) : 지정된 키 값을 이용하여 unorderd_map에서 요소를 찾음
- M.clear() : 모든 요소를 제거
- M.find(key) : 지정된 키와 일치하는 요소를 찾음. 키와 일치하는 요소가 있다면 const_iterator를 반환하고, 없다면 M.end()를 반환
- M.erase(key): 지정된 키와 일치하는 요소를 제거
- insert(pair<T, T>) : M에 key와 value 삽입(pair형태로 삽입해야함)
- M.count(key) : 지정한 키와 일치하는 요소의 수 찾음
- M.begin() : 제어되는 시퀀스 또는 버킷의 시작을 지정
- M.end() : 제어되는 시퀀스의 끝을 지정
- M[key] : 지정된 키가 있는 요소를 찾거나 삽입함