c++ - 如何有效地从 vector 中删除重复的用户定义数据？

Question

让我们定义一个简单的结构 A。

struct A
{
   int x,y,z;
};

我想按照规则从 vector 中删除一些元素。

if two compared segments' x is same, remove one which has larger y value.

[before remove]
x y z
1 2 3
1 3 4 
1 4 5

[after remove]
x y z
1 2 3

另一个规则。

if two compared segment's x and y values are same, remove one which has smaller z value.
[before remove]
x y z
1 2 3
1 2 4
1 2 5

[after remove]
1 2 5

我在 STL 中使用了 unique 和 erase 函数来解决这个问题......如下所示

bool compare_x(const A & p1, const A & p2)
{
    if(p1.x == p2.x) // to erase larger one.
        return p1.y < p2.y
}


...
vector<A> list; // let's assume that this vector has some data.

list.erase(unique(list.begin(), list.end(), compare_x), list.end());

但是有些人对我说独特的功能并不好用..

所以我想知道有什么技术或功能可以解决这类问题。

谢谢。

Answer 1

为了去除所有重复元素，赋予std::unique 的范围必须让所有重复元素彼此相邻。元素的排序顺序会影响哪些重复项未被删除。因此，正确的解决方案是 std::sort、std::unique、erase。

其次，compare_x 是伪造的。它缺少返回语句以防 p1.x != p2.x。行为未定义。此外，谓词不能告诉算法要删除哪个等价元素；它告诉算法哪些元素是等价的。删除哪个元素取决于它们在输入范围中的位置。保留第一个等效元素。

问题的解决方案在于对排序和唯一性使用不同的谓词。 Unique 需要更宽松的标准，而排序需要有相同的标准，除了在相同的情况下它应该排序以便删除恰好正确的元素。

if two compared segments' x is same, remove one which has larger y value.

唯一谓词:仅由x。

排序谓词:按x，然后是y。 y 必须按升序排序。

if two compared segment's x and y values are same, remove one which has smaller z value.

唯一谓词:通过 x 和 y。

排序谓词:按x 和y，然后按z。 z 必须按降序排列。