위의 답변은 트리 대안 만 다루고 빨간색은 아마도 역사적인 이유로 남아있을 것입니다.

왜 해시 테이블이 아닌가?

유형은 <연산자 (비교) 만 트리의 키로 사용해야합니다. 그러나 해시 테이블에는 각 키 유형에 hash함수가 정의 되어 있어야합니다 . 일반적인 프로그래밍에서는 유형 요구 사항을 최소로 유지하는 것이 매우 중요하므로 다양한 유형 및 알고리즘과 함께 사용할 수 있습니다.

좋은 해시 테이블을 디자인하려면 사용될 컨텍스트에 대한 친밀한 지식이 필요합니다. 개방형 주소 지정 또는 연결된 체인을 사용해야합니까? 크기를 조정하기 전에 어떤 수준의 부하를 수용해야합니까? 충돌을 피하는 고가의 해시 또는 거칠고 빠른 해시를 사용해야합니까?

STL은 애플리케이션에 가장 적합한 선택을 예상 할 수 없으므로 기본값이 더 유연해야합니다. 나무는 “그냥 작동”하고 잘 확장됩니다.

(C ++ 11은을 사용하여 해시 테이블을 추가했습니다 unordered_map. 설명서 에서 이러한 많은 옵션을 구성하기 위해 정책을 설정해야한다는 것을 알 수 있습니다.)

다른 나무는 어떻습니까?

레드 블랙 트리는 BST와 달리 빠른 조회를 제공하고 자체 균형을 유지합니다. 다른 사용자는 자체 균형 AVL 트리보다 장점을 지적했습니다.

Alexander Stepanov (STL의 창시자)는 std::map다시 쓰면 레드-블랙 트리 대신 B * 트리를 사용할 것이라고 말했다 . 현대 메모리 캐시에 더 친숙하기 때문이다.

그 이후로 가장 큰 변화 중 하나는 캐시의 성장이었습니다. 캐시 미스는 비용이 많이 들기 때문에 참조의 지역성이 훨씬 중요합니다. 참조 지역성이 낮은 노드 기반 데이터 구조는 훨씬 덜 이해됩니다. 오늘 STL을 디자인하고 있다면 다른 컨테이너 세트가있을 것입니다. 예를 들어, 인 메모리 B *-트리는 연관 컨테이너를 구현하기 위해 레드-블랙 트리보다 훨씬 낫습니다. – 알렉산더 스테파노 프

지도는 항상 나무를 사용해야합니까?

또 다른 가능한 맵 구현은 정렬 된 벡터 (삽입 정렬) 및 이진 검색입니다. 이것은 자주 수정되지는 않지만 자주 쿼리되는 컨테이너에는 효과적입니다. 나는 종종 C에서이 작업을 수행 qsort하고 bsearch내장되어 있습니다.

지도를 사용해야합니까?

캐시 고려 사항은 학교에서 배운 상황 (예 : 목록의 중간에서 요소를 제거하는 경우)에 사용 std::list하거나 그 std::deque이상 사용하는 것이 거의 의미가 없음을 의미합니다 std:vector. 동일한 추론을 적용하면서 for 루프를 사용하여 목록을 선형 검색하는 것이 몇 가지 조회를 위해 맵을 작성하는 것보다 더 효율적이고 깔끔합니다.

물론 읽기 가능한 컨테이너를 선택하는 것이 일반적으로 성능보다 중요합니다.

답변