map과 unordered_map 비교

C++에서 키-값 쌍으로 데이터를 관리하는 자료구조는 특이하게 map과 unordered_map 두 가지가 있다.
이 두 컨테이너는 얼핏 봐서는 비슷해 보이지만, 내부 구현 방식이나 성능 측면에서 간과할 수 없는 차이점이 존재한다.

map과 unordered_map의 차이점과 사용 사례, 성능을 비교해보며 자신의 프로젝트에 어느 자료구조를 쓰는 것이 더욱 적합한지 판단할 수 있도록 해보자.

std::map

map은 내부적으로 균형 이진 검색 트리(BST)를 사용해 데이터를 저장한다.
이로 인해 키는 항상 정렬된 상태로 저장되어 요소에 대한 삽입/삭제/검색에 O(log n)의 시간복잡도를 가진다. 추가적인 트리 구조로 인하여 메모리 사용률 또한 높다.

 

map은 보통 키의 정렬이 필요할 때, 범위 기반의 검색이 자주 발생할 때 그리고 삽입/삭제/검색 시간이 일정하게 유지되어야 할 때 사용하기에 적합하다.

std::unordered_map

unordered_map은 해시 테이블을 기반으로 데이터를 저장하는 컨테이너이다.
map과의 차이점은 키에 대한 순서가 정해져있지 않다는 것이다. 그럼으로 인해 요소 삽입/삭제/검색에 평균적으로 O(1)의 시간복잡도를 가진다. 해시 테이블로 인해 메모리 사용률도 더 낮을 수 있다.

 

unordered_map은 키의 순서가 중요하지 않을 때, 빠른 검색이 필요할 때 그리고 메모리의 효율성이 중요시 되는 경우에 사용하면 좋다.

map과 unordered_map의 연산

내부적인 로직은 상당히 다르지만, 개발자들이 다뤄야하는 사용법은 동일하다.
연산 코드를 함께 보며 map과 unordered_map을 잘 다룰 수 있도록 해보자.

 

생성

#include <map>
map<int, std::string> myMap;

#include <unordered_map>
unordered_map<int, std::string> myMap;

<map> 헤더 파일을 참조하여 map을 사용할 수 있고,

unordered_map 헤더 파일을 참조해 unordered_map을 사용할 수 있다.

 

꺽쇠(<>) 내에 키로 사용할 값의 자료형과 값으로 사용할 값의 자료형을 쉼표로 구분해 선언해준다.

 

요소 추가

myMap[1] = "One";
myMap.insert({2, "Two"});
myMap[1] = "Three";
myMap.insert({2, "Four"});

cout << myMap[1] << endl; //Three
cout << myMap[2] << endl; //Two

 

대괄호([])를 사용해 삽입하는 방법과 insert() 함수를 통해 삽입하는 방법이 있다.
둘의 차이점은 중복된 키가 존재할 때, 대괄호는 해당 키의 값을 업데이트 하고, insert()는 중복 키의 값이 무시된다.

 

요소 조회

cout << myMap[3] << endl; //(non-pointer)
cout << myMap.at(3) << endl; //std::out_of_range

auto it = myMap.find(1);
cout << it.first << endl; //1
cout << it.second << endl; //Three

 

삽입된 요소를 조회할 때도 마찬가지로 대괄호([])를 사용하는 방법이 존재하고, at()함수를 사용하는 방법이 있다. Pair 자료구조와 비슷하게 키는 first 로, 값은 second로 구분해준다.
둘의 차이점은 키가 존재하지 않을 때, 대괄호는 해당 키에 기본 값을 쌍으로 하여 새로 삽입하는 반면, at()은 std::out_of_range 예외를 발생시킨다.

 

키의 존재 여부를 찾기 위해서는 find() 함수를 사용한다. 해당 키가 있는 이터레이터를 반환하고, 존재하지 않을 시 end()를 반환해준다.

 

요소 삭제

myMap.erase(2); //키가 2인 요소 제거
myMap.clear(); //모든 요소 제거

요소를 삭제하고 싶다면 erase() 함수 내에 전달 인자로 삭제하고 싶은 키를 넣으면 된다.
만약 요소를 모두 비우고 싶다면 clear() 함수를 통해 비워줄 수 있다.