我有一个包含几个非相邻重复的载体。
举一个简单的例子，考虑：
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算法可以从矢量除去非相邻的重复？ 什么是它的复杂性？
我想你会做这样的：
我想在矢量使用两个迭代器：
的第一个的读取数据，并将其插入一个临时的集合。
在设置的读取数据是不是你第一个迭代器复制到第二个和增加它。
在最后你只保留到第二个迭代器中的数据。
复杂性为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 ;
}
}
}
如果不使用临时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 。 具有代表性的输入测量是可以肯定的，但唯一的办法。
你可以删除一些在环发的使用回答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，或者如果您的值的范围是很小的话，你可以简单地使用数组或bitarray。
由于问题是“有没有任何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 。 被删除的所有元素比较等于元素权之前他们（第一要素保持，因为我们不能统一不了了之）。 迭代器返回点的范围内新的结束[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梅干的载体。
有没有STL算法做你想要保留什么序列的原始顺序。
您可以创建一个std::set迭代或索引的入载体，与使用引用的数据，而不是迭代器/索引排序的东西比较谓语。 然后你删除一切事情，从没有在集合中引用的载体。 （当然，你也可以同样使用其他std::vector迭代器/索引， std::sort和std::unique的是，并以此作为参考，以什么保留。）
基于@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; 。 举例来说，在我的项目忽略某些舍入误差。
有约翰Torjo一个很好的文章与系统的方式过这个问题涉及。 他出现的结果似乎更通用，更高效比任何解决方案的建议到这里为止：
http://www.builderau.com.au/program/java/soa/C-Removing-duplicates-from-a-range/0,339024620,320271583,00.htm
https://web.archive.org/web/1/http://articles.techrepublic%2ecom%2ecom/5100-10878_11-1052159.html
不幸的是，约翰的解决方案的完整的代码似乎不再可用，约翰没有回应可电邮。 因此，我写了这是基于类似的理由，就像他自己的代码，但在一些细节上有所不同故意。 请随时与我联系（vschoech认为细胞COM），如果你想讨论细节。
为了使代码编译为你，我加了一些我自己的东西，图书馆，我经常使用。 此外，而不是用普通STL去，我用提高了很多创造更通用，更高效，更可读的代码。
玩得开心！
#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的选项是你提到的那些：放物品的std::set ，或致电std::sort ， std::unique和调用erase()在容器上。 这些都不满足您的要求“除去非相邻的重复和维护元素的顺序。”
那么，为什么不将STL提供一些其他的选择吗？ 没有标准库将提供一切为了每一位用户的需求。 在STL的设计考虑包括“对几乎所有用户的速度不够快”，“对几乎所有的用户是有用的，”和“提供异常安全性尽可能多地”（和“是标准委员会足够小”为库斯捷潘诺夫原本写的是大很多，而且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。 查找参考 。
基于该@戈登的回答，但使用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（纳米）。 其中n是元件的数量，m是独特的元素的数量。 至于空间的复杂性，因为它在地方移走，这将使用O（N）。
