[C++] unordered_map 라이브러리

일반적인 map과 다른 라이브러리이다.

주로 삽입과 검색이 많이 이루어지는 경우에 사용하면 효과적인 라이브러리이다.

우선 해시맵에 대한 개념 이해가 필요하다.

 

map같은 경우는 key와 value를 동시에 저장을 한다. key를 가지고 저장될 위치를 정하고 그 위치에 값을 저장하게 된다.

key를 가지고 저장될 위치를 정하는 것을 hashing이라고 한다. 

요약해서 설명을 하자면 해시맵을 생성하는 동시에 저장할 값의 위치를 결정해 줄 해싱 함수와, 저장이 될 공간을 한번에 생성한다. 

이것을 그림으로 보면 다음과 같다.

이제 대충 hash라는 개념이 잡혀있을 것이라 생각한다.

여기에서 한가지 의문이 든다. 지금 그림을 보면 저장 공간이 저렇게 나와있다. hashing으로 인해 들어가는 저장 공간의 위치가 동일한 경우는 어떻게 할까?

이러한 경우를 충돌이라 표현한다. 충돌이 많은 경우 저장공간에서 chaing기법으로 리스트로 연결하여 저장해준다. 그러니까 지금 위의 그림을 보면 hashing을 통해 저장할 저장 공간을 지정이 될 것이다. 하지만, 이미 해당 칸에 다른 {key, value}가 있다고 하자. 그러면 이 {key, value}값이 다음 노드를 가리키는 것을 만들어 hashing으로 지정된 그{key, value}를 연결해주는 것이다. 저장 공간을 살짝 줄여주는 역할을 한다. 하지만, 충돌이 많아질 경우 O(1)이 되지 않을 수 있다. 그렇기 때문에 해시맵을 사용할 떄, 충돌이 적게 일어나야 좋다.

 

이제 해시맵에 대한 개념은 알게 되었다. 이제 함수를 사용하는 방법에 대해 알아보자.

라이브러리

 - #include <unordered_map>

 

네임스페이스

- std

 

선언

- unordered_map<TYPE, TYPE> var;

즉, - unordered_map<타입이름, 타입이름> 변수명;

std::unordered_map<int, int> m;

만약 여기에서 map을 내림차순으로 하고 싶다면 algorithm 라이브러리를 추가해 준 뒤, 다음처럼 해줘야 한다.

std::map<int, int, greater<int>> m

 

기본 함수

m. insert({k, v}) - 원소 키 값이 k, 값이 v인 pair형 삽입 

m. find(k) - k가 위치해 있는 iterator 반환 / 없다면 m.end()반환

m.begin()	m위 가장 첫 원소의 위치 (iter)반환
m.end()	m의 가장 끝 원소의 위치 + 1 (iter)반환
m. insert({k, v})	원소 k 삽입
m. count(k)	원소 k의 개수 반환 -> 중복 허용 X이므로 있으면 1, 없으면 0 반환
m.erase(k)	원소 k 삭제
m.erase(k)	iterator k위치 삭제
m.erase(k, l)	iterator k ~ iterator l위치 삭제

추가적으로 팁을 말하자면, 이 자료구조는 파이썬의 dict와 비슷하게 사용할 수 있다. 그러니까 m.insert({k, v})를 m[k] = v로 쉽게 접근이 가능하다는 것이다. k요소에 저장되어 있는 v의 값을 알려고 할 때에도 m[k]로 쉽게 접근이 된다.