항목 23 : 연관 컨테이너 대신에 정렬된 vector를 쓰는 것이 좋을 때가 있다.

"좋을 때가 있다" 이런 문구가 들어가면, 조금 복잡해 지는 경향이 없지 않아 있다. 왜냐하면, 경우에 따라서 달라지는 상황에 대해서 판단을 내려야 하기 때문이다. 제목을 다시 정리하지만 "연관 컨테이너(Associative Containers)보다 연속 컨테이너(Sequence Containers)의 vector가 더 좋다는 이야기가 아니라, ... vector가 더 좋을 수도 있다"는 이야기로 이번 항목은 시작 되었다.


연관 컨테이너(Associative Containers)는 탐색에 특화된 컨테이너라 할 수 있는데, 이 탐색이란 것은 "C 배우는 알고리즘"에서 나와 있는 비슷한 방법으로 행해지게 된다. 구체적인 내용은 정리 글의 범주에서 벗어 나므로 생략하고, 구글에서 "균형 이진 트리" 라고 구글링(?) 하면 자세히 나온다.

이 표준 연관 컨테이너들(Associative Containers)은 "균형 이진 탐색 트리(balanced binary search tree)"를 사용 한다. 이 트리는 삭제, 삽입, 탐색이 아무 때나 이루어져도 균형적인 성능을 보이도록 만들어 졌다.

그러면 정렬된 vector가 더 빠를 수 있다는 낚시 제목!?
은 아니고, 만약 "데이터를 미리 다 밀어 넣고,  데이터를 탐색한다" 방식으로 연관 컨테이너(Associative Containers)를 사용 한다면, 정렬된 vector가 더 빠르다는 이야기 이다.


왜냐하면 이 연관 컨테이너(Associative Containers)는 메모리 참조 위치의 근접성(locality of reference)이 보장 되지 않기 때문이다.

이것은 연관 컨테이너(Associative Containers)에 사용된 메모리가 많아지면서 메모리 페이지 오류(page fault)가 증가됨에 따라 탐색, 삽입, 삭제 시간이 오래 걸린다.(여기서 말한 page fault에 대해서는 별도로 링크를 제공한다)

왜 많은 메모리를 사용 하느냐?
연관 컨테이너(Associative Containers)는 자신에게 데이터를 밀어 넣으면, 그 데이터와 함께 3개의 포인터가 생성 되면서 "균형 이진 탐색 트리 구조"를 갖추게 된다. 즉 원소 한개당 메모리 오버헤드를 지불해야 한다.
vector는 미리 메모리 공간을 확보하여, 그 공간에만 사용 하기 때문에, 초기 vector 생성시 들어 가는 메모리 오버헤드만 지불하면 되는 차이를 보인다.

즉, 연관 컨테이너(Associative Containers)는 정렬된 vector 보다 page fault가 더 많이 발생 하여, 느릴 수 있다는 점을 지적한다.

그렇다면 vector만 써도 되는게 아닌가?
제목에서도 말했듯이 더 좋을수 있다는 가능성을 생각하라는거지, 무조건 좋다는 이야기가 아니였다. vector 같은 경우, 탐색 전에 반드시 정렬시키는 비용을 지불해야 한다. 여기에 데이터의 삽입과 삭제가 합처지면 이 비용도 결코 만만치 않다.

위에서 말한 vector의 비용은 vector에 많은 량의 데이터를 삽입한 후 정렬 시키거나, 앞쪽의 데이터를 삭제 할때 정말 큰 비용을 내게 되는데, 상대편에게 피박에 광박 먹이고 3고 한 찰나에, 홍단으로 무너저 독박 당해 내는 비용과 별 반 차이가 없다.

여기서 말했던 가능성이란,  "데이터를 미리 다 밀어 넣고,  데이터를 탐색한다" 방식 으로 사용한다면~ 정렬된 벡터가 더 빠를 가능성이 있다는 것이다.



자~ vector을 연관 컨테이너(Associative Containers) 처럼 어떻게 사용 할수 있을까?
이렇게 사용자가 조작하게 된다는것은 많은 변위 가능성이 높다는 것을 뜻하여,템플릿 클래스로 구성해 두어 캡슐화 하여, 유지보수가 용이해야 될 것이라고 판단한다.

// 이건 클래스 설계
1. 클래스로 만든다.
2. 멤버 객체로 vector를 갖는다(객체 합성으로 상속 형태를 취한다)


// 내부 설계
1. 벡터는 pair 객체를 이용하여 담고 first가 key 역활을 한다.
2. pair 객체의 first를 이용항 동등성 비교 객체 함수를 만든다.
3. pair 객체의 first와 원하는 데이터와의 상등성 비교 객체 함수를 만든다.
4. 값을 다 넣었다면 정렬한다.
5. 정렬된 데이터를 탐색한다.
6. 삽입과 삭제가 있다면, 탐색 전 정렬을 시켜야 한다.

어디까지나 이것의 전제 조건은, ... 데이터 삽입이 다 끝난후 데이터의 변동이 없고, 탐색만 한다면 vector가 더 좋다는 이야기이다!

게임에선 변동폭이 적은 리소스 관리를 위한 컨테이너로 쓰면 좋을듯 싶다. 한번 말어 봐야지~

관련링크
http://set2happy.tistory.com/260 <-- page fault
http://ilu8318.egloos.com/848106 <-- 탐색 알고리즘

나머지는 검색어 "정렬된 벡터" 식으로 검색하면 많이 나오므로 생략하고 이번 항목 정리를 끝마친다.