c++ - 从容器中获取唯一元素 [c++]

Question

我只想从容器中获取独特的元素。假设 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 的评论。也改变了元素的顺序。有没有更好的方法在不改变顺序的情况下获得独特的元素？

谢谢

Answer 1

根据有关源数据的信息进行编辑:您看到集合插入比排序 vector 更快完成的原因是您的输入数据是两个已经排序的范围。对于快速排序(通常由 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 应该删除唯一值，但请记住，无论您断言什么，它仍会按照与前两个选项完全相同的方式重新排序项目。