맵과 정렬된 벡터 : 어느 것이 더 나은가?
STL의 연관 컨테이너와 시퀀스 컨테이너는 몇 가지 중요한 차이점이 있다. 가장 중요한 것은, 메모리의 연속성이다. 벡터와 같은 시퀀스 컨테이너는 켄테이너 요소들의 인접성을 보장하지만, 연관 컨테이너는 이것을 보장하지 않는다는 점이다. 그러나, 연관 컨테이너는 언제라도 평균 이상의 컨테이너 요소들의 삽입, 삭제, 검색을 보장해주는, 중요한 특징을 가지고 있다. 흔히 이야기하는, '맵을 사용하는 것보다 정렬된 벡터를 사용하는 것이 낫다'라는 이야기는, 이 메모리의 연속성 여부와 관련있다. 즉, 맵은 하나의 노드를 생성하는데 메모리가 연속된 형태가 아니기 때문에 나름대로의 메모리 할당 비용이 발생하며, 벡터보다 약간 비싼 오버헤드가 존재한다. 노드 하나를 추가하는데 추가적인 메모리 할당 비용이 들어가는 것은..
더보기