[자료구조] std::map & std::unordered_map 개념

std::map은?

- 순서가 지정된 연관 컨테이너

- 항목을 삭제하는 경우를 제외하고 반복자와 참조가 절대 무효화 되지않는다.

- 반복자는 항목을 정렬한 순서나 역순으로 정렬한 순서로 생성

- 노드기반 자료구조. 하지만 키의 값에 따라 노드를 자동으로 정렬

- 내부는 균형 이진트리로 구현

- 트리를 사용하지만 트리는 아니다.

- 메모리 관리자와 매우 간단하고 예측 가능한 방법으로 상호작용

- 각 항목에 할당된 저장 공간의 크기는 모두 같음.(메모리 단편화 생길 가능성 낮음)

- 검색은 std::vector로 std::lower_bound 사용하는게 더 빠름

 

사용 방법 : 

https://blockdmask.tistory.com/87

[C++] map container 정리 및 사용법

 

 

 

std::unorder_map은?

 

- 순서가 지정된 연관 컨테이너

- std::map과 유사하지만 매핑을 수행하는 방법이 다름. std::unorder_map은 해시테이블로 구현.

(평균적으로 상수시간에 값을 검색하기 위해 키를 정수해시로 변환한뒤, 배열의 색인으로 사용)

- 생성에 비용이 많이 든다. 각 테이블 항목에 동적으로 할당된 노드와 동적으로 크기를 조정할 수 있는 버킷배열을 포함하기때문(버킷배열은 테이블의 크기가 커지면서 주기적으로 재할당) 따라서 검색 성능을 향상하기 위해 메모리를 상당이 많이 소비.

- 순서가 지정되지 않은 맵에 있는 항목의 개수를 크기(size)라고 하고, 크기를 버킷의 개수로 나눈 값을 로드팩터(load factor)라고 한다.

로드팩터가 1.0보다 크면 일부 버킷에 여러 항목 체인이 있어 해당 키의 검색성능 저하. 즉 해시가 완전하지 않다.

 

- map과의 차이로는 바로 삽입되면 정렬되지 않는다.

- std::unorder_map이 존재하는 이유는 바로 검색떄문이다. 맵과 벡터로 std::lower_bound를 사용해 검색하는 것에 비해, 훨씬 빠르다.

- 단점으로는 저장 공간의 크기이다. 저장공간이 제약된다면 std::vector가 낫고, 그게 아니라면 std::unorder_map이 성능면에서 유리하다.

 

unorder_map 사용법

https://math-coding.tistory.com/31

[Data Structure] unordered_map 사용법