0

重複の可能性:
C++ マルチマップはどのように実装されていますか?

C++ リファレンスの言及

マルチマップは通常、二分探索木として実装されます。

しかし、彼らの典型的な内部表現は何ですか? 似ているstd::map<Key, std::list<Value> >か似ているか？私の懸念は、同じキーを持つ一連の要素に対する挿入と反復の複雑さです。

4

1 に答える 1

1

特定の操作の複雑さを知りたい場合は、標準以外に目を向ける必要はありません。標準には複雑さに関する保証がありますが、実装は自由にそれらの保証を満たすことができます。

挿入のO(lg n)場合、毎回最適なヒントを指定しない限り、複雑さは です。その場合、複雑さはO(1)償却されます。(詳細はこちら: http://en.cppreference.com/w/cpp/container/multimap/insert )

同じキーを持つ一連の要素に対する反復の場合、複雑さは、任意の反復子から別の反復子への反復と同じです。反復子が既に見つかっている場合、反復は、反復するアイテムの数に比例します。（申し訳ありませんが、現在これに関する参照を見つけることができません）

于 2013-01-29T12:17:13.287 に答える