Extracting duplicates from a vector into a new one

[chrisloeys]

Hello all,

Suppose I have a vector which contains the elements {6, 1, 3, 4, 1, 7, 5, 3, 7}. What I've been trying to do is extract the duplicate values, in this case {1, 1, 3, 3, 7, 7}, and make that into a new vector. The old vector still has to remain intact however. I really can't figure out how I would tackle this efficiently, and searching around the internet I've only found examples where they delete the duplicates from a vector.

Does anyone have a clever idea how I could do this? I've really been breaking my head around how to do this in an elegant way.

[Duthomhas]

#include <algorithm>
#include <iterator>
#include <iostream>
#include <vector>

//----------------------------------------------------------------------------
// Remove unique elements to the end of the sorted range. Returns an iterator
// to the new end of the range.
template <typename ForwardIterator>
ForwardIterator
anti_unique( ForwardIterator begin, ForwardIterator end )
  {
  ForwardIterator result = begin;
  ForwardIterator first_equal = begin;
  size_t          count_equal = 1;

  while (++begin != end)
    {
    if (*begin == *first_equal) ++count_equal;
    else
      {
      if (count_equal > 1)
        {
        result = std::copy( first_equal, begin, result );
        }
      first_equal = begin;
      count_equal = 1;
      }
    }
  if (count_equal > 1)
    {
    result = std::copy( first_equal, begin, result );
    }
  return result;
  }

//----------------------------------------------------------------------------
int main()
  {
  using namespace std;

  int _xs[] = { 6, 1, 3, 4, 1, 7, 5, 3, 7 };
  vector <int> xs( _xs, _xs + (sizeof( _xs ) / sizeof( int )) );

  vector <int> ys( xs );         // copy
  sort( ys.begin(), ys.end() );  // sort

  ys.erase( anti_unique( ys.begin(), ys.end() ), ys.end() );

  cout << "non-unique elements: ";
  copy( ys.begin(), ys.end(), ostream_iterator <int> ( cout, " " ) );
  cout << endl;

  return 0;
  }

Enjoy.

[edit]
Sorry, some notes for you.
You cannot do it efficiently unless you first sort the range. Hence, copy and sort is the first thing we do. Then we apply an algorithm that does the opposite of what std::unique() does.

Hope this helps.

[chrisloeys]

Thanks a lot, this is exactly what I've been looking for!

[Duthomhas]

One more note: If you want to maintain relative order of equivalent elements, sort with std::stable_sort(). The algorithm assumes that your equivalence predicate (the == operator) may not be the default, 'exactly equal' predicate. (I could have made it a bit simpler if it were safe to assume that.)

Glad to be of help. :O)