使用具有结构的 STL 向量上的唯一内容

Question

在编程任务中，我试图确保特定向量仅包含唯一的项目。对于原始类型，操作非常简单：

vector<int> lala;
lala.push_back(1);
lala.push_back(99);
lala.push_back(3);
lala.push_back(99);

sort(lala.begin(), lala.end()); // lala: 1, 3, 99, 99
lala.erase(unique(lala.begin(), lala.end()), lala.end()); // lala: 1, 3, 99

但是，问题是我没有使用 int。但是：

typedef struct
{
    int x;
    int y;
    int maxX;
    int maxY;
    int width;
    int height;
    int id;
} Rect;

bool SameRect(Rect first, Rect second)
{
    return first.x      == second.x &&
           first.y      == second.y &&
           first.width  == second.width &&
           first.height == second.height &&
           first.maxX   == second.maxX &&
           first.maxY   == second.maxY;
}

//...
vector<Rect> lala;
//...
sort(lala.begin(), lala.end());
lala.erase(unique(lala.begin(), lala.end(), SameRect), lala.end());
//...

实际上不起作用。我做错了什么？

编辑：

根据某人的建议，我为 std::sort() 实现了两个排序谓词：

bool SortRect(const Rect &first, const Rect &second)
{
    if (first.x < second.x) return true;
    if (first.x > second.x) return false;

    if (first.y < second.y) return true;
    if (first.y > second.y) return false;

    if (first.maxX < second.maxX) return true;
    if (first.maxX > second.maxX) return false;

    if (first.maxY < second.maxY) return true;
    if (first.maxY > second.maxY) return false;

    if (first.width < second.width) return true;
    if (first.width > second.width) return false;

    if (first.height < second.height) return true;
    if (first.height > second.height) return false;

    if (first.id < second.id) return true;
    if (first.id > second.id) return false;

    return false;
}

但我发现它具有相同的效果：

bool SortRect(const Rect &first, const Rect &second)
{
    return first.x < second.x;
}

如果 SGI 的文档有任何内容。更短、简单的排序谓词也应该有效。我的测试已经证实了这一点（尽管我还没有尝试所有可能的组合）。

Answer 1

您还必须定义一个比较函数，sort() 应该使用该函数对矩形进行排序。这个比较函数应该实现严格弱排序，以便相等的元素最终在向量中彼此相邻。

如果向量未排序，unique() 将找不到未排序的重复元素。

Answer 2

为什么不使用 std::set首先？其内容保证是唯一的。

旁注：
您不需要在 C++ 中typedef 结构，只需 struct Rect {}; 就足够了。
您的比较函数应该通过 const 引用（即 const Rect&）获取其参数，因为它不需要修改它们，也不需要副本。

Answer 3

sort(lala.begin(), lala.end());

std::sort 如何知道如何对 Rect 进行排序？适当地？定义一个比较函数并将其作为第三个参数传递，就像您对 std::unique 所做的那样。它必须采用两个 Rect 作为参数，如果第一个 Rect 小于则返回 true。第二个。

例如：

bool CompareRect(const Rect& first, const Rect& second) {
    return first.id<second.id;
}

请注意，我将 Rect 作为 const 引用传递，您似乎在示例中忘记了这一点。

Answer 4

这就是我想到的：

我在排序函数中添加了一个谓词：

bool SortRect(const Rect &first, const Rect &second)
{
    if (first.x < second.x) return true;
    if (first.x > second.x) return false;

    if (first.y < second.y) return true;
    if (first.y > second.y) return false;

    if (first.maxX < second.maxX) return true;
    if (first.maxX > second.maxX) return false;

    if (first.maxY < second.maxY) return true;
    if (first.maxY > second.maxY) return false;

    if (first.width < second.width) return true;
    if (first.width > second.width) return false;

    if (first.height < second.height) return true;
    if (first.height > second.height) return false;

    if (first.id < second.id) return true;
    if (first.id > second.id) return false;

    return false;
}

但我发现它具有相同的效果：

bool SortRect(const Rect &first, const Rect &second)
{
    return first.x < second.x;
}

那么是不是像所说的那样，我只需要对第一个元素进行排序（对于唯一的函数工作正常）？

Answer 5

我不确定你想要实现什么，但一般来说，正如所指出的，你需要设计你的矩形的比较。是什么使得一个矩形在序列中排在另一个矩形之前。

最简单的变体之一是在 x 坐标上进行比较。更复杂的选项是根据为矩形计算的希尔伯特值进行排序。请参阅问题计算 希尔伯特 R 树中使用的点的希尔伯特值？

也许您正在研究某种空间索引，然后了解R 树