c++ - C++ STL マップ: アクセス時間は O(1) ですか?

Question

キールックアップはstd::mapO(1) ですか? もっとよく考えるまではそうだと思っていました。ツリーの実装に基づいているため、ルックアップ時間は O(log N) である必要がありますね。

そして、std::unordered_mapおそらく O(1) で文字列キーを検索することは可能ですか?

Answer 1

のルックアップの複雑さstd::mapは O(log N) (コンテナーのサイズの対数) です。

パラグラフ 23.4.4.3/4 の C++11 標準std::map::operator []:

複雑さ: 対数。

のルックアップの複雑さはstd::unordered_map、平均的なケースでは O(1) (一定)、最悪のケースでは O(N) (線形) です。

C++11 標準のパラグラフ 23.5.4.3/4 によると、std::unordered_map::operator []

複雑さ: 平均ケース O(1)、最悪ケース O( size())。

ノート：

あなたの質問が計算の複雑さのみに関係している場合は、上記の内容がそれに答えるはずです。実際、操作の計算の複雑さは、コンテナーのサイズ(コンテナーに含まれる要素の数) で測定されます。

ただし、文字列キーを使用するコンテナで O(1) ルックアップを実行する方法を探していて、ルックアップの複雑さがコンテナのサイズではなく文字列の長さに関して一定である場合は、答えはstd::unordered_map、要件を満たしていないということです。

キーを検索するには、まずキーのハッシュを生成する必要があります。キーが文字列の場合、この操作自体は文字列のサイズに比例する可能性があります。次に、実装はキーを同じバケット内のすべての文字列キーと比較する必要があり、これらの比較のそれぞれは、それらの文字列のサイズで順番に線形になります。

Answer 2

はい、確かstd::map に一定時間の複雑さは平均的でありO(log N)、最悪の場合はハッシュ衝突が多すぎる場合です。std::unordered_mapO(N)

Answer 3

基本的に std::map は赤黒ツリーを使用して実装されています。赤黒ツリーの挿入操作と削除操作では O(LogN) 時間がかかるため、 std::map 時間の複雑さはすべての要素で O(LogN) です。

std::unodered_map はハッシュを使用して実装され、すべての操作に O(1) 時間がかかります。