set_difference()

[danciu]

In a school test, the code below is a:
a. runtime error
or
b.0,3,9,2,0,0,0,
thank you.

#include <vector>
#include <iostream>
#include <algorithm>
using namespace std;
void printer(int i) {        cout << i << ", ";	}
int main() {
        int mynumbers1[]={3, 9, 0, 2};
        int mynumbers2[]={6, 1, 4, 5};
        vector<int> v1(7);
        sort(mynumbers2, mynumbers2 + 3);
        sort(mynumbers1, mynumbers1 + 3);//LINE I
        set_difference(mynumbers1, mynumbers1+4, mynumbers2, mynumbers2+4, v1.begin());//LINE II
        for_each(v1.begin(), v1.end(), printer);        return 0;	}

[Peter87]

If you are not allowed to run the code you should step through each line, one by one, and think what will be the content of the arrays and the vector after each step.

Note that a runtime error is an error that happens when the program runs. This means you will not have to worry about trivial syntax errors (such as a missing semicolon or a misspelled function name) because that would give you an error at compile time, not at runtime.

[danciu]

Thank you Peter87,
If I run the code I will get the b answer, but at line 10 and 11 is sorted just a part of arrays and then we apply set_diference to the whole arrays, is not correct. My question is, in a school test what is the right answer a or b?

[Peter87]

You're right. The arrays should be sorted before using set_difference. I think this is considered a runtime error, even though it might not give you an error message, because there is no guarantee that it will work. It's simply undefined behaviour.

[Chervil]

From the reference pages of this site:
http://www.cplusplus.com/reference/algorithm/set_difference/

cplusplus_com wrote:

The behavior of this function template is equivalent to:

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; ++result; ++first1; }
    else if (*first2<*first1) ++first2;
    else { ++first1; ++first2; }
  }
  return std::copy(first1,last1,result);
}

By referring to that documentation, it is possible to step through the code line by line to see exactly what happens.

[Peter87]

The C++ standard doesn't specify the exact implementation. The cplusplus.com reference page probably means it's equivalent to that piece of of code under the assumption that the preconditions are fulfilled (i.e. the ranges [first1,last1) and [first2,last2) are sorted).

[Chervil]

Nevertheless, the given equivalent code gives a defined outcome in this specific case.

My understanding of the purpose of such equivalent code is to not go into the intricacies of any particular compiler implementation, but to allow the functioning of the algorithm to be understood in terms which might be considered as in effect pseudocode for that algorithm.