Каков наилучший способ поиска/поиска точки в векторе точек?

Question

Я попытался отсортировать точки на основе их координат x и выполнить двоичный поиск по вектору, но я не могу найти точки, которые, как я знаю, они существуют.

Благодарим за помощь.

struct PointSort { 
    bool operator() (cv::Point pt1, cv::Point pt2) { return (pt1.x < pt2.x);} 
} mySort; 

. 
. 
. 
std::sort (temp.begin(), temp.end(), mySort); 
if (std::binary_search(temp.begin(), temp.end(), somePoint, mySort)){ 
    doSomething(); 
} 

Answer 1

Так что-то вроде:

struct point { int x, y; }; 
std::vector<point> pts { {1,2}, {4,5} }; 
auto comp_x=[](const point& p1, const point& p2) { 
    return p1.x < p2.x; 
}; 
std::sort(begin(pts), end(pts), comp_x); 
//using binary search 
auto it=std::lower_bound(begin(pts), end(pts), some_point, comp_x); 
//it now points to the point 

Нижней границы функции использует бинарный поиск, чтобы найти первый элемент (upper_bound находит последний) и дает итератор этому элементу.

Если вам не нужно его сортировать, я бы просто использовал std::find.

auto it=std::find_if(begin(pts), end(pts), [&](const point& p) { 
     return p.x==some_point.x; 
    } 
); 

Answer 2

Если вы просто хотите, чтобы найти Point, который соответствует одному вы подачи:

std::vector<Point> points; 
// points is filled somewhere 
Point p { 1, 2 }; 
std::vector<Point>::iterator it = std::find(points.begin(), points.end(), p); 

Если вы хотите настроить сравнение, вы можете использовать std::find_if:

Point pt { 1, 2 }; 
std::vector<Point>::iterator it = std::find_if(points.begin(), points.end(), [&](const Point& p) 
{ 
    return pt.x == p.x; 
}); 

И, ради Бога, игнорировать вздор «AAA» ...

Боковое примечание: ваш вектор не нужно сортировать, чтобы использовать std::find (хотя он ускорит его, если он есть). И если вы можете использовать стандарт C++ 11, вам не нужно, чтобы создать функтор:

std::sort(temp.begin(), temp.end(), [](const Point& p1, const Point& p2) 
{ 
    return p1.x < p2.x; 
}); 

Кроме того, если элементы вашего Point класса чисел с плавающей точкой, вы не хотите использовать прямое равенство для сравнений. Вместо этого, нарвать небольшое количество в качестве минимальной приемлемой точности (эпсилон), и сравнить разницу между 2 значения к нему:

float x = SOME_VALUE; 
float y = SOME_OTHER_VALUE; 
float EPSILON = 0.000000001; 
bool are_equal = std::abs(x - y) < EPSILON;