如何在 std::set 中存储二维几何向量

Question

我最近参加了编程比赛。其中一项任务是关于几何的。我发明的解决方案是使用 2D 向量容器，其中每个向量都是唯一的。抛出副本的最快容器是 std::unordered_set。但是我忘记了如何制作自定义哈希，所以我使用了 std::set:

struct Vector
{
    int x;
    int y;

    bool operator<(const Vector& rhs) const
    {
        return x < rhs.x && y < rhs.y;
    }
}

std::set<Vector> geometry;

当然错了。 明白为什么错了。这是比赛的六个任务之一，时间限制为 2 小时。所以我假设，这个 任务可以在 ~20 分钟 内完成。我可以使用 std::vector 检查唯一性，但测试器有时间限制，而且速度可能很慢（O（n^2））。

所以我有这些要求：

容器必须防止插入副本
容器必须至少比 std::vector
代码应该足够简单和小，以便在大约 10 分钟内编写和调试它

那么，有了所有这些要求，如何以这种方式存储二维向量？

Answer 1

我认为您在 std::set 中存储（让我说点）的想法很好，并且在实践中效果很好。

但是您在执行 operator<() 时出错了。例如。积分会发生什么

(1, 4) 和 (2, 2)？你的代码会告诉你

(1, 4) >=(2, 2) 和 (2, 2) >= (1, 4)，这是 stl

中相等的定义

您可以使用 std::tie() 来自动执行这样的比较，如下所示：

struct Vector
{
    int x;
    int y;

    bool operator<(const Vector& rhs) const
    {
        return std::tie(x, y) < std::tie(rhs.x, rhs.y);
    }
};

Answer 2

正如另一个答案指出的那样，您的解决方案在理论上是正确的。但是，您的 operator < 将不正确。

使用 <complex> 的替代方法是仅使用 std::pair 表示 x,y 点。 std::pair 包含一个内置的 operator <，因此您需要做的就是在 operator < 函数中调用它。

看这里：http://en.cppreference.com/w/cpp/utility/pair

#include <set>
#include <map>
#include <iostream>

struct Vector
{
    std::pair<int, int> xy;
    Vector(int x_ = 0, int y_ = 0) : xy(std::make_pair(x_, y_)) {}
    bool operator<(const Vector& rhs) const
    { return xy < rhs.xy; }
};

std::set<Vector> geometry;

int main()
{
    geometry.insert(Vector(1,2));
    geometry.insert(Vector(1,5));
    geometry.insert(Vector(1, 8));
    geometry.insert(Vector(1, 8));
    geometry.insert(Vector(1, 8));  // repeated
    geometry.insert(Vector(1, 8));  // repeated
    geometry.insert(Vector(2, 2));

    std::cout << geometry.size();
}

实例：http://ideone.com/njmuVX

该示例表明集合中只存储了唯一项，表明 std::pair 具有 operator < 所需的正确语义。

鉴于此，除非您向 Vector class 添加额外的成员函数，否则您可以简单地这样做：

std::set<std::pair<int, int>> geometry;

然后在 main 中执行此操作：

int main()
{
    geometry.insert(make_pair(1,2));
    geometry.insert(make_pair(1, 5));
    geometry.insert(make_pair(1, 8));
    geometry.insert(make_pair(1, 8));
}

但同样，如果您知道 pair 代表什么，并且您打算不将 Vector class 扩展到超过 x/y 值，请执行此操作.

Answer 3

关于 std::set 中排序的要点是某种排序必须存在，但排序不必具有任何实际意义。这意味着我们可以自由使用任何顺序，前提是不同的对永远不会被认为是相等的。一个简单的方法是：

struct Vector
{
    int x;
    int y;

    bool operator<(const Vector& rhs) const
    {
        if (x == x.rhs) {
            return y < rhs.y;
        else {
            return x < rhs.x;
        }
    }
}

std::set<Vector> geometry;

在上面，我们首先对x进行排序，只有当它们相等时，我们才会对y进行排序。这将提供 stl::set.

所需的唯一排序

Answer 4

将 std::unordered_set 与您选择的散列器一起使用。另外，不要忘记重载 operator== 以获得唯一性。总而言之，

#include <iostream>
#include <unordered_set>

struct Vector
{
    int x;
    int y;

    Vector(int x_, int y_) : x(x_), y(y_) { }

    friend bool
        operator==(const Vector& lhs, const Vector& rhs)
        { return (lhs.x == rhs.x) && (lhs.y == rhs.y); }
};

struct Hash
{
    int operator()(const Vector& v)
    const { return (v.x + v.y) % 13; }
  //^^^^^
  //hasher functions must be const
};

int main()
{
    std::unordered_set<Vector, Hash> vectorset;

    vectorset.insert(Vector(0, 1)); //unique
    vectorset.insert(Vector(2, 1)); //unique
    vectorset.insert(Vector(3, 4)); //unqiue
    vectorset.insert(Vector(0, 1)); //repeat
    vectorset.insert(Vector(2, 1)); //repeat
    vectorset.insert(Vector(3, 4)); //repeat
    vectorset.insert(Vector(2, 1)); //repeat
    vectorset.insert(Vector(9, 4)); //unique
    vectorset.insert(Vector(2, 1)); //repeat

    std::cout << vectorset.size() << std::endl;

    return 0;
}

输出： 4

如何在 std::set 中存储二维几何向量

How to store 2D geometry vectors in std::set

c++

vector

set

c++11