为什么我的最终向量是应有大小的两倍并且有前导 0？

我正在为一个班级做这个小项目，我已经基本完成了它，但由于某种原因，我的合并向量是应有大小的两倍，并且有不应该存在的前导 0。 main函数是为我们编写的，我们必须编写分区、快速排序和multiway_merge函数。首先，程序应该获取列表的数量、每个列表中的整数数量，然后从键盘输入每个列表中的数字。然后我们使用快速排序和分区功能对每个列表进行快速排序。分区函数中的主元应该是列表中第一个、中间和最后一个元素的中位数。排序后，我们使用 multiway_merge 函数来合并排序后的列表。我已经得到它来对列表进行排序并合并它们，但由于某种原因，我得到的最终向量是应有大小的两倍，并且它的前半部分是 0。如果你们能帮我解决这个问题，那就太好了！

#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>
#include <queue>

using namespace std;

int partition(vector<int>& list, int first, int last) {
    // The pivot should be the median of the
    // first, middle, and last elements.
    int pivot;
    int index, smallIndex;
    int middle = floor(list.size() / 2);

    int arr[3] = {first, middle, last};
    int size = sizeof(arr) / sizeof(arr[0]);
    sort(arr, arr + size);

    swap(first, arr[1]);
    pivot = list[first];
    smallIndex = first;

    for(index = first + 1; index <= last; index++)
        if(list[index] < pivot) {
            smallIndex++;
            swap(smallIndex, index);
        }

    swap(first, smallIndex);
    return smallIndex;
}

void quicksort(vector<int>& list, int first, int last) {
    if(first == last)
        return;

    else {
        int pivotLocation = partition(list, first, last);
        quicksort(list, first, pivotLocation - 1);
        quicksort(list, pivotLocation + 1, last);
    }
}

void multiway_merge(vector<vector<int> >& input_lists, 
vector<int>& output_list) {
    int size = input_lists.size();
    int s = input_lists[0].size();
    priority_queue<int, vector<int>, greater<int> > minHeap;

    for(int i = 0; i < size; i++) {
        for(int j = 0; j < s; j++) {
            minHeap.push(input_lists[i][j]);

            if(minHeap.size() > size) {
                output_list.push_back(minHeap.top());
                minHeap.pop();
            }
        }
    }

    while(minHeap.size()) {
        output_list.push_back(minHeap.top());
        minHeap.pop();
    }
}

int main(int argc, char** argv) {
    int n, m;
    cin >> n >> m;

    vector<vector<int> > input_lists(n, vector<int>(m));

    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < m; ++j) {
            cin >> input_lists[i][j];
        }
    }

    // Quicksort k sublists
    for (int i = 0; i < input_lists.size(); ++i)
        quicksort(input_lists[i], 0, m-1);

    // Merge n input sublists into one sorted list
    vector<int> output_list(n * m);
    multiway_merge(input_lists, output_list);

    for (int i = 0; i < output_list.size(); ++i)
        cout << output_list[i] << " ";
    cout << endl;
}

vector<int> output_list(n * m);初始化output_list尺寸n*m并用 0 填充。然后是你push_back之后的值。

您有 3 个选择：

1. 不初始化output_list要有价值观。让程序在您进行操作时动态预留空间push_back.

2. 不初始化output_list拥有价值观，但要增加它capacity using reserve http://en.cppreference.com/w/cpp/container/vector/reserve.

3. 初始化output_list就像你一样，但不push_back在函数中。相反，修改索引的值而不是添加更多。