如何有效地仅保留重复项? [英] How to keep only duplicates efficiently?
本文介绍了如何有效地仅保留重复项?的处理方法,对大家解决问题具有一定的参考价值,需要的朋友们下面随着小编来一起学习吧!
问题描述
给定一个STL向量,仅按排序顺序输出重复项,例如,
Given an STL vector, output only the duplicates in sorted order, e.g.,
INPUT : { 4, 4, 1, 2, 3, 2, 3 }
OUTPUT: { 2, 3, 4 }
该算法很简单,但是目标是使其效率与std :: unique()一样。我的天真的实现就地修改了容器:
The algorithm is trivial, but the goal is to make it as efficient as std::unique(). My naive implementation modifies the container in-place:
我的天真的实现:
void not_unique(vector<int>* pv)
{
if (!pv)
return;
// Sort (in-place) so we can find duplicates in linear time
sort(pv->begin(), pv->end());
vector<int>::iterator it_start = pv->begin();
while (it_start != pv->end())
{
size_t nKeep = 0;
// Find the next different element
vector<int>::iterator it_stop = it_start + 1;
while (it_stop != pv->end() && *it_start == *it_stop)
{
nKeep = 1; // This gets set redundantly
++it_stop;
}
// If the element is a duplicate, keep only the first one (nKeep=1).
// Otherwise, the element is not duplicated so erase it (nKeep=0).
it_start = pv->erase(it_start + nKeep, it_stop);
}
}
如果可以提高效率,美观或一般,请让我知道。例如,使用自定义排序算法或在第二个循环中复制元素以消除对delete()的调用。
If you can make this more efficient, elegant, or general, please let me know. For example, a custom sorting algorithm, or copy elements in the 2nd loop to eliminate the erase() call.
推荐答案
STL ish比以前的条目更多。假定已排序的输入。
Shorter and more STL-ish than previous entries. Assumes sorted input.
#include <algorithm>
#include <functional>
template< class I, class P >
I remove_unique( I first, I last, P pred = P() ) {
I dest = first;
while (
( first = std::adjacent_find( first, last, pred ) )
!= last ) {
* dest = * first;
++ first;
++ dest;
if ( ( first = std::adjacent_find( first, last, std::not2( pred ) ) )
== last ) break;
++ first;
}
return dest;
}
template< class I >
I remove_unique( I first, I last ) {
return remove_unique( first, last,
std::equal_to< typename std::iterator_traits<I>::value_type >() );
}
这篇关于如何有效地仅保留重复项?的文章就介绍到这了,希望我们推荐的答案对大家有所帮助,也希望大家多多支持IT屋!
查看全文