C++ 맵이 시도로 구현되지 않는 이유는 무엇입니까?

Question

시도는 매우 빠른 데이터 구조입니다. 단어를 찾으려면 O (sizeofword) 시간이 걸리며, std::map은 자체 균형이 잡힌 나무입니다. 표준 C++ 맵 템플릿이 구현되지 않는 이유는 무엇입니까? 특별한 이유가 있습니까? 자체 균형 트리가 아닌 트라이를 사용하면 어떤 상반 관계가 있습니까?

Answer 1

Tries은 저장할 키를 숫자 단위 또는 문자 단위로 처리 할 수있는 경우에만 사용할 수 있습니다. C++ std::map 및 std::set은 키와 비슷한 요소와 함께 작동하도록 설계되었으므로 문자를 문자별로 처리하는 방식으로 구현할 수 없습니다. 그들은 대신 (일반적으로) 키에 대해 인트로 필 할 필요가없고 비교기를 사용하여 빠른 조회를 수행 할 수있는 균형 이진 검색 트리를 사용합니다.

특정 속성이 키를 보유하고 있다는 것을 알고 있다면 경우에 따라 시도보다 더 잘 수행 할 수 있습니다 (예제는 van Emde Boas tree 참조). 그러나 라이브러리 설계자는 많은 유스 케이스를 설계해야하므로 최대한 많은 수의 옵션을 처리해야하므로 절대적으로 최선의 옵션보다 느린 옵션을 선택해야 할 수도 있습니다.

또한 키가 문자열 일 때 trie를 사용하는 std::map 또는 std::set의 특수화를 준수하는 C++ 구현이 실제로 실제로 완벽하게 가능합니다. 나는 아무 것도 믿지 않지만 이론적으로 가능합니다.

희망이 도움이됩니다.