4

我希望只从容器中获取独特的元素。假设srcContainer是我想要独特元素的容器。我看了三个选项：

  1. 使用 std::unique 

       std::sort(srcContainer.begin(), srcContainer.end());
   srcContainer.erase(std::unique(srcContainer.begin(), srcContainer.end()), srcContainer.end());

  2. 使用 BOOST::unique 

    boost::erase(srcContainer, boost::unique<boost::return_found_end>(boost::sort(srcContainer)));

  3. 我自己的方法 

    std::set<T> uniqueElems(srcContainer.begin(), srcContainer.end());  
srcContainer.clear();  
srcContainer.insert(srcContainer.end(), uniqueElems.begin(), uniqueElems.end());

1. 和 2. 的问题在于它们改变了成员在原始 srcContainer 中出现的顺序。与 3. 相比，顺序没有变化，此外，与上面的 1. 和 2 相比，它提供了更好的性能（是不是因为 3. ?? 中没有明确的排序）。上面 3 种方法的挂钟时间和 srcContainer 中的元素数量如下所示：

  1. srcContainer 的大小（包含整数）= 1e+6
    - std::unique = 1.04779 秒
    - BOOST::unique = 1.04774 秒
    - 自己的方法 = 0.481638 秒

  2. srcContainer 的大小（包含整数）= 1e+8
    - std::unique = 151.554 秒
    - BOOST::unique = 151.474 秒
    - 自己的方法 = 57.5693 秒

我的问题是：

  1. 有没有更好的方法来使用 std::unique 或 BOOST::unique 或任何其他代码找到唯一并保持容器中的原始顺序？
  2. 使用上述方法 3. 的任何问题。

对于性能分析srcContainer，创建如下： 

std::vector<int> srcContainer;  
int halfWay = numElems/2;  
for (size_t k=0; k<numElems; ++k) {  
   if (k < halfWay)  
      srcContainer.push_back(k);  
   else  
      srcContainer.push_back(k - halfWay);  
}

编辑：
同意方法3的评论。也改变了元素的顺序。有没有更好的方法在不改变顺序的情况下获得独特的元素？

谢谢

4

1 回答 1

1

根据有关源数据的信息进行编辑：您看到集合插入完成比对向量排序更快的原因是您的输入数据是两个已经排序的范围。对于快速排序（通常由 使用std::sort），这是一种退化的情况，也是您可以给它的最糟糕的输入之一。对于1e8更改排序的输入大小std::sort以std::stable_sort将运行时间从 ~25s 减少到 <9s。

如果您想保留原始项目顺序，您可以尝试以下方法，保留所有项目的哈希值。我不知道这会是什么性能，但例如，您可以使用一种带有散列的方法，remove_if如下图所示：

struct Remover
{
    explicit Remover(hash& found_items) : found_items_(found_items) { }
    bool operator()(const Iter& item) { retval = <does exist in hash>; add to hash; return retval; }

    hash& found_items_;
};

hash dup_finder;
Remover remover(dup_finder);
std::erase(std::remove_if(src.begin(), src.end(), remover), src.end());

我的答案的原始组成部分：

如果源容器中的元素大部分已经排序，您可能会看到stable_sort在调用之前使用排序而不是排序更好unique。如果没有有关 yoru 数据集的更多信息，我无法猜测可能导致选项 3 的性能优于 1&2 的原因。

选项 3 应该删除唯一性，但请记住，尽管您断言，它仍然会以与前两个选项完全相同的方式重新排序项目。

于 2013-05-10T19:56:53.420 回答