[effective STL] 항목 23 : 연관 컨테이너 대신 정렬된 벡터를 쓰는 것이 좋을 때도 있다.

일반적으로 빠른 데이터 검색을 지원하는 자료구조가 필요하면?

바로 떠오르는 것은 연관 컨테이너다.

표준 연관 컨테이너는 전형적으로 균형 이진 탐색 트리로 되어있다.

삽입, 삭제, 탐색이 아무 때나 이루어질 때 유리한 구조.

But, 많은 프로그램들이 실제로 이런 극단적으로 혼란스러운 구조를 가지지 않는다.

대개 프로그램에서 자료구조를 사용하는 3단계

1. Setup : 자로 구조를 만든다. 데이터 삽입과 삭제가 대부분이며 탐색은 거의 일어나지 않는다.

2. Lookup : 셋업이 끝난 자료 구조 중 원하는 정보를 찾는다.

3. Reorganize : 자료 구조의 내용물을 바꾼다. 1과 비슷한 일을 하며 작업이 끝나면 2로 진입한다.

이러한 프로그램이라면 벡터가 연관 컨테이너보다 훨씬 나은 수행성능을 제공할 가능성이 높다.

이유 1. 진부하지만 메모리 크기.

이유 2. 메모리 참조 위치의 근접성(locality of reference).

제약. 정렬된 데이터이어야 한다. binary_search, lower_bound, equal_range 등의 탐색 알고리즘을 제대로 적용할 수 있어서.

Widget 예시

widget 객체를  컨테이너를 담는다면 역시 탐색 속도가 꽤 중요하다.

연관 컨테이너냐 정렬된 벡터를 사용할 것이냐 고민하게 된다.

균형 이진 탐색 트리는 Left, Right 자식 노드 포인터와 대개 Parent 노드의 포인터를 가진다.

한 마디로 연관 컨테이너에 Widget 하나를 저장하는데 세 개의 포인터를 담는 메모리가 오버헤드로 걸린다.

widget 객체의 크기 : 12byte

시스템 : 한 pgage 4K, 포인터 4byte

백터의 경우 341개의 widget 객체를 담을 수 있다.

연관 컨테이너의 경우 170개 정도의 widget 객체를 담을 수 있다. 2배의 차이.

사용 메모리가 많아지면 page fault도 그만큼 많아진다.

가까운 노드 사이에도 물리적으로 가깝다는 보장이 없다.

이진 탐색 시의 page fault를 최소화하려면 가까운 노드들은 인접한 물리 메모리에 저장되도록 구조를 만드는 것이 정석이다.

일단 여기까지.. pair<K, V>를 인자로 가지는 벡터를 만드는 방법인데..

활용할 일이 있을지 잘 모르겠다. 

항상 정렬된 상태여야 한다는 운명적인 단점과 맵을 흉내내서 만들기 때문에 사이드 이펙트도 꽤 생길 것 같다.

다음에 필요할 때 사용해 보는 것으로.