c++ - 如何在 std::set 中存储二维几何 vector

Question

我最近参加了编程比赛。其中一项任务是关于几何的。我发明的解决方案是使用 2D vector 容器，其中每个 vector 都是唯一的。最快的容器是 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))。

所以我有这些要求:

1. 容器必须防止插入拷贝
2. 容器必须至少比 std::vector
快
3. 代码应该足够简单和小，以便在大约 10 分钟内编写和调试

那么，在所有这些需求下，如何以这种方式存储 2D vector ？

Answer 1

正如另一个答案所指出的，您的解决方案在理论上是正确的。然而你的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 添加额外的成员函数类，你可以简单地这样做:

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类比 x/y 值更多。