1

我有成对的 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;
};

但是 < 只需要一个参数。这个怎么做 ？

4

3 回答 3

5

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

于 2012-11-02T14:24:10.390 回答
2

正如 Luchian Grigore 已经说过的，您不应该对点列表进行排序。但是，我想在这里解决您的语法问题。

您不能将比较运算符作为比较其他两个对象的类成员。您只有两种可能来定义比较运算符：

  1. 作为左侧操作数bool T::operator<(const U& rhs) const的成员函数。this（我认为 const-reference 是可选的，但当然强烈推荐。）请注意，T == U这不一定是真的。

  2. 非成员函数bool operator<(const T& lhs, const U& lhs) const又T == U不一定是真的。

所以你不能有一个比较运算符来访问你想要的三个对象：两个操作数，有点像一个可以参数化比较的“上下文”。

为了解决这个问题，我知道以下两种解决方案（可能不止这些）：

  1. 开始使用比较运算符时，将附加参数设置为全局变量。当然，这很脏（全局变量在 OOP 中总是脏的）并且使排序不可重入。由于它太脏了，我永远不会推荐它（但它仍然是一个可能的解决方案），因此我不会在这里给出示例代码。

  2. 使用谓词而不是operator <. 有多种方法可以做到这一点。这里有两个：

    如果您有可用的 c++0x / c++11：使用lambda 函数，该函数可以从客户端上下文（您运行的位置std::sort）捕获附加参数：

    Point origin = ...;
std::sort(..., [origin](const Point & a, const Point & b){
    return distance(a, origin) < distance(b, origin);
});

    如果您没有可用的 c++0x / c++11：您仍然可以定义自定义谓词以自定义方式比较两个对象，而无需 lambda 函数。您必须定义一个比较器助手类：

    // Helper class:
struct PointDistanceComparator {
    PointDistanceComparator(Point origin) : origin(origin) {}
    bool operator() (const Point & a, const Point & b) const {
        return distance(a, origin) < distance(b, origin);
    }
private:
    Point origin;
};

// Client code:
Point origin = ...;
std::sort(..., PointDistanceComparator(origin));

    当然，您可以（像您一样）优化代码以不使用平方根来计算距离。示例代码应该只让您了解如何对一般比较进行参数化。

于 2012-11-02T15:08:16.257 回答
1

如果您需要多次查询坐标列表，您可能需要考虑使用Kd-tree进行最近邻搜索。这将具有O(log n)时间复杂度。构建和查询 Kd 树大约需要 15-20 行（可读）C++ 代码。看看Kd-tree wikipedia article 也看看std::nth_element，你可以使用它来有效地构建你的 Kd-tree （选择支点和分区容器（左右子项，请参阅 wikipedia 文章中的 python 代码） .

更新：我使用 K-最近邻搜索创建了一个C++ N 维 Kd 树实现。它包括一些单元测试，向您展示如何使用它。

于 2012-11-03T03:12:06.253 回答