順序付けられた（増加する）要素のシーケンスをマップに挿入すると、最終的なバイナリツリーは何らかの形で最適化されますか？それとも、すべての要素に「正しい」子がありますか？その場合、ルックアップは線形になるため、このようなツリーは非常に非効率になります。
STLマップへの挿入プロセスに関する詳細情報が見つかりませんでした。
5646 次
5 に答える
23
C ++ 11標準（23.1）は、両方insertとfind連想コンテナーの対数の複雑さを義務付けています。適切にソートされた値の範囲を示す2つのイテレータからそれらを構築するiことjは[i, j)、線形の時間計算量を持つためにも必要です。それが「最終的な二分木が最適化される」ことを意味するのか、それともマップが二分木であるのかは、特定されていません。
ただし、実際にはstd::set、std::mapとそのマルチフレンドは事実上常に赤黒木です。これは、STLの元のHP / SGIリファレンス実装が持っていたものであり、私が知っているすべての最新のC++ライブラリはその実装から派生しているためです。
于 2012-05-03T09:20:20.343 に答える
4
一般に、astd::mapは、自己バランス型の赤黒木を使用して実装されます。そうです、それは最適化されています。
順序付けられたデータを挿入する場合、ノード間のスワップはそれほど頻繁ではないため、セルフバランシングにかかる時間はおそらく少なくなります。
于 2012-05-03T09:14:36.040 に答える
1
C ++標準では、std :: map（ISO / IEC 14882の23.4.4.3）の要素に対数アクセス時間が必要なため、std::mapは自己平衡ツリーとして実装する必要があります。
于 2012-05-03T09:36:57.980 に答える
0
setとはmap通常ツリーバランシングを行うため、findはO（log n）です。操作の複雑さの多くはここに示されています：
http ：//www.cplusplus.com/reference/stl/
于 2012-05-03T09:17:47.430 に答える
0
最適化されています！
SGIの標準テンプレートライブラリプログラマーズガイドをご覧ください。要素を挿入および検索するための次の複雑さの仕様があります。
- 挿入範囲の平均複雑度は最大でO（N * log（size（）+ N））、
- ここで、Nはj-iです。検索の平均的な複雑さは、せいぜい対数です。
于 2012-05-03T09:27:14.540 に答える