c++ - STLセットで静的とメンバーのfindメソッドを使用していますか?

Question

セットなどのソートされたコンテナーのクイックルックアッププロパティを使用したいので、セットを使用しています。並べ替えられたコンテナーの利点を得るためにメンバーの検索メソッドを使用する必要があるのか​​ 、それとも STL アルゴリズムで静的検索メソッドを使用できるのか疑問に思っています。

私の推測では、静的バージョンを使用すると、私が望むようにバイナリ検索ではなく線形検索が使用されるということです。

Answer 1

非会員バージョンは線形検索を行うのに対し、会員バージョンは O(log N) 検索を行うのは正しいです。std::set は、O(log N) の挿入、取得、および削除用に最適化されています。

定義のポイントとして、std::find メソッドは静的関数ではありません。C++ でstatic が意味するさまざまなことの説明については、こちらを参照してください。

Answer 2

これは実装に依存します。誰かがセットでバイナリ検索を使用する静的な「検索」の部分的な特殊化を実装している可能性がありますが、すべてを考慮すると、メンバー関数バージョンの方がパフォーマンスが優れている可能性があります。

IIRC の Scott Meyers は、彼の著書「Effective STL」で、find、swap などの一般的な関数のメンバー バージョンを非メンバー関数よりも常に優先することを提案しています。これは、非メンバー バージョンと比較して最適な実装である可能性が高いためです。また、通常はメンバー バージョンのパフォーマンス上の利点に頼ることができますが、特定の関数の部分的な特殊化が存在するという事実に常に頼ることはできません。