从容器中获取独特元素[E]

发布时间：2020-12-16 07:04:19 所属栏目：百科来源：网络整理

导读：我只想从容器中获取独特的元素.假设srcContainer是我想要独特元素的容器.我看了三个选项：使用std :: unique std::sort(srcContainer.begin(),srcContainer.end()); srcContainer.erase(std::unique(srcContainer.begin(),srcContainer.end()),srcContainer

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

>使用std :: unique

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

>使用BOOST :: unique

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

>我自己的方法

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种方法的挂钟时间和srcContainer中的元素数量如下：

> srcContainer的大小(包含整数)= 1e 6
???? – std :: unique = 1.04779秒
???? – BOOST :: unique = 1.04774秒
???? – 自己的方法= 0.481638秒
> srcContainer的大小(包含整数)= 1e 8
???? – std :: unique = 151.554秒
???? – BOOST :: unique = 151.474秒
???? – 自己的方法= 57.5693秒

我的问题是：

>有没有更好的方法来查找使用std :: unique或BOOST :: unique或任何其他代码并保持容器中的原始顺序的唯一？
>使用上述方法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.也改变了元素的顺序.有没有更好的方法来获得独特的元素而不改变秩序？

谢谢

解决方法

编辑基于源数据的信息：
您看到设置插入完成比排序向量更快的原因是您的输入数据是两个已经排序的范围.对于快速排序(通常由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应该删除uniques但请记住,尽管你断言,它仍然会以与前两个选项完全相同的方式重新排序项目.

（编辑：李大同）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!