C++ Recursive Union, Intersection, and Difference

Question

This is a homework assignment, and I don't really know how to do this. I would normally create v3 = v1, then increment through v2, via i, and check if v2's elements are in v3. If not, I would add them to v3. But I can't create v3 outside of the method and if I try to create it inside the method, it would just reset itself. Can anyone help me please?

Here is the code I have for them and their wrapper functions thus far (it's just the skeleton):

// returns a new vector; every element in v1 and every element in v2 are also in this new vector
// if an element appears in both v1 and v2, it is only added once to the new vector
template <typename T> vector<T> vec_union(vector<T> &v1, vector<T> &v2)
{
    return v1;
}

template <typename T> vector<T> vec_union(vector<T> &v1, vector<T> &v2, unsigned i)
{
    return v1;
}

// returns a new vector; every element that is in both v1 and v2 are also in this new vector
// there are no duplicates in v1 and v2
template <typename T> vector<T> intersection(vector<T> v1, vector<T> v2)
{
    return v1;
}

template <typename T> vector<T> intersection(vector<T> v1, vector<T> v2, unsigned i)
{
    return v1;
}

// returns a new vector; every element that is in v1 but not v2 are also in this new vector
// there are no duplicates in v1 and v2
template <typename T> vector<T> difference(vector<T> v1, vector<T> v2)
{
    return v1;
}


template <typename T> vector<T> difference(vector<T> v1, vector<T> v2, unsigned i)
{
    return v1;
}

Answer 1

You create v3 by fowarding the T template parameter and passing it to vector like I have done below:

vector<T> v3;

I have implemented your vec_union function for you. Note the following: I have created v3 inside the function. I have returned v3, which results in a copy of v3 which the outside code will get, when the caller calls vec_union.

template <typename T> vector<T> 
vec_union(vector<T> &v1, vector<T> &v2)
{
  if ( v2.empty() )
    return v1;

  vector<T>::iterator found = std::find(v1.begin(), v1.end(), v2.back());
  if ( found == v1.end() )
  {
    // all good, element not already in v1, so insert it.
    T value = v2.back();
    v1.push_back(value);
    v2.pop_back(); // remove back element
    return vec_union(v1, v2);
  }
  else
  {
    // element was already in v1, skip it and call vec_union again
    v2.pop_back(); // remove back element
    return vec_union(v1, v2);
  }
}

Note that my answer modifies v1 and v2. I assumed this is what your teacher expected in order to achieve a recursive implementation that isn't ridiculously inefficient by repeatedly copying v1 and v2 around.

You call vec_union like so:

vector<int> firstVector;
vector<int> secondVector;
vector<int> unionVector = vec_union(firstVector, secondVector);