set difference for duplicates in the second range, alternative remove_copy

Question

I have two arrays or vectors, say:

  int first[] = {0,0,1,1,2,2,3,3,3};
  int second[] = {1,3};

I would like to get rid of the 1s and 3s in the first set, set_difference can only get rid of the first occurrences of these values however this is not what I want to have.

Should I do this with remove_copy by iterating on the second range and each time remove one entry from the first set.

What would be the best way to do this in C++?

Answer 1

Write a specialised set_difference:

template <typename InputIterator1, typename InputIterator2, typename OutputIterator>
OutputIterator set_difference_any( InputIterator1 first1, InputIterator1 last1,
                                   InputIterator2 first2, InputIterator2 last2,
                                   OutputIterator result )
{
  while ( first1 != last1 && first2 != last2 )
    if ( *first1 < *first2 ) {
      *result = *first1;
      ++first1;
      ++result;
    } else if ( *first2 < *first1 ) {
      ++first2;
    } else {
      ++first1;
      //++first2; // this is the difference to set_difference
    }
  return std::copy( first1, last1, result );
}

Then apply it to the problem:

#include "set_difference_any.h"
#include <boost/range.hpp>
#include <iterator>
#include <vector>

std::vector<int> result;
set_difference_any( boost::begin( first ), boost::end( first ),
                    boost::begin( second ), boost::end( second ),
                    std::back_inserter( result ) );

This algorithm is linear (max. last1-first1 + last2-first2 comparisions)

Answer 2

Are you sure set_difference won't work? The standard in 25.3.5 says

This section defines all the basic set operations on sorted structures. They also work with multisets containing multiple copies of equivalent elements.

And the description of set_difference just says it gives you everything in first not in second, which is what you want.

Answer 3

You should write simple function or functional which returns true if element is in second and false otherwise (lets call it ok). And then use std::remove_if or std::remove_copy_if:

first.erase(std::remove_if(first.begin(), first.end(), ok));

P.S. considered that first is std::vector<int> and not array.