Добавление элементов в вектор

Question

Мне нужно отсортировать 2 вектора (A и B), используя сортировку слиянием, и поместить отсортированные элементы в 3-й вектор (R).
На тесте с 3 элементами в A (1,3,5) и B:(2,4,6) мой код работает нормально, пока я не вставлю 4-й элемент.В этот момент мой код вылетает с векторным индексом из-за ошибки диапазона.

Я впервые использую векторы, но я думал, что функция push_back() изменяет размер вектора.Я догадываюсь, что целевой вектор (R) может содержать только 3 элемента, поэтому, когда я иду, чтобы вставить 4-й элемент, мой код падает.Нужно ли что-то делать, чтобы изменить размер R?

using namespace std;
#include <iostream>
#include <vector>


// combine two sorted lists A and B into R
// displays comparison every time it is done
void combine(vector<int> A, vector<int> B, vector<int>& R)
{
    int ia = 1;
    int ib = 1;
    int ir = 1;

    while (!A.empty() && !B.empty()) {
        if (A[ia] < B[ib]) {
            R.push_back(A[ia]);
            ia++;
            ir++;
        }
        else {
            R.push_back(B[ib]);
            ib++;
            ir++;
        }
    }
        if (!A.empty()) {
            for (int i = ia; i < A.size(); i++) {
                R.push_back(A[i]);
            }
        }
        else if (!B.empty()) {
            for (int i = ib; i < B.size(); i++) {
                R.push_back(B[i]);
            }
        }
        cout << "comparison" << endl;
        // be careful -- R comes in as an empty vector


}


int main()
{
    vector<int> L1;
    vector<int> L2;
    vector<int> L3;
    int N;  // how many elements in each of L1 and L2
    int e;  // for each element

    cout << "How many elements in each list?" << endl;
    cin >> N;

    cout << "List1" << endl;
    for (int i = 1; i <= N; i++)
    {
        cout << "element :"; cin >> e; L1.push_back(e);
    }

    cout << "List2" << endl;
    for (int i = 1; i <= N; i++)
    {
        cout << "element :"; cin >> e; L2.push_back(e);
    }


    combine(L1, L2, L3);


    cout << "The result is: ";
    for (int i = 0; i < N * 2; i++)
    {
        cout << L3[i];
    } cout << endl;

}// end of main

Answer 1

вектор A и B всегда не пустые, если только pop_front

просто как лайки,

if(A.at(0) < B.at(0)) {
    C.push_back(A.at(0));
    A.pop_front();
}

или, цикл до размера A и B

int ia = 0;
int ib = 0;
while(ia < A.size() && ib < B.size())
{
    if(A.at(ia) < B.at(ib))
    {
        C.push_back(A.at(ia));
        ia++;
    }
    // ...
}

Answer 2

Вы правы в точке: Я думал, что функция push_back() изменяет размер вектора.

Ошибка связана с неверным доступом к индексу в вашей программе.

В вашей программе ваше условие завершения цикла while равно while (!A.empty() && !B.empty()).Поскольку вы не удаляете какой-либо элемент для вектора A или B, условие завершения никогда не будет удовлетворять.Что приводит к бесконечному циклу и что также ведет к доступу неверного индекса в векторе A или B (в зависимости от того, из ia или ib, которые пересекли фактический размер соответствующего вектора).

Также обратите внимание на следующее:

• Вы начали обращаться к элементам с индекса 1, а не с 0. Индексы векторов начинаются с 0.
• Это условия if (!A.empty()) иif (!B.empty()) будет всегда true.Так как вы не удаляете элементы из вектора A и B.

Ниже приведен исправленный код.Вы можете увидеть, как он работает здесь :

#include <iostream>
#include <vector>
using namespace std;

// combine two sorted lists A and B into R
// displays comparison every time it is done
void combine(vector<int> A, vector<int> B, vector<int>& R)
{
    int ia = 0;
    int ib = 0;
    int sA = A.size();
    int sB = B.size();

    while ((ia < sA) && (ib < sB)) {
        if (A[ia] < B[ib]) {
            R.push_back(A[ia]);
            ia++;
        }
        else {
            R.push_back(B[ib]);
            ib++;
        }
    }
    while(ia < sA)
    {
        R.push_back(A[ia++]);
    }
    while(ib < sB)
    {
        R.push_back(B[ib++]);
    }
    cout << "comparison" << endl;
    // be careful -- R comes in as an empty vector
}

int main()
{
    vector<int> L1;
    vector<int> L2;
    vector<int> L3;
    int N;  // how many elements in each of L1 and L2
    int e;  // for each element

    cout << "How many elements in each list?" << endl;
    cin >> N;

    cout << "List1" << endl;
    for (int i = 1; i <= N; i++)
    {
        cout << "element :"; cin >> e; L1.push_back(e);
    }

    cout << "List2" << endl;
    for (int i = 1; i <= N; i++)
    {
        cout << "element :"; cin >> e; L2.push_back(e);
    }

    combine(L1, L2, L3);

    cout << "The result is: ";
    for (int i = 0; i < N * 2; i++)
    {
        cout << L3[i] << " | ";
    } cout << endl;
}// end of main

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

using namespace std;
#include <iostream>
#include <vector>


// combine two sorted lists A and B into R
// displays comparison every time it is done
void combine(const vector<int>& A, const vector<int>& B, vector<int>& R)
{
    auto itA = A.begin();
    auto itB = B.begin();

    while ( (itA != A.end()) && (itB != B.end()) )
    {
        if (*itA < *itB) 
        {
            R.push_back(*itA);
            itA++;
        }
        else 
        {
            R.push_back(*itB);
            itB++;
        }
    }
    while(itA != A.end())
    {
        R.push_back(*itA);
        itA++;
    }
    while(itB != B.end())
    {
        R.push_back(*itB);
        itB++;
    }
    cout << "comparison" << endl;
    // be careful -- R comes in as an empty vector
}


int main()
{
    vector<int> L1;
    vector<int> L2;
    vector<int> L3;
    int N;  // how many elements in each of L1 and L2
    int e;  // for each element

    cout << "How many elements in each list?" << endl;
    cin >> N;

    cout << "List1" << endl;
    for (int i = 0; i < N; i++)
    {
        cout << "element :"<<endl; cin >> e; L1.push_back(e);
    }

    cout << endl << "List2" << endl;
    for (int i = 0; i < N; i++)
    {
        cout << "element :"<<endl; cin >> e; L2.push_back(e);
    }

    combine(L1, L2, L3);


    cout << "The result is: ";
    for (int i = 0; i < N * 2; i++)
    {
        cout << L3[i]<<" | ";
    }

}// end of main

Answer 3

В вашем цикле вы проверяете, являются ли векторы пустыми, я думаю, вы должны вместо этого проверять, находятся ли их счетчики в диапазоне или что-то в этом роде.Например, если вектор A равен [1,2], а B равен [3,4,5] после двухкратного цикла и вставки вектора A, ia теперь будет выходить за пределы, но вы все равно дойдете до оператора if, где A [ia]по сравнению с B [ib] Я считаю, что это где вы выходите за пределы своего вектора.Также я считаю, что векторный индекс начинается с 0, это также может быть вашей проблемой.