C++ push_back in vectors

Question

I built a recursive function that reads a vector as input and returns a new vector in which every two consecutive elements are switched. For example input: 1 2 3 4 5 6 and output: 2 1 4 3 6 5. The thing I don't get is that when I write the function this way:

vector<int> reverse(vector<int> v) {
 if (v.size() < 2)
 return v;
 else
 {
 int pos1 = v.at(0); //= 1
 int pos2 = v.at(1); //= 2
 v.erase(v.begin()); //v = 2 3 4 5 6
 v.erase(v.begin()); //v = 3 4 5 6
 vector<int> rev = reverse(v);
 rev.push_back(pos2); //rev = 2
 rev.push_back(pos1); //rev = 2 1
 return rev;
 }
}

i get 6 5 4 3 2 1. I know the vector::push_back() adds the elements at the end of the vector, so why not 2 1 4 3 6 5? When I wrote it this way it gave me the good answer though (2 1 4 3 6 5) but idk why:

vector<int> reverse(vector<int> v) {
 if (v.size() < 2)
 return v;
 else
 {
 int pos1 = v.at(v.size() - 2); //= 5
 int pos2 = v.at(v.size() - 1); //= 6
 v.pop_back(); //v = 1 2 3 4 5
 v.pop_back(); //v = 1 2 3 4
 vector<int> rev = reverse(v); //call the recursive function
 rev.push_back(pos2); //rev = 5
 rev.push_back(pos1); //rev = 6 5
 return rev;
 }
}

The main() function is this:

int main() {
 vector<int> w;
 int zahl;
 cout << "Please give the vector or any letter to end the input: "<< endl;
 while (cin >> zahl)
 {
 w.push_back(zahl);
 }
 for (int elem : reverse(w))
 {
 cout << elem << ", ";
 }
 return 0;
}

Answer 1

It's an easy fix.

The problem with your code is that the recursive step does not correctly translate a correctly constructed sub-result to a slightly larger one. You would want to do:

// Correctly create the head of the result.
vector<int> rev = {pos2, pos1};
// Now you want to handle the tail, and assuming the output of reverse
// is correct for smaller lists, this would be achieved by appending
// the rest.
const auto sub = reverse(v);
rev.insert(rev.end(), sub.begin(), sub.end());

This ensures that if your list starts with 1 2, it would turn into a list with 2 1, followed by a correctly processed tail.

Your second code worked because you were processing the sequence in reverse, so your recursive step was in fact correct.

Answer 2

The result you obtain is incorrect because in the last call to your function you return an empty vector, and then you push at the back of this vector your last pair of numbers inverted, so 6,5, so you do proceding back in the call stack. Let's have a look to what you have at every call (first call, second call, ecc.):

1. v=[1,2,3,4,5,6] ->recursive call
2. v=[3,4,5,6] ->recursive call
3. v=[5,6] ->recursive call
4. v=[] ->return empty vector
5. rev=[], push back the first two elements of v in reverse order, so rev=[6,5] ->return rev
6. rev=[6,5], push back the first two elements of v in reverse order, so rev=[6,5,4,3] ->return rev
7. rev=[6,5,4,3], push back the first two elements of v in reverse order, so rev=[6,5,4,3,2,1]

For this reason, you need first to have a vector with the first two numbers reversed and then attach the processed tail, as suggested above.

Please note that you are constructing copies of the vector every time you call the function. You can create a reversed copy without modifying the copy of the argument given as argument. I would use iterators instead, so that every time your function "sees" a smaller portion of the original vector, without touching it. Here an implementation:

vector<int> reverse(vector<int>::const_iterator begin, vector<int>::const_iterator end) {
 if (begin==end-1) //the vector has an odd number of elements, let's append the last element
 return vector<int>(1, *(end-1));
 else if(begin>=end) //the vector has en even number of elements
 return vector<int>();
 else
 {
 vector<int> pairWiseReversed({*(begin+1), *begin});
 vector<int> tail=reverse(begin+2, end);
 pairWiseReversed.insert(pairWiseReversed.end(), tail.begin(), tail.end());
 return pairWiseReversed;
 }
}
vector<int> buildReversed(const vector<int>& input){
 return reverse(input.begin(), input.end());
}

And here a main:

int main() {
 vector<int> v{1,2,3,4,5,6};
 cout<<"Input vector"<<endl;
 for(auto n:v)
 cout<<n<<" ";
 cout<<endl;
 vector<int> res=buildReversed(v);
 cout<<"Output vector"<<endl;
 for(auto n:res)
 cout<<n<<" ";
 cout<<endl;
 return 0;
}