如何使向量元素独特？(删除不相邻的重复项)

Question

我有一个包含很少非相邻重复项的向量.

举个简单的例子,考虑一下:

2 1 6 1 4 6 2 1 1

我试图vector通过删除不相邻的重复项并保持元素的顺序来使这个独特.

结果将是:

2 1 6 4 

我尝试的解决方案是:

1. 插入std :: set但这种方法的问题是它会扰乱元素的顺序.
2. 使用std :: sort和std :: unique的组合.但同样的订单问题.

3. 手动重复消除:

       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算法可以从向量中删除不相邻的重复项？它的复杂性是什么？

Answer 1

我想你会这样做:

我会在向量上使用两个迭代器:

第一个读取数据并将其插入临时集.

当读取数据不在集合中时,将其从第一个迭代器复制到第二个迭代器并递增它.

最后,您只将数据保留到第二个迭代器.

复杂度为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 ;
        }
    }
}

Answer 2

如果不使用临时性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.但是,使用代表性输入进行测量是唯一可以确定的方法.

Answer 3

问题是"是否有任何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修剪向量.

Answer 4

你可以使用以下方法删除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对此进行改进,或者如果值的范围足够小,则可以简单地使用数组或位阵.