c++ - std::unordered_multiset 挿入の複雑さ

Question

std::unordered_multiset挿入の最悪の場合の複雑さが線形になるのはなぜですか? （挿入された値がセットにないことを確認する必要があります）が、マルチセットの場合はわかりstd::unordered_setません。明らかな何かが欠けていますか？

Answer 1

の最悪の場合の複雑さstd::unordered_multiset::insert()は次の理由から線形です。

• 一意でないキーをサポートする順序付けられていない連想コンテナーは、同等のキーをサポートすると言われています。これらのコンテナを反復するとき、同等のキーを持つ要素は反復中に互いに隣接し、同等のキー グループを形成します。
• イテレータ関数には一定の償却時間が必要です。

たとえば、5、13、およびがバケットを持つ13に挿入され、が返される場合を考えてみましょう。この場合、はとの両方に対して異なるハッシュ コードを返します。ハッシュ コードが異なっていても、これらの要素は同じバケットに挿入される可能性があります。整数のハッシュ関数が整数自体を返し、バケット インデックスがバケット数を法とするハッシュ コードの結果である場合、次のようになります。unordered_multiset4unordered_multiset::key_eq(5, 13)falseunordered_multiset::hash_function(5)513

• 要素5は にハッシュされ5、バケットを使用すると、4バケットに配置されます1。
• 要素13は にハッシュされ13、バケットを使用すると、4バケットにも配置さ1れます。

unordered_set::insert()挿入中の重複を防ぐためにチェックしながらunordered_multiset::insert()、同等のキー グループ化のために要素を挿入する場所を識別します。最悪の場合、[5, 13]最後の を挿入するときにバケットに含まれ13、すべての要素を反復すると、バケットに が含まれます[5, 13, 13]。すべての要素に対する反復が発生すると、複雑さは線形になりsize()ます。

unordered_multiset::insert()中に再ハッシュが発生する可能性があることに注意してください。これは、平均ケースが線形で、最悪のケースが二次unordered_multiset::rehash()である複雑さを持つと指定されています。size()再ハッシュ中、元のハッシュ テーブルのすべての要素が繰り返され、新しいハッシュ テーブルに挿入されます。反復の複雑さは で線形でsize()あり、上で特定したように、各挿入は で線形の最悪のケースを持ちsize()、結果として生じる最悪のケースはO(size()*size())です。