如何使vector元素独特？ （删除不相邻的重复项）
我有一个载体，包含less数不相邻的重复项。
作为一个简单的例子，考虑：
2 1 6 1 4 6 2 1 1 我试图通过删除不相邻的重复项和维护元素的顺序使这个vector唯一。
结果将是：
2 1 6 4
我尝试的解决scheme是：
- 插入一个std ::集合，但这种方法的问题是，它会扰乱元素的顺序。
- 使用std :: sort和std :: unique的组合。 但是同样的顺序问题。
-
手动重复消除：
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.
我的问题是：
是否有任何STLalgorithm可以从vector中删除不相邻的副本？ 它的复杂性是什么？
我想你会这样做：
我会在vector上使用两个迭代器：
第一个读取数据并将其插入一个临时集合。
当读取的数据不在集合中时，将其从第一个迭代器复制到第二个迭代器，并将其递增。
最后，只保留数据到第二个迭代器。
复杂性是O（n .log（n）），因为重复元素的查找使用集合而不是vector。
#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() );
对于较小的数据集，实现的简单性和缺less额外分配可能会抵消使用额外set的理论上更高的复杂性。 测量与代表性的input是唯一可以肯定的方法。
您可以使用remove_copy_if删除fa答案中的一些循环：
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)); }
这对algorithm的复杂性没有影响（也就是写成O（n log n））。 你可以使用unordered_set来改进，或者如果你的值的范围足够小，你可以简单地使用一个数组或一个bitarray。
由于问题是“是否有任何STLalgorithm…？它的复杂程度如何？ 实现像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修改。 这可能会令人困惑。 下面的例子实际上将容器减less到统一集合。
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行创build一个vector{ 5, 5, 5 } 。 在第2行调用unique返回第二个元素的迭代器，这是第一个不是唯一的元素。 因此， distance返回1，并resize修剪向量。
没有STLalgorithm做你想要保留序列的原始顺序。
你可以在向量中创build一个std::set迭代器或索引，使用引用的数据而不是迭代器/索引来sorting内容的比较谓词。 然后你从集合中没有引用的vector中删除所有的东西。 （当然，你也可以使用迭代器/索引的另一个std::vector ， std::sort和std::unique ，并且用它作为参考。）
基于@fa的回答。 它也可以使用STLalgorithm重写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());
这样它就更紧凑，我们不需要关心迭代器。
这似乎甚至没有引入太多的performance惩罚。 我在我的项目中使用它，需要经常处理相当大的复杂types的vector ，并没有真正的区别。
另一个很好的特性是可以通过使用std::set<int, myCmp_> tmpSet;来调整唯一性 std::set<int, myCmp_> tmpSet; 。 例如，在我的项目中，忽略某些舍入错误。
John Torjo有一篇很好的文章，系统地解决了这个问题。 他提出的结果似乎比迄今为止所提出的任何解决scheme都更通用，更有效率：
https://web.archive.org/web/1/http://articles.techrepublic%2ecom%2ecom/5100-10878_11-1052159.html
不幸的是，约翰的解决scheme的完整代码似乎已经不可用了，约翰没有回应可能的电子邮件。 所以我写了我自己的代码，这个代码基于类似他的理由，但在一些细节上故意有所不同。 随时与我联系（vschoech think-cell com），并讨论细节，如果你愿意。
为了让代码为你编译，我添加了一些我自己定期使用的库东西。 另外，不用简单的stl，我使用boost来创build更通用，更高效，更可读的代码。
玩的开心！
#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 }
我的问题是：
是否有任何STLalgorithm可以从vector中删除不相邻的副本？ 它的复杂性是什么？
STL选项是你提到的：把项目放在std::set ，或者调用std::sort ， std::unique并在容器上调用erase() 。 这些都不符合你的要求，“去除不相邻的副本和维护元素的顺序”。
那么STL为什么不提供其他选项呢？ 没有标准的图书馆会为每个用户的需求提供一切。 STL的devise考虑因素包括：“对于几乎所有的用户来说足够快”，“对几乎所有的用户都有用”，“尽可能地提供例外安全”（“对于标准委员会来说足够小”写的很大，Stroustrup剔除了2/3的东西）。
我能想到的最简单的解决scheme是这样的：
// 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; }
这个解决scheme应该是O（M * N），其中M是唯一元素的数量，N是元素的总数量。
据我所知，在STL没有。 查阅参考 。
基于@ Corden的答案，但使用lambdaexpression式并删除重复项，而不是写在输出向量中
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 } );
考虑到你的input是在vector<int> foo你可以在这里使用remove来完成这个工作，那么如果你想缩小vector，只需要使用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），因为它在原地进行移除。
