combine unique and set_difference

Hi,
I want to combine std::unique and std::set_difference into one single procedure.

For instance, I have now this

Code:

---

// A & B are both already sorted

new_end = std::unique(A->begin(), A->end());

std::set_difference(A->begin(), new_end(), B->begin(), B->end(), C->begin())

//I want to create a single produce mixing both, so that while scanning A and filtering out duplicates, I could also get the elements that are present in A, but not in the B.


template <class ForwardIterator>
ForwardIterator unique ( ForwardIterator first, ForwardIterator last ) {
  ForwardIterator result=first;
  while (++first != last) {
    if (!(*result == *first)) 
      *(++result)=*first;
  }
  return ++result;
}

template <class InputIterator1, class InputIterator2, class OutputIterator>
OutputIterator set_difference ( InputIterator1 first1, InputIterator1 last1,
                                InputIterator2 first2, InputIterator2 last2,
                                OutputIterator result ) {
  while (first1!=last1 && first2!=last2) {
    if (*first1<*first2) *result++ = *first1++;
    else if (*first2<*first1) first2++;
    else { first1++; first2++; }

  }
  return copy(first1,last1,result);
}

---

I would appreciate some help with this

What have you tried so far? Do you have any ideas on it?

I would try expanding those implementations into something more obvious and readable so you get a better understanding of what is going on. For example, the implementation of unique uses the variable "first" but treats it like the "current" value as it iterates over the range. So maybe add a new variable called "current" and initialize it with first, then use current in the loop. That might make it easier to understand what is going on in that loop. If you do that a few times and expand some of the other statements, it might become clearer which steps to take to combine them.

I was trying combine them by doing the following, but is not correct yet

Code:

---

template <class InputIterator1, class InputIterator2, class OutputIterator>
OutputIterator unique_difference(InputIterator1 first1, InputIterator1 last1,
                                InputIterator2 first2, InputIterator2 last2,
                                OutputIterator result ) {
 
 
  InputIterator1 current=first1;
 
  while (first1!=last1 && first2!=last2) {

    if (!(*current == *first1)) {
      *(++current)=*first1; 
    } 
   
    if (*first1<*first2) {
      *result++ = *first1++;
    }
    else
      if (*first2<*first1)
        first2++;
      else {
        first1++;
        first2++;
      }   
  }
 
 
  return copy(first1,last1,result);
}

---

any idea as how to correct it?

Follow the set_difference algorithm. Notice that in each iteration of the loop, it might do something as simple as increment either first1 or first2. So I would consider adding code to check if the current value of first1 duplicates either the next value or the previous value, and if it does I'd increment it and continue.

So basically you'd be taking almost the exact same code from the set_difference function, and then just adding a single check in the beginning of the loop to skip duplicates. Since you know the ranges are sorted, you can just skip the duplicate and continue (potentially multiple times).

Your attempt above is actually similar to that, but you added the current variable without using it later, so I don't think that first if statement accomplishes anything. You don't have to use "current" if you don't want to, that was just an idea to help you understand the steps better. You need a better mechanism for comparing the first1 value to either the next or the previous value and skipping the duplicate.

Hi thanks for the reply,
I came up with the following, seems to be working, but I'd like a second opinion

Code:

---

template <class InputIterator1, class InputIterator2, class OutputIterator>
OutputIterator my_set_difference ( InputIterator1 first1, InputIterator1 last1,
                                  InputIterator2 first2, InputIterator2 last2,
                                  OutputIterator result ) {
  InputIterator1 next = first1;
 
  while (first1!=last1 && first2!=last2) {

    next = first1;
    next++;   
   
    while (next!=last1 && *first1 == *next){         
      first1++;
      next++;     
    }
   
   
    if (*first1<*first2) {
      *result++ = *first1++;
    }
    else
      if (*first2<*first1)
        first2++;
      else {
        first1++; first2++;
      }
  }
 
  return copy(first1,last1,result);
}

---

I didn't give it a thorough look (I've got to go home now), but at a quick glance it looks good, and that's the idea I had in mind.