c++ - 如何从 C++ 数组中删除重复项？

Question

我有一个结构数组；该数组的大小为 N。

我想从数组中删除重复项；也就是说，进行就地更改，将数组转换为具有每个结构的单一外观。此外，我想知道新的大小 M(缩减数组中的最高索引)。

这些结构包含基元，因此比较它们很简单。

我怎样才能在 C++ 中高效地做到这一点？

我已经实现了以下运算符:

bool operator==(const A &rhs1, const A &rhs2) 
{       
    return ( ( rhs1.x== rhs2.x )  &&
             ( rhs1.y == rhs2.y ) );
}

bool operator<(const A &rhs1, const A &rhs2) 
{       
    if ( rhs1.x == rhs2.x )  
             return ( rhs1.y < rhs2.y );

    return ( rhs1.x < rhs2.x );
}

但是，运行时出现错误:

std::sort(array, array+ numTotalAvailable);

 * array will have all elements here valid.

std::unique_copy(
        array, 
        array+ numTotalAvailable, 
        back_inserter(uniqueElements)); 

 * uniqueElements will have non-valid elements.

这里有什么问题吗？

Answer 1

您可以结合使用 std::sort 和 std::unique 算法来完成此操作:

std::sort(elems.begin(), elems.end());                  // Now in sorted order.
iterator itr = std::unique(elems.begin(), elems.end()); // Duplicates overwritten
elems.erase(itr, elems.end());                          // Space reclaimed

如果您使用的是原始数组(而不是 std::vector)，那么如果不将元素复制到新范围，您实际上无法回收空间。但是，如果您可以从原始数组开始并以 std::vector 或 std::deque 之类的内容结束，则可以使用 unique_copy 和一个迭代器适配器，用于仅复制唯一元素:

std::sort(array, array + size); // Now in sorted order

std::vector<T> uniqueElements;
std::unique_copy(array, array + size,
                 back_inserter(uniqueElements)); // Append unique elements

此时，uniqueElements 现在包含所有唯一元素。

最后，为了更直接地解决您最初的问题:如果您想就地执行此操作，您可以通过使用 unique 的返回值来确定剩余的元素数量来获得答案:

std::sort(elems, elems + N);                // Now in sorted order.
T* endpoint = std::unique(elems, elems + N);// Duplicates overwritten
ptrdiff_t M = endpoint - elems;             // Find number of elements left

希望这对您有所帮助!