맵과 정렬된 벡터 : 어느 것이 더 나은가?

STL의 연관 컨테이너와 시퀀스 컨테이너는 몇 가지 중요한 차이점이 있다. 가장 중요한 것은, 메모리의 연속성이다. 벡터와 같은 시퀀스 컨테이너는 켄테이너 요소들의 인접성을 보장하지만, 연관 컨테이너는 이것을 보장하지 않는다는 점이다. 그러나, 연관 컨테이너는 언제라도 평균 이상의 컨테이너 요소들의 삽입, 삭제, 검색을 보장해주는, 중요한 특징을 가지고 있다.

흔히 이야기하는, '맵을 사용하는 것보다 정렬된 벡터를 사용하는 것이 낫다'라는 이야기는, 이 메모리의 연속성 여부와 관련있다. 즉, 맵은 하나의 노드를 생성하는데 메모리가 연속된 형태가 아니기 때문에 나름대로의 메모리 할당 비용이 발생하며, 벡터보다 약간 비싼 오버헤드가 존재한다. 노드 하나를 추가하는데 추가적인 메모리 할당 비용이 들어가는 것은 맵이나 벡터나 어쩔 수 없지만, 최소한 컨테이너의 끝에 원소를 추가하는 경우, 맵은 벡터에 비할 바가 못된다. 특히, 컨테이너 요소의 삽입이 드물게 일어나며 검색이 자주 필요한 구조라면, 정렬된 벡터를 사용하는 것이 훨씬 유리하다. 처음부터 필요한 대략적인 벡터의 크기를 잡아두고, 드물게 일어나는 삽입이 발생할 때 이 요소들을 정렬하고, 검색에는 이진 탐색을 적용하는 것이 맵을 사용하는 것보다 메모리 사용량이나 검색 속도나 훨씬 이득이 크다는 뜻이다. 그리고, 이 이야기는 대부분의 경우 맞는 이야기다.

그러나, 이것은 다음과 같은 부분을 고려해야 완전히 맞는 이야기가 된다.

첫째, 삽입이 확실히 매우 드물게 일어나야 하며, 그렇지 않다면 벡터의 시퀀스 컨테이너 특성 때문에 정렬 과정에서 막대한 비용이 소모될 수 있다. 맵이 삽입, 삭제와 같은 동작에 대해 언제나 평균적인 성능을 보장해주는 것을 고려한다면, 이와 같은 동작이 불규칙적으로 자주 일어나는 경우, 벡터 대신 맵을 사용하는게 낫다.

둘째, 이진 탐색 알고리즘을 잘 작성해야 한다. 이진 탐색 알고리즘은 워낙 간단해서 더 잘 작성할 여지가 없어 보이지만, 손수 만드는 이진 탐색 알고리즘 구현이 최소한 STL의 알고리즘과 성능면에서 비슷하거나 더 나아야 한다. STL의 binary_search는 컨테이너 안에 원하는 요소가 있는지 없는지 여부만 알려주기 때문에, 정렬된 벡터를 맵 대신 사용하기로 했다면 필수적으로 이진 탐색 알고리즘을 작성해야 한다.


언제나 그렇듯이 모든 상황에 맞는 절대적인 답은 없으며, 경우에 따라 맵을 사용하는 것이 유리할지, 정렬된 벡터와 이진 탐색 조합을 사용하는게 유리할지 판단할 수 밖에 없다.