如何有效地保留重复？

Question

给定STL向量,仅按排序顺序输出重复项,例如,

INPUT : { 4, 4, 1, 2, 3, 2, 3 }
OUTPUT: { 2, 3, 4 }

该算法很简单,但目标是使其与std :: unique()一样高效.我天真的实现就地修改了容器:

我天真的实施:

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);
 }
}

如果你能使这个更高效,优雅或一般,请告诉我.例如,自定义排序算法,或第二个循环中的复制元素,以消除erase()调用.

Answer 1

我第一次尝试失败了,假设std::unique将所有重复项移动到范围的末尾(它没有).哎呀.这是另一个尝试:

这是一个实现not_unique.它消除,在排序的范围只出现一次的任何元件和出现一次以上的所有元素的重复.因此,结果范围是出现不止一次的唯一元素列表.

该函数具有线性复杂度,并且在该范围内进行单次传递(std::unique具有线性复杂度). It必须满足前进迭代器的要求.返回结果范围的结尾.

template <typename It>
It not_unique(It first, It last)
{
    if (first == last) { return last; }

    It new_last = first;
    for (It current = first, next = ++first; next != last; ++current, ++next)
    {
        if (*current == *next)
        {
            if (current == new_last)
            {
                ++new_last;
            }
            else
            {
                *new_last++ = *current;
                while (next != last && *current == *next)
                {
                    ++current;
                    ++next;
                }
                if (next == last)
                    return new_last;
            }
        }
    }
    return new_last;
}

Answer 2

比以前的条目更短、更接近 STL。假设输入已排序。

#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 >() );
}