如何从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

如果您正在使用原始数组(而不是a 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

希望这可以帮助!