今日私はpythonのソースコードを探しています。そして、私はpythonとC＃の両方を使って、Dictionaryを実装するためのハッシュを見つけました。C++ STLはRBtreeを使って "std :: map"を実装するのはなぜですか？
ハッシュの時間の複雑さはO(1)あるとRBtreeはO(lgn)なので、誰も私にC++ STLがstd::mapを実装するためにRBtreeを使用する理由を伝えることができますか？
ハッシュテーブル用に別のコンテナがあるため、std::unordered_map<>です。また、.NETにはDictionary<>に加えてSortedDictionary<>があります。
'std :: map'（ソートされています）への追加の要件について言及すると、' Dictionary'と異なり、 'SortedDictionary'と等しくなります。 –
RBtreeでは特定の範囲内にあるすべてのアイテムを選ぶことができますが、ハッシュテーブルではこれを行うことはできません。 – lai
"ハッシュの時間複雑さはO（1）です" - 最良の場合です。最悪の場合はまだO（n）です。 rbツリーは、すべてのケースでlog（n）を達成するためのバランス技術を使用します。そして、プラス、もちろん順番の違い。 – innochenti
答えは、オンラインで利用可能な「標準C++ライブラリ、チュートリアルおよびリファレンス」http://cs-people.bu.edu/jingbinw/program/The%20C++STL-T&R.pdfにあります。説明
ショート引用：一般的に
は、全体の標準（言語とライブラリは）議論の多くと世界中の何百人もの人々から 影響の結果です。たとえば、日本語は という重要な国際化対応を思いついた。もちろん間違いがあり、心が変わった、 と人々は異なった意見を持っていました。その後、1994年に、標準が に近いと考えられたとき、STLが組み込まれ、ライブラリ全体が大幅に変更されました。しかし、 になると、拡張機能がどのように役に立つかにかかわらず、主な拡張機能についての考え方は最終的に停止しました。したがって、ハッシュテーブルは標準の一部ではありませんが、 は共通データ構造としてSTLの一部でなければなりません。
++ 11 Cその時が出てきたことから明らかにし、名前以来mapはすでに撮影された、とhash_mapは既に広く（eg__gnu_cxx :: hash_map）一般的な拡張ライブラリを経由して使用された名前、名前unordered_mapですハッシュマップ用に選択されました。
漸近線によって盲目にされるべきではありません。 BSTとハッシュテーブルは非常に異なるデータ構造であり、測定することでどちらが問題に適しているか分かります。ハッシュテーブルはキータイプの要求がより難しく複雑であるため、ツリーベースの* ordered *マップは連想型コンテナーにとってより自然な第一の選択肢でしたが、C++ 11では両者があります。 –