std::unordered_setには、2つのオブジェクトAとオブジェクトBが等しいかどうかを示す述語があります。私の質問は、AとBが等しいかどうかを判断するのに、O(k)時間が必要であるとします。 unordered_set::findはまだ償却された一定の時間を取るか、償却されたO(k)時間かかりますか？std :: unordered_setは、述語にかかわらずオブジェクトの償却定数ルックアップ時間を取るか？
std::unordered_mapによって保証される平均一定ルックアップの複雑さは、マップ内の要素の数のみを参照します。同じハッシュ値*を持つ少なくとも1つの要素がマップに含まれている場合、少なくとも1つのキーの完全比較を実行する必要があります。その比較がO（k）ならば、明らかにルックアップもO（k）となるが、それはかなり大きなkにのみ関係するはずである。
*）ほとんどの実装では、同じハッシュについてだけでなく、同じバケットに要素があると思います。
定数は償却されません。平均的なケース定数です。この区別は少し微妙だが重要である。 –
@ T.C。 ：ありがとう、固定 – MikeMB
O（k）がヒットしました。少なくとも1つの完全な比較を行う必要があります。 – MikeMB