В настоящее время я ищу исходный код на языке python, и я нашел, что и хеш для python и C# реализует Dictionary.Почему C++ STL использует RBtree для реализации «std :: map»?
Временная сложность хэша O(1) и RBtree является O(lgn), так кто-нибудь может сказать мне причину, почему C++ STL использует RBtree для реализации std::map?
Потому что у него есть отдельный контейнер для хеш-столов: std::unordered_map<>. Также обратите внимание, что .NET имеет SortedDictionary<> в дополнение к Dictionary<>.
Возможно, вы захотите упомянуть о дополнительных требованиях к 'std :: map' (сортировке, которые есть), что отличает его от словаря' Dictionary' и равно 'SortedDictionary'. –
Спасибо, поэтому в RBtree можно выделить все элементы, находящиеся в определенном диапазоне, но в хеш-таблице мы не можем этого сделать, правильно? – lai
«Сложность времени хэша O (1)» - в лучшем случае. В худшем случае все еще O (n). В rb tree используются методы балансировки для достижения log (n) для всех случаев. И, плюс, разница в порядке, конечно. – innochenti
Ответ можно найти в «Стандартной библиотеке C++, учебном пособии и справочной информации», который можно найти здесь: http://cs-people.bu.edu/jingbinw/program/The%20C++STL-T&R.pdf.
Короткая цитата объяснения:
В общем, всем стандарте (язык и библиотека) является результатом многих дискуссий и влияния сотни людей во всем мире. Например, японцы придумали важную поддержку интернационализации . Конечно, были сделаны ошибки, изменились умы, , и у людей были разные мнения. Затем, в 1994 году, когда люди считали, что стандарт близок к , конец STL был включен, что радикально изменило всю библиотеку. Однако до все закончилось, мышление об основных расширениях было в конечном итоге остановлено, независимо от того, как будет полезным расширение. Таким образом, хеш-таблицы не являются частью стандарта, хотя они должны быть частью STL как общей структуры данных.
Очевидно, что так как время с ++ 11 вышла, а с именем map уже принято, и hash_map это имя, которое уже широко используется с помощью библиотек общего расширения (eg__gnu_cxx :: hash_map), имя unordered_map был выбран для хэш-карт.
Вы не должны ослеплять асимптотикой. BST и хэш-таблицы - это очень разные структуры данных, и вы можете только реально узнать, какой из них лучше для вашей проблемы, измеряя. Поскольку хэш-таблицы имеют более сложные требования к типу ключа и являются более сложными, построенная на основе дерева * упорядоченная * карта была более естественным первым выбором для ассоциативного контейнера, но с C++ 11 мы имеем оба. –