良いのstd ::ポインタのコレクションで見つけ、const参照値

Question

に間接参照値との比較は、もともと私はこれをしなかった方法でstd::vector<Point>たメンバーを持っていましたstd::vector<Point*>となり、もはや働いていた従来の方法と私はそれを変更しなければならなかった：

bool Spline::Intersects(const Point& point) const { 
    for(std::vector<Point*>::const_iterator _iter = _result_points.begin(); _iter != _result_points.end(); ++_iter) { 
     if(*(*_iter) == point) return true; 
    } 
    return false; 
} 

std::findが同じ線形検索を実行していますか？もしそうなら、これを行うためのより速い/より良い/より少ない粗い方法があります（特にイテレータの二重参照解除）？

std::find(this->_result_points.begin(), _result_points.end(), point) != _result_points.end();（またはそれに類するが、反対の結果）が実行されるコードには他の場所があり、その遅い線形ループを使用する必要はありません。

Answer 1

はい、findは同じ線形検索を行います。

あなたは、適切な述語でfind_ifを使用することにより、ループ、ダブル間接を隠すことができます：bool operator()(Point* ptr) { return *ptr == point; }

あなたは線形検索を避けたい場合は、データが格納されている方法を変更する必要があります。例えば、ベクトルをソートしたままにすると、std::findよりも速いstd::binary_searchが可能になります。これは、値がではなく、がポインタ値でソートされているため、比較器をstd::sortなどに渡す必要があります。また、まったく別のコンテナを使用することもできます。(unordered_)(multi)setのいずれかです。