C++ 'map' vs 'unordered

Efficient Coding/C++

ehdbs0903 2024. 8. 22. 17:43

C++에서 map과 unordered_map는 둘 다 키-값 쌍을 저장하는 연관 컨테이너로, 유사한 기능을 제공하지만 내부 구현 및 성능 특성에서 큰 차이가 있다. 각각의 차이점을 아래와 같이 비교할 수 있다.

1. map:

구조: Red-Black 트리와 같은 이진 탐색 트리로 구현된다.
원소 순서: 키를 기준으로 정렬된 상태로 원소들이 저장된다.
탐색, 삽입, 삭제 속도: 평균적으로 O(log n)의 시간 복잡도.
메모리 사용량: 트리 구조를 유지하기 위해 각 노드가 추가적인 포인터(부모, 자식)를 포함하므로 메모리 사용량이 많을 수 있다.
키의 비교: 기본적으로 operator< 연산자를 사용하여 키를 비교한다. 사용자 정의 키 타입의 경우 operator<를 오버로드해야 한다.
범위 기반 함수 지원: lower_bound, upper_bound, equal_range와 같은 함수들을 제공하여 특정 범위 내에서 원소를 쉽게 검색할 수 있다.
안정성: 항상 키가 정렬된 상태로 유지되므로, 삽입과 삭제 후에도 반복자의 유효성을 보장한다.

2. unordered_map:

구조: 해시 테이블로 구현된다.
원소 순서: 원소들이 해시 값에 따라 버킷에 저장되며, 순서는 일정하지 않다.
탐색, 삽입, 삭제 속도: 평균적으로 O(1)의 상수 시간 복잡도. 그러나 해시 충돌이 많을 경우 최악의 경우 O(n)이 될 수 있다.
메모리 사용량: 해시 테이블의 버킷을 유지하기 위한 추가 메모리를 사용한다. 사용 중인 해시 함수와 충돌 처리 방식에 따라 메모리 사용량이 달라질 수 있다.
키의 비교 및 해싱: 기본적으로 operator==와 해시 함수(std::hash)를 사용하여 키를 비교하고 해싱한다. 사용자 정의 키 타입의 경우 operator==와 std::hash를 오버로드해야 한다.
범위 기반 함수 미지원: lower_bound, upper_bound, equal_range와 같은 함수들은 제공되지 않는다. 해시 테이블의 특성상 순서 기반의 검색이 불가능하다.
안정성: 키의 순서를 보장하지 않으며, 삽입과 삭제 후에 버킷 리해싱이 발생할 경우 반복자가 무효화될 수 있다.