我有一个包含一些不相邻重复项的向量。
作为一个简单的例子，考虑：
2 1 6 1 4 6 2 1 1
我试图vector通过删除不相邻的重复项并保持元素的顺序来使其独一无二。
结果将是：
2 1 6 4
我尝试的解决方案是：
手动消除重复：
Define a temporary vector TempVector.
for (each element in a vector)
{
if (the element does not exists in TempVector)
{
add to TempVector;
}
}
swap orginial vector with TempVector.
我的问题是：
是否有任何 STL 算法可以从向量中删除不相邻的重复项？它的复杂性是什么？
如果不使用临时set的，这样做可能会导致（可能）一些性能损失：
template<class Iterator>
Iterator Unique(Iterator first, Iterator last)
{
while (first != last)
{
Iterator next(first);
last = std::remove(++next, last, *first);
first = next;
}
return last;
}
用于：
vec.erase( Unique( vec.begin(), vec.end() ), vec.end() );
对于较小的数据集，实现简单性和不需要额外分配可能会抵消使用额外的理论更高的复杂性set。但是，使用代表性输入进行测量是唯一确定的方法。
我想你会这样做：
我会在向量上使用两个迭代器：
第一个读取数据并将其插入一个临时集。
当读取的数据不在集合中时，您将其从第一个迭代器复制到第二个迭代器并递增它。
最后，您仅将数据保留到第二个迭代器。
复杂度为 O(n.log(n))，因为重复元素的查找使用集合，而不是向量。
#include <vector>
#include <set>
#include <iostream>
int main(int argc, char* argv[])
{
std::vector< int > k ;
k.push_back( 2 );
k.push_back( 1 );
k.push_back( 6 );
k.push_back( 1 );
k.push_back( 4 );
k.push_back( 6 );
k.push_back( 2 );
k.push_back( 1 );
k.push_back( 1 );
{
std::vector< int >::iterator r , w ;
std::set< int > tmpset ;
for( r = k.begin() , w = k.begin() ; r != k.end() ; ++r )
{
if( tmpset.insert( *r ).second )
{
*w++ = *r ;
}
}
k.erase( w , k.end() );
}
{
std::vector< int >::iterator r ;
for( r = k.begin() ; r != k.end() ; ++r )
{
std::cout << *r << std::endl ;
}
}
}
因为问题是“是否有任何 STL 算法......？它的复杂性是多少？” 实现如下功能是有意义的std::unique：
template <class FwdIterator>
inline FwdIterator stable_unique(FwdIterator first, FwdIterator last)
{
FwdIterator result = first;
std::unordered_set<typename FwdIterator::value_type> seen;
for (; first != last; ++first)
if (seen.insert(*first).second)
*result++ = *first;
return result;
}
所以这就是如何std::unique实现加上一个额外的集合。unordered_set应该比普通的快set。删除所有与它们之前的元素比较相等的元素（保留第一个元素，因为我们无法统一为空）。返回的迭代器指向 range 内的新端点[first,last)。
编辑：最后一句话意味着容器本身没有被unique. 这可能会令人困惑。以下示例实际上将容器简化为统一集。
1: std::vector<int> v(3, 5);
2: v.resize(std::distance(v.begin(), unique(v.begin(), v.end())));
3: assert(v.size() == 1);
第 1 行创建一个向量{ 5, 5, 5 }。在第 2 行调用unique返回一个迭代器到第二个元素，它是第一个不唯一的元素。因此distance返回 1 并 resize修剪向量。
您可以使用以下方法删除fa答案中的一些循环remove_copy_if：
class NotSeen : public std::unary_function <int, bool>
{
public:
NotSeen (std::set<int> & seen) : m_seen (seen) { }
bool operator ()(int i) const {
return (m_seen.insert (i).second);
}
private:
std::set<int> & m_seen;
};
void removeDups (std::vector<int> const & iv, std::vector<int> & ov) {
std::set<int> seen;
std::remove_copy_if (iv.begin ()
, iv.end ()
, std::back_inserter (ov)
, NotSeen (seen));
}
这对算法的复杂性没有影响（即，它也是 O(n log n)）。您可以使用 unordered_set 对此进行改进，或者如果您的值范围足够小，您可以简单地使用数组或位数组。
基于@fa 的回答。它也可以使用 STL 算法重写std::stable_partition：
struct dupChecker_ {
inline dupChecker_() : tmpSet() {}
inline bool operator()(int i) {
return tmpSet.insert(i).second;
}
private:
std::set<int> tmpSet;
};
k.erase(std::stable_partition(k.begin(), k.end(), dupChecker_()), k.end());
这样它更紧凑，我们不需要关心迭代器。
似乎甚至没有引入太多的性能损失。我在我的项目中使用它，该项目需要经常处理相当大的复杂类型向量，它没有真正的区别。
另一个不错的功能是，可以使用std::set<int, myCmp_> tmpSet;. 例如，在我的项目中忽略某些舍入错误。
没有 STL 算法可以做您想要保留序列的原始顺序的事情。
您可以在向量中创建一个std::set迭代器或索引，并使用一个比较谓词使用引用的数据而不是迭代器/索引来对内容进行排序。然后，您从向量中删除集合中未引用的所有内容。（当然，您也可以使用另一个std::vector迭代器/索引，std::sort然后std::unique将其用作保留内容的参考。）
John Torjo 有一篇很好的文章，它系统地处理了这个问题。他提出的结果似乎比迄今为止建议的任何解决方案都更通用、更有效：
https://web.archive.org/web/1/http://articles.techrepublic%2ecom%2ecom/5100-10878_11-1052159.html
不幸的是，John 的解决方案的完整代码似乎不再可用，并且 John 没有回复可能的电子邮件。因此，我编写了自己的代码，该代码基于与他类似的理由，但在某些细节上故意有所不同。如果您愿意，请随时与我联系 (vschoech think-cell com) 并讨论详细信息。
为了使代码为您编译，我添加了一些我自己经常使用的库内容。此外，我没有使用普通的 stl，而是大量使用 boost 来创建更通用、更高效、更易读的代码。
玩得开心！
#include <vector>
#include <functional>
#include <boost/bind.hpp>
#include <boost/range.hpp>
#include <boost/iterator/counting_iterator.hpp>
/////////////////////////////////////////////////////////////////////////////////////////////
// library stuff
template< class Rng, class Func >
Func for_each( Rng& rng, Func f ) {
return std::for_each( boost::begin(rng), boost::end(rng), f );
};
template< class Rng, class Pred >
Rng& sort( Rng& rng, Pred pred ) {
std::sort( boost::begin( rng ), boost::end( rng ), pred );
return rng; // to allow function chaining, similar to operator+= et al.
}
template< class T >
boost::iterator_range< boost::counting_iterator<T> > make_counting_range( T const& tBegin, T const& tEnd ) {
return boost::iterator_range< boost::counting_iterator<T> >( tBegin, tEnd );
}
template< class Func >
class compare_less_impl {
private:
Func m_func;
public:
typedef bool result_type;
compare_less_impl( Func func )
: m_func( func )
{}
template< class T1, class T2 > bool operator()( T1 const& tLeft, T2 const& tRight ) const {
return m_func( tLeft ) < m_func( tRight );
}
};
template< class Func >
compare_less_impl<Func> compare_less( Func func ) {
return compare_less_impl<Func>( func );
}
/////////////////////////////////////////////////////////////////////////////////////////////
// stable_unique
template<class forward_iterator, class predicate_type>
forward_iterator stable_unique(forward_iterator itBegin, forward_iterator itEnd, predicate_type predLess) {
typedef std::iterator_traits<forward_iterator>::difference_type index_type;
struct SIteratorIndex {
SIteratorIndex(forward_iterator itValue, index_type idx) : m_itValue(itValue), m_idx(idx) {}
std::iterator_traits<forward_iterator>::reference Value() const {return *m_itValue;}
index_type m_idx;
private:
forward_iterator m_itValue;
};
// {1} create array of values (represented by iterators) and indices
std::vector<SIteratorIndex> vecitidx;
vecitidx.reserve( std::distance(itBegin, itEnd) );
struct FPushBackIteratorIndex {
FPushBackIteratorIndex(std::vector<SIteratorIndex>& vecitidx) : m_vecitidx(vecitidx) {}
void operator()(forward_iterator itValue) const {
m_vecitidx.push_back( SIteratorIndex(itValue, m_vecitidx.size()) );
}
private:
std::vector<SIteratorIndex>& m_vecitidx;
};
for_each( make_counting_range(itBegin, itEnd), FPushBackIteratorIndex(vecitidx) );
// {2} sort by underlying value
struct FStableCompareByValue {
FStableCompareByValue(predicate_type predLess) : m_predLess(predLess) {}
bool operator()(SIteratorIndex const& itidxA, SIteratorIndex const& itidxB) {
return m_predLess(itidxA.Value(), itidxB.Value())
// stable sort order, index is secondary criterion
|| !m_predLess(itidxB.Value(), itidxA.Value()) && itidxA.m_idx < itidxB.m_idx;
}
private:
predicate_type m_predLess;
};
sort( vecitidx, FStableCompareByValue(predLess) );
// {3} apply std::unique to the sorted vector, removing duplicate values
vecitidx.erase(
std::unique( vecitidx.begin(), vecitidx.end(),
!boost::bind( predLess,
// redundand boost::mem_fn required to compile
boost::bind(boost::mem_fn(&SIteratorIndex::Value), _1),
boost::bind(boost::mem_fn(&SIteratorIndex::Value), _2)
)
),
vecitidx.end()
);
// {4} re-sort by index to match original order
sort( vecitidx, compare_less(boost::mem_fn(&SIteratorIndex::m_idx)) );
// {5} keep only those values in the original range that were not removed by std::unique
std::vector<SIteratorIndex>::iterator ititidx = vecitidx.begin();
forward_iterator itSrc = itBegin;
index_type idx = 0;
for(;;) {
if( ititidx==vecitidx.end() ) {
// {6} return end of unique range
return itSrc;
}
if( idx!=ititidx->m_idx ) {
// original range must be modified
break;
}
++ititidx;
++idx;
++itSrc;
}
forward_iterator itDst = itSrc;
do {
++idx;
++itSrc;
// while there are still items in vecitidx, there must also be corresponding items in the original range
if( idx==ititidx->m_idx ) {
std::swap( *itDst, *itSrc ); // C++0x move
++ititidx;
++itDst;
}
} while( ititidx!=vecitidx.end() );
// {6} return end of unique range
return itDst;
}
template<class forward_iterator>
forward_iterator stable_unique(forward_iterator itBegin, forward_iterator itEnd) {
return stable_unique( itBegin, itEnd, std::less< std::iterator_traits<forward_iterator>::value_type >() );
}
void stable_unique_test() {
std::vector<int> vecn;
vecn.push_back(1);
vecn.push_back(17);
vecn.push_back(-100);
vecn.push_back(17);
vecn.push_back(1);
vecn.push_back(17);
vecn.push_back(53);
vecn.erase( stable_unique(vecn.begin(), vecn.end()), vecn.end() );
// result: 1, 17, -100, 53
}
我的问题是：
是否有任何 STL 算法可以从向量中删除不相邻的重复项？它的复杂性是什么？
您提到的 STL 选项是：将项目放入 astd::set或 callstd::sort中，std::unique然后调用erase()容器。这些都不能满足您“删除不相邻的重复项并保持元素的顺序”的要求。
那么为什么 STL 不提供其他选项呢？没有标准库会为每个用户的需求提供一切。STL 的设计考虑包括“对几乎所有用户来说足够快”、“对几乎所有用户都有用”和“尽可能提供异常安全”（以及“对标准委员会来说足够小”，就像库 Stepanov 最初一样写的要大得多，Stroustrup 砍掉了大约 2/3 的东西）。
我能想到的最简单的解决方案如下所示：
// Note: an STL-like method would be templatized and use iterators instead of
// hardcoding std::vector<int>
std::vector<int> stable_unique(const std::vector<int>& input)
{
std::vector<int> result;
result.reserve(input.size());
for (std::vector<int>::iterator itor = input.begin();
itor != input.end();
++itor)
if (std::find(result.begin(), result.end(), *itor) == result.end())
result.push_back(*itor);
return result;
}
此解决方案应为 O(M * N)，其中 M 是唯一元素的数量，N 是元素的总数。
据我所知，stl中没有。查找参考。
基于@Corden 的回答，但使用 lambda 表达式并删除重复项，而不是将它们写入输出向量
set<int> s;
vector<int> nodups;
remove_copy_if(v.begin(), v.end(), back_inserter(nodups),
[&s](int x){
return !s.insert(x).second; //-> .second false means already exists
} );
鉴于您的输入，vector<int> foo您可以remove在这里为您完成腿部工作，然后如果您想缩小向量，只需使用erase其他方式，last当您想要删除重复的向量但订单保留：
auto last = end(foo);
for(auto first = begin(foo); first < last; ++first) last = remove(next(first), last, *first);
foo.erase(last, end(foo));
就时间复杂度而言，这将是O(nm)。其中n是元素的数量，m是唯一元素的数量。就空间复杂度而言，这将使用O(n)，因为它会就地移除。