c++ - マルチセット、マップ、およびハッシュ マップの複雑さ

Question

次の場合の STL マルチセット、マップ、およびハッシュ マップ クラスの Big O 表記の複雑さを知りたいです。

• エントリの挿入
• エントリへのアクセス
• エントリの取得
• エントリの比較

Answer 1

マップ、セット、マルチマップ、マルチセット

これらは、バランス型二分探索木の一種である赤黒木を使用して実装されます。次の漸近的な実行時間があります。

挿入: O(log n)
検索: O(log n)
削除: O(log n)

hash_map、hash_set、hash_multimap、および hash_multiset

これらは、ハッシュ テーブルを使用して実装されます。次のランタイムがあります。

挿入: O(1) 予想、O(n) 最悪の場合
ルックアップ: O(1) 予想、O(n) 最悪の場合
削除: O(1) 予想、O(n) 最悪の場合

適切なハッシュ関数を使用すると、最悪の場合の動作はほとんど見られませんが、これは心に留めておくべきことです —その例については、Crosby と Wallach によるアルゴリズムの複雑さによるサービス妨害を参照してください。