빠른 데이타 검색을 지원하는 자료구조가 필요할 경우 많은 경우 연관 컨테이너를 사용한다. (물론 비표준의 해쉬컨테이너가 더 빠를것이다.)
하지만 vector를 정렬되어 있다고 가정할 경우 대부분의 검색 속도에서 vector가 더욱 빠른 검색 속도를 보여준다. 연관 컨테이너는 전형적으로 이진 탐색 트리로 구현되어 있다. 이 트리는 테이터 노드의 삽입, 삭제, 탐색이 임의대로 아무 때나 이루어지는 상황에 적합하도록 구현된 자료구조 이다. 하지만 많은 상황에서 그런 복잡한 구조를 가지지는 않을 것이다.
- 데이터 셋업, 생성
- 데이터 탐색
- 데이터 재구성
정렬된 vector가 연관 컨테이너보다 유리한 점은 간단하게 2가지 정도를 생각할수 있다.
- 하나의 데이터당 사용하는 메모리의 크기
연관 컨테이너의 경우 노드가 포인터로 연결된 구조를 사용하기 때문에 포인터 만큼의 메모리를 더 사용한다. (최소 포인터 3개)
- 메모리 참조위치의 근접성
vector 같은 연속 메모리 구조를 취하는 데이터구조는 논리적으로 인접해 있는 데이터가 물리적으로도 인접해 있게 되기 때문에 메모리 접근에 지역성에 따른 속도 계산을 생각할수 있다.
이후 자세한 내용은 생략한다. pair 객체를 넣고 비교함수를 어쩌구 저쩌구 하는 방법은 책을 참조하던지 나중에 적어 넣던지~