c++ - 下限のある最も近い点を見つけています...しかしデータはソートされていません

Question

線に沿った特定の参照点までの距離を格納するベクトルがあります。たとえば、距離が700メートルまたはその距離に最も近い値であるインデックスが必要です。

ベクトルがソートされ、lower_boundを使用して成功したと仮定しました。

問題は、実際にはエラーが発生することです。たとえば、データを保存するときにユーザーがその行に従わなかった可能性があるため、常に並べ替えられたベクトルがあるとは限りません。

データが並べ替えられていない場合、どうすれば最も近い値を見つけることができますか？

Answer 1

std::vectorはシーケンスコンテナであるため、できません。並べ替えアルゴリズムを使用してデータを並べ替える必要があります。

Answer 2

std::min_element3つの引数の形式で使用できます。true最初の引数が2番目の引数よりもターゲット距離（700m）に近い場合に返されるコンパレータを渡します。次に、から返される結果はmin_element、ターゲットに最も近いポイントになります。

もちろん、これは漸近的にはよりも遅くなりますがlower_bound、ベクトルをソートする最悪の場合よりも漸近的に速くなります。ベクトルを一度並べ替えてから、複数の異なる距離で最も近い点を検索している間、並べ替えたままにすることができる場合は、おそらくとを使用する必要がstd::sortありstd::lower_boundます。最も近いポイントを見つけることが1回限りの操作である場合は、を使用して「遅い」方法で行う方がよい場合がありますmin_element。

Answer 3

vectorをstlにコピーしてからset、要素を見つけるためにベクトルに対して行ったのと同じロジックを使用します。