[C++] map, set, hash_map (연관 컨테이너)

와 방금 알고리즘문제를 풀다가 모르는 부분이 있어서 아는 선배한테 물어봤는데 너무 신기한 알고리즘아닌 알고리즘을 들었다. 그 문제를 풀기위해 필요한게 c++에서는 해시맵이라고 친절히 알려주셔서 오늘은 해시맵 관련 컨테이너들을 공부하도록 하겠다! 

(이 글을 써둔게 2018.5.17 였는데 이어서 추가 및 수정한다.)

해시맵은 연관 컨테이너 중 하나이다. 예를 들어 vector나 list와 같은 컨테이너는 순서에 따라 값을 저장하지만 연관 컨테이너는 어떠한 key와 짝을 이루어서 값을 저장한다. 따라서 값을 넣고, 찾을 때에는 key가 필요하다! 대량의 자료를 저장하고 빠르게 검색하기 위해 사용된다고 한다. hash table을 만들어두면 O(1)로 검색을 할 수 있듯이 비슷한 것같다.(아니 그 개념을 적용한 컨테이너인가보다.)

연관컨테이너의 종류에는 map, set, hash_map, hash_set이 있다. 중복되는 key값을 사용할 경우에는 앞에 'multi'를 붙여서 multi_map과 같이 사용한다. map과 set은 이진 탐색 트리로 구현이 되어 있어서 key값을 통해 value를 넣거나 삭제하거나 찾고자 할 때 O(logn)이 보장된다! 그리고 원하는 정렬기준에 따라 value를 정렬하여 보관할 수 있다. hash_map 는 map보다 더 빠른 탐색속도를 보여서 O(1)이다! 그렇지만 STL 표준이 아니라고 한다. (hash_map은 value를 정렬하지 않고 탐색 성능이 안정적이지 못하다고 한다.)

유용하게 사용할 수 있는 것 같은 map을 먼저 정리 해보겠다.

map<key 타입, value 타입, (정렬조건)> 변수명; 와 같이 선언한다.

value는 저장할 데이터, key는 value를 가리킬 데이터이다. 세번째인자인 정렬조건은 필요할 때 우선순위 큐에서 사용하듯이 넣어주면 된다.

ex) map<int, int> m;

map에 값을 넣고 싶을 때는 m[key값] = value값 을 해주면되고 만약 해당하는 key값이 있을 경우 value를 갱신시켜준다.(key는 고유한 값이기때문에 중복되지 않는다.) insert를 통해서 넣을 수도 있는데 key, value쌍을 넣어줘야하므로 pair 객체로 m.insert(make_pair(key값, value)); 해주면 된다. 인덱스가 key값이기 때문에 순차적으로 접근할 때는 iterator를 통해서 해야한다. 대부분의 컨테이너들의 내부 함수와 비슷하게 동작하므로 필요한 함수들만 잘 사용해주면 된다!

ex) map<int, int>::iterator iter = m.begin(); iter->first와 같이 접근하거나 (*iter).first 와 같이 접근할 수 있다.

다른 연관 컨테이너들도 사용해볼 때 추가적으로 정리를 해봐야겠다.