c++ - 从列表中找到最近的点到一个引用列表

Question

我有成对的 int 坐标列表，例如

list<pair<int,int> > coordinates;

我需要找到离一个点原点最近的点，

class Point{
public:
float x;
float y;
};

我可以找到自定义比较器对象和排序，但我想知道是否有更快的方法使用 min ？我试过了

class DistanceComparator{
public:
    DistanceComparator(const Point& p){origin=p;}
    inline bool operator<(std::pair<int,int> & lhs,std::pair<int,int > & rhs)
    {
        float deltaX1=lhs.first-origin.x;
        float deltaY1=lhs.second-origin.y;
        float deltaX2=rhs.first-origin.x;
        float deltaY2=rhs.second-origin.y;
        return (deltaX1*deltaX1+deltaY1*deltaY1)<(deltaX2*deltaX2+deltaY2*deltaY2);
    }
private:
    Pointorigin;
};

但是 < 只需要一个参数。如何做到这一点？

Answer 1

您的解决方案不是最优的，因为它需要对整个列表进行排序，而这并不是必需的。您只需要最小的元素，无需对其余元素进行排序。我建议您查看 std::partial_sort 或只是去突击队并遍历它(O(n) 而不是 O(n*log(n )) 排序).