Extracting duplicates from a vector into a new one

Nov 1, 2012 at 10:50pm
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.
Nov 2, 2012 at 12:27am
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
#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.
Last edited on Nov 2, 2012 at 12:28am
Nov 2, 2012 at 1:09am
Thanks a lot, this is exactly what I've been looking for!
Nov 2, 2012 at 1:17am
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)
Topic archived. No new replies allowed.