c++ - 複雑さに関してより効率的な C++ map::find または map::iterator

Question

ご存知のように、 map::find は、キーの場所を見つける場所を指すイテレータを返します。また、二分探索操作であるため、複雑さは O(logn) です。したがって、内部的にイテレータを維持しているようで、成功すると返されます。どちらも実行時に同じ複雑さを提供すると思うので、どちらがより効率的な検索またはイテレータです（私は間違っているかもしれません）。どこでfindを使用し、どこでイテレータを使用するかを提案してください。実装の 1 つと同様に、特定のキーのマップを調べる必要があります (マップには N 個のキーが含まれている可能性があり、そのうち m 個のキーのみに関心があります)。したがって、 find がより効率的かイテレータか。また、複雑さを増すコードにif elseケースをあまり入れたくないので、find failureケースを処理するための良い方法は何でしょう。

Answer 1

私はあなたが何を意味するのか完全にはわかりませんが、マップのイテレータstd::map<...>::find()で使用するよりも使用する方が効率的です。内部ツリーのバイナリ検索はツリーをナビゲートするだけで、マップのサイズでパフォーマンスがあります。バイナリ検索も実行しますが、イテレータを使用および/または移動する必要があります。したがって、パフォーマンスがあります。コンパイルさえすべきではないと思いますが、コンパイルできないかどうかは完全にはわかりません。std::lower_bound()O(log(n))nstd::lower_bound()operator++()operator--()O(n)

Answer 2

まず、彼らは 2 つの異なることを行います。第二に、実装に依存します。

Answer 3

経験則として、一般的なアルゴリズム（std::findここ）と同じ名前のコンテナー固有のアルゴリズム（ここ）のどちらかを選択できる場合は、コンテナー固有のアルゴリズムをstd::map<...>::find使用してください。

一般的なバージョンよりも効率的でなければ、コンテナ固有のコンテナを実装することを気にする人は誰もいなかったでしょう。それは時間の損失でした。