std :: map의 기본 구조는 무엇입니까?

Question

어제 누군가가 주문한지도의 기본 구조가 이진 검색 트리라는 것을 나에게 이야기했습니다. O (1) 검색을 수행 할 수 없기 때문에 이것은 나에게 이해가되지 않습니다. 아무도 설명 할 수 있을까요?

또한 stdlib을 사용하지 않고 C++로 해시 테이블을 구현하는 경우 가장 좋은 방법은 무엇입니까?

Answer 1

1. 기본 데이터 구조는 구현에 따라 정의됩니다. 가장 일반적으로 자체 균형 조정 이진 검색 트리 인 Red-Black 트리로 구현됩니다. 요소를 가져 오는 데 드는 시간 복잡도는 O (logn)입니다 (this 참조)

2. 나는 std::unordered_map의 구현을 시작으로 읽을 것입니다. 나는 이것이 학습 활동이라고 가정하고 작업 STL 구현을 읽고 이해하는 것이 좋은 운동이 될 것입니다. 운동이 아닌 경우 std::unordered_map

Answer 2

std :: map은 노드 삽입/삭제 및 검색의 복잡성 사이에서 적절한 균형을 유지하므로 Red-Black 트리를 사용합니다.

Answer 3

std :: map 조회 시간이 O (1) O (log (n))가 아닙니다.

std :: unordered_map에는 O (1)의 조회 시간이 상각됩니다.

std :: unordered_map 및 std :: unordered_set은 해시 테이블입니다.