構築中のSTLマップコンテナは最適化されていますか（バランスツリー）？

（増加する）シーケンスの要素をマップに挿入すると、最後のバイナリツリーは何とか最適化されますか？それとも、すべての要素に「正しい」という子供がいますか？それはからルックアップが線形になるので、そのような木は非常に非効率になります。構築中のSTLマップコンテナは最適化されていますか（バランスツリー）？

STLマップへの挿入プロセスに関する詳細情報が見つかりませんでした。

出典

2012-05-03 HWende

これは厳密に実装依存であり、移植性について心配しない限り、実装固有の動作に実際に頼るべきではありません。あなたは、 'std :: map'が出現すると思われる*動作*に頼るべきです。 –

@Als「implmenentation specific behaviorsに依存する」と、理解の観点から行動がどのように実装されるかを知ることには違いがあります。 – Benj

@Benj：それが私がコメントとして投稿した理由です、あなたはそれに反対していますか？ –

C++ 11標準（23.1）はinsertと連想容器のfind両方について対数複雑さを義務付け。 2つのイテレータiおよびjからそれらを構成して、[i, j)が適切にソートされた値の範囲を示すようにしても、線形時間の複雑さが必要でさえあります。つまり、「最終バイナリツリーが最適化されている」ことを意味するのか、マップがバイナリツリーであるのかは不明です。それはSTLのオリジナルHP/SGIのリファレンス実装が持っていたものですので、実際には

は、しかし、std::set、std::mapとその多友人は、事実上、常に赤、黒の木であり、私が知っているすべての現代のC++ライブラリから派生しますその実装。

出典

2012-05-03 09:20:20

+1標準語の仕様の範囲内で質問に答えるためです。 –

@larsmans：実際には 'std :: map'はいくつかの制約のためバイナリツリー（red-blackまたはavl）として実装されています：1.' const'メソッドによってアクセスされたときにミュートされないようにする2.要素はメモリ内で安定していなければなりません。私は最近、スキップリストの使用について尋ねましたが、明らかに悪化しました。 Splay Treeは「1」に違反し、Bのツリー（およびバリアント）は「2」に違反します。私は、Bツリーがより良いパフォーマンスを提供する（より多くのメモリにやさしく、よりキャッシュフレンドリである）ので、「2」が挑戦されたはずだと思う。 –

@MatthieuM：私は同じ結論wrtに来るだろう。スプレイ・ツリーとスキップ・リストを含むが、B-ツリーはまだ考えていない。私は、Bツリーや2-3ツリー*が、間接的なレベルの追加レベルを犠牲にして使用できると考えています。 –

一般に、std::mapは、赤バランスのとれたツリーを使用して実装されています。だから、それは最適化されています。

注文データを挿入すると、ノード間のスワップがそれほど頻繁に行われないため、セルフバランシングはおそらく少なくなります。

出典

2012-05-03 09:14:36

さて、ありがとう！この情報の参照はありますか？（違反はありません） – HWende

@HWende none taken。実装が定義されているため、参照がありません。だから私は「一般的に」言った。標準ではいくつかの時間制限が保証されているので、O（n）を挿入または削除するのではなく、O（log（n））を得ることは間違いありません。 –

ソートされたデータを自己分散型ツリーに送ります。ツリーを作成するときに、いつも再均衡を取るのに多くの時間を費やす必要があるため、2番目のステートメントは正しくありません。大きなデータセットの場合は、可能であれば無作為に読み込むほうがよいでしょう。 – user2548100

setとmapは通常、ツリーバランシングを行いますので、findはO（log n）です。操作複雑さの多くは、ここに示されている：

http://www.cplusplus.com/reference/stl/

出典

2012-05-03 09:17:47 devil

私のセットとマップは樹木ではないので、ツリーバランスはしません.... – PlasmaHH

あなたに良いです。 :-) – devil

最適化されています！

SGI's Standard Template Library Programmer's Guideをご覧ください。あなたは、要素を挿入し、見つけるための以下の複雑さの仕様があります：挿入範囲の

平均複雑さはNがJで最もO（N *ログ（サイズ（）+ N））、

であります- 私。 findの平均複雑度は、最大でも対数です。

出典

2012-05-03 09:27:14 trenki

標準的なライブラリではないその特定のSTLライブラリの実装について。 – juanchopanza

@元高館：しかし//STLです。私が最後にチェックしたのは、STLと呼ばれるものは何も定義していませんでした。 – PlasmaHH

@PlasmaHHしかし、SGIのドキュメントはSGIのSTLを参照していますが、SGIのSTLはC++標準ライブラリに完全にはマッピングされていません。私はOPがSTLでなく標準ライブラリを意味すると仮定しています。 – juanchopanza

C++スタンダールはのstd ::マップ内の任意の要素そうのstd ::マップは自己均衡ツリーとして実装する必要があります（ISO/IEC 14882は、23.4.4.3の）対数アクセス時間を要します。

出典

2012-05-03 09:36:57 Alexander

構築中のSTLマップコンテナは最適化されていますか（バランスツリー）？

答えて

関連する問題