为什么我的最终向量大小应该是原来的两倍，并且前导0? [英] Why is my final vector double the size it should be and have leading 0's?

问题描述

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

I am doing this small project for a class and I have pretty much finished it but for some reason my merged vector is double the size it should be and has leading 0's that shouldn't be there. The main function was written for us, we have to write the partition, quick sort, and multiway_merge functions. First, the program should take in the number of lists, number of integers in each list, and then the numbers that go in each list from the keyboard. Then we quick sort each of the lists using a quick sort and partition function. The pivot in the partition function should be the median of the first, middle, and last elements in the list. Once sorted, we use the multiway_merge function to merge the sorted lists. I have gotten it to sort the lists and merge them but for some reason I am getting a final vector that is double the size it should be and the first half of it are 0's. If you guys could help me figure this out, that would be great!

#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 值.

vector<int> output_list(n * m); initializes output_list to be size n*m and fills with 0's. You then push_back values after that.

您有3个选择:

1. 不要将 output_list 初始化为具有值.让程序在您 push_back 时动态地保留空间.

1. Don't initialize output_list to have values. Let the program reserve space on the fly as you push_back.

不要将 output_list 初始化为具有值，而是使用

Don't initialize output_list to have values, but increase its capacity using reserve.

根据需要初始化 output_list ，但不要在函数中 push_back .相反，请修改索引的值，而不要添加更多的值.

Initialize output_list as you have, but don't push_back in the function. Instead, modify the values of the indexes instead of adding more.

这篇关于为什么我的最终向量大小应该是原来的两倍，并且前导0?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！