CODEWITHSUNDEEP
c++algorithmstlfind
Abruzzo Forte e Gentile
Abruzzo Forte e Gentile

Reputation: 14869

find first element within a range not included in another range

In STL I can use std::includes to check whether the second range is contained entirely in the first range.

The 2 ranges are sorted.

 std::includes( r1.begin(), r1.end(), rng2.begin(), r2.end()); // returns a bool

What can I do if I want the exact point where this failure occurs?

Essentially I am looking for the first elements in r2 that is NOT included in r1 or something that returns an iterator.

I can't find any STL algorithm for that.

Do I have to code myself that using find or there is already something?

Upvotes: 2

Views: 396

Answers (1)

4pie0
4pie0

Reputation: 29734

based on std::set_difference I have written something like this:

/*
* first difference of elements: element present in first container
* and not present in second
*/
template <class T>
T first_difference (T* first1, T* last1,
                                 T* first2, T* last2)
{
  while (first1!=last1 && first2!=last2)
  {
    if (*first1<*first2) { return *first1; }
    else if (*first2<*first1) ++first2;
    else { ++first1; ++first2; }
  }
  if ( first1 != last1 && first2 == last2) return *first1;
  return 0;
}

usage:

int main(int argc, char** argv) {

    int first[] = {5, 10, 15, 20, 25};
    int second[] = {50, 40, 30, 20, 10};

    std::sort(first, first + 5); //  5 10 15 20 25
    std::sort(second, second + 5); // 10 20 30 40 50

    int i = first_difference( first, first + 5, second, second + 5);
    assert( i == 5);
    return 0;
}

Upvotes: 1

Related Questions