<자료구조> Unordered Map과 Map 차이

Unordered Map : hash 방식으로 구현

key hash 값에 따라 저장

O(1)

 

Map : 균형 이진 트리(Red-black tree)로 구성됨

key에 따라 정렬되어 저장

O(logN)

 

키 값이 고르지 못할 경우 Insert/Delete 성능이 저하

(그러나 O(logN)의 성능은 보장됨)

 

속도(데이터 양이 많을시)

Unordered Map > Map

 

숫자형 키를 사용할 경우

Unordered Map > Map

 

문자열 키를 사용할 경우

Unordered Map > Map (이부분은 경우에 따라 다르다.)

 

정렬이 필요하다면 map을 사용하고 그외에는 Unordered Map을 사용하자.

 

 

정리

map : 정렬이 됨 / 레드블랙트리기반 / 탐색, 삽입, 삭제에 O(logN)이 걸림
unordered_map : 정렬이 안됨 / 해시테이블 기반 / 탐색, 삽입, 삭제에 평균적으로 O(1), 가장 최악의 경우
O(N)
얼핏보면 정렬이 필요로 하지 않은 문제에는 unordered_map을 써야 할 것같지만 제출해보면 시간초과가
나기도 합니다. 이는 가장 최악의 경우 O(N)이기 때문임. 되도록 map을 쓰는 것을 권장함

 

 

 

 

unordered_map 활용 코드

---

#include<bits/stdc++.h>
using namespace std;

int main()
{
	unordered_map<string, int> umap;
	
	//==== 값 삽입 
	umap.insert({"test1", 1});
	umap.emplace("test5", 5);
	// 이걸 권장 
	umap["test1"] = 4;
	
	
	for(auto element : umap)
		cout << element.first << " :: " << element.second << "\n";
		
	
	// ==== 값 찾기 
	auto search = umap.find("test4");
	if(search != umap.end())
		cout << "found" << search->first << "" << (*search).second << "\n";
	else
		cout << "Not found" << "\n";
	
	// ==== 이런식으로 int를 증가가능하다. 
	umap["test1"]++;
	cout << umap["test1"] << endl;
	
	// ==== 크기
	cout << umap.size() << "\n";
	umap.erase("test1"); // 특정 값 지우기
	cout << umap.size() << "\n";
	
	return 0; 
}