<unordered_map> 자료구조

<map> 자료구조

---

<map> 자료구조랑은 조금의 차이가 있는 자료구조이다. 

<map> 같은 경우에는 이진 트리로 되어 있기 때문에 어떠한 값을 찾기 위해서는 log(n) 의 시간 복잡도를 갖게 된다.

하지만, <unoredred_map> 같은 경우에는 해쉬테이블로 구현한 자료구조로 탐색 시간 복잡도는 O(1) 이다.

 

<unordered_map>을 사용하기 위해서는 #include< unordered_map> 을 선언해야한다. 

 

주의해야 할 점은, key가 유사한 데이터가 많을 시 해시 충돌로 인해 성능이 떨어질 수도 있다. 

그렇기 때문에 key 값이 다르면서 해당 key값을 갖는 원소의 갯수를 탐색 할 때 사용하면 빠른 시간내에 찾을 수 있다.

 

 

find(key) : 맵에서 해당하는 key값을 갖는 원소가 있는지 확인한다.

operator [] : key를 통해 value 를 지정한다. 코드를 확인해보면 어떻게 쓰이는지 안다. 

size() : 맵의 크기를 확인한다. 

empty() : 맵이 비어있는지 확인한다.

insert({key,value}) : key값과 value값을 한번에 삽입한다. 

erase(key) : key 해당하는 원소를 제거한다. 

celar() : 맵 초기화 

 

참고로 인덱스로 접근할 수 없고 iterator로 접근하여 다음과 같이 출력한다. 

#include <iostream>
#include <unordered_map>
using namespace std; 
int main() {
	unordered_map <int, int> m;
	for (int i = 0; i < 3; i++) {
		m[i]++; 
	}
	for (auto x : m) {
		cout << x.first << " " << x.second << endl; 
	}
	cout << endl; 
	m[1] = 2; 
	for (auto x : m) {
		cout << x.first << " " << x.second << endl;
	}cout << endl; 
	cout << m[3] << endl; 
}

 

 

unordered_map 을 활용한 문제

 

11723번: 집합

#include <iostream>
#include <unordered_map>
#include <string>
#include <algorithm>
using namespace std; 
unordered_map <int, int> m; 

int main() {
	ios::sync_with_stdio(false); 
	cin.tie(0); 
	cout.tie(0); 
	int n; cin >> n; 
	for (int i = 0; i < n; i++) {
		string s;	int x;	cin >> s;
		if (s != "all" && s != "empty") {
			cin >> x; 
		}
		if (s == "add") {
			m[x]++; 
		}
		else if (s == "remove") {
			m.erase(x);
		}
		else if (s == "check") {
			if (m[x] > 0)cout << 1 << "\n";
			else cout << 0 << "\n"; 
		}
		else if (s == "toggle") {
			if (m[x] > 0) {
				m.erase(x); 
			}
			else {
				m[x]++; 
			}
		}
		else if (s == "all") {			
			for (int j = 1; j <= 20; j++) {
				m[j]=1;
			}
		}
		else if(s=="empty"){
			m.clear(); 
		}
	}
}