C ++ push_back в векторах

Question

Я построил рекурсивную функцию, которая считывает вектор в качестве входных данных и возвращает новый вектор, в котором переключаются каждые два последовательных элемента. Например, введите: 1 2 3 4 5 6 и выведите: 2 1 4 3 6 5. Чего я не понимаю, так это того, что когда я пишу функцию так:

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;
    }
}

я получаю 6 5 4 3 2 1. Я знаю, что vector::push_back() добавляет элементы в конце вектора, так почему бы не 2 1 4 3 6 5? Когда я написал это таким образом, он дал мне хороший ответ, хотя (2 1 4 3 6 5), но не знаю почему:

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;
    }
}

Функция main () такова:

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

Это легко исправить.

Проблема с вашим кодом заключается в том, что рекурсивный шаг неправильно переводит правильно сконструированный промежуточный результат в чуть больший. Вы хотели бы сделать:

// 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());

Это гарантирует, что если ваш список начинается с 1 2, он превратится в список с 2 1, за которым следует правильно обработанный хвост.

Ваш второй код работал, потому что вы обрабатывали последовательность в обратном порядке, поэтому ваш рекурсивный шаг был на самом деле правильным.

Answer 2

Полученный вами результат неверен, потому что при последнем вызове вашей функции вы возвращаете пустой вектор, а затем вы возвращаете sh в конце этого вектора вашу последнюю пару чисел, инвертированных, поэтому 6,5, так что вы продолжайте возвращаться в стек вызовов. Давайте посмотрим, что вы имеете при каждом вызове (первый вызов, второй вызов, e cc.):

1. v = [1,2,3,4,5,6] -> рекурсивный вызов
2. v = [3,4,5,6] -> рекурсивный вызов
3. v = [5,6] -> рекурсивный вызов
4. v = [] -> вернуть пустой вектор
5. rev = [] , pu sh возвращает первые два элемента v в обратном порядке, поэтому rev = [6,5] -> return rev
6. rev = [6,5], pu sh возвращает первые два элемента v в обратный порядок, т. е. rev = [6,5,4,3] -> return rev
7. rev = [6,5,4,3], pu sh назад первые два элемента v в обратном порядке, т. е. rev = [6,5,4,3,2,1]

По этой причине вам нужно сначала иметь вектор с обратными первыми двумя числами, а затем присоединить обработанный хвост, как предложено выше.

Обратите внимание, что вы создаете копии вектора каждый раз раз вы вызываете функцию. Вы можете создать обратную копию, не изменяя копию аргумента, заданного в качестве аргумента. Вместо этого я бы использовал итераторы, чтобы каждая функция «видела» меньшую часть исходного вектора, не касаясь его. Вот реализация:

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());
}

А вот основная:

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;
}