2

我有一个结构数组；数组大小为 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.

这里有什么问题？

4

4 回答 4

6

您可以使用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::vectoror之类的东西结束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现在拥有了所有独特的元素。

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

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

希望这可以帮助！

于 2011-08-24T17:59:20.203 回答
1 
std::set<T>  uniqueItems(v.begin(), v.end());

现在uniqueItems只包含独特的物品。用它做任何你想做的事。也许，您想v包含所有独特的项目。如果是这样，请执行以下操作：

//assuming v is std::vector<T>
std::vector<T>(uniqueItems.begin(), uniqueItems.end()).swap(v);

现在v包含所有独特的物品。它也缩小v到最小尺寸。它利用了Shrink-to-fit成语。

于 2011-08-24T18:07:27.813 回答
0

您可以使用享元模式。最简单的方法是使用Boost Flyweight 库。

编辑：我不确定是否有某种方法可以找出 Boost flyweight 实现存储了多少对象，如果有，我似乎无法在文档中找到它。

于 2011-08-24T17:56:43.247 回答
0

将算法应用于数组的另一种方法是将其元素插入到std::set. 这样做是否合理取决于您计划如何使用您的物品。

于 2011-08-24T18:07:46.763 回答