STLAlgorithmExtensions/NonUniqueCopy

Given: 1,2,2,3,4,4,4,4,4,5
Result: 2,4 (These items were duplicated)

Presented below is a fairly efficient algorithm, given the iterator types supplied, solving this somewhat tricky problem. As with unique_copy, the initial iterator range is assumed to represent a sequence in either non-ascending or non-descending order, otherwise the behavior is undefined. As with unique_copy, an iterator one past the end of the output range is returned:

template<typename InputIterator, typename OutputIterator>
OutputIterator nonunique_copy(InputIterator first1, InputIterator last1, OutputIterator first2)
{
  if (first1!=last1) // Test for empty range
    for (InputIterator prev(first1++);first1!=last1;++prev,++first1)
      if (*first1==*prev) // Test if current pair is not unique
        {
        *first2++=*first1; // Store in output sequence
        for (;;) // Find next set of distinct elements 
          {
          prev=first1++;
          if (first1==last1) // End of input range hit, done
            return first2;
          if (!(*first1==*prev)) // Next non-unique pair found, skip and look for next dupe
            break;
          }
        }

  return first2;
}

template<typename InputIterator, typename OutputIterator, typename BinaryPredicate>
OutputIterator nonunique_copy(InputIterator first1, InputIterator last1, OutputIterator first2, BinaryPredicate pred)
{
  if (first1!=last1) // Test for empty range
    for (InputIterator prev(first1++);first1!=last1;++prev,++first1)
      if (pred(*first1,*prev)) // Test if current pair is not unique
        {
        *first2++=*first1; // Store in output sequence
        for (;;) // Find next set of distinct elements 
          {
          prev=first1++;
          if (first1==last1) // End of input range hit, done
            return first2;
          if (!pred(*first1,*prev)) // Next non-unique pair found, skip and look for next dupe
            break;
          }
        }

  return first2;
}

Sample code usage, with std:: omitted for brevity:

int main()
{	
  int nums[]={1,2,2,3,4,4,4,4,4,5};
  vector<int> nonUniqueNums; // set<int> could have been used instead, since the resulting elements are unique
  
  nonunique_copy(nums,nums+sizeof(nums)/sizeof(int),back_inserter(nonUniqueNums));
  
  std::copy(nonUniqueNums.begin(),nonUniqueNums.end(),ostream_iterator<int>(cout,","));
  std::cout << '\n';  
}

Output:

Enjoy,

-- People/Michael Goldshteyn