与矢量和数组不同的结果

Question

我写了两个几乎相同的代码片段,区别在于第一个使用数组而第二个使用向量.

使用数组:

int merge_count(int toMerge[], int arrSize, int lo, int mid, int hi)
{
    int aux[arrSize];
    for (int k = 0; k < arrSize; k++)
        aux[k] = toMerge[k];

    int i = lo, j = mid+1;
    int numinversions = 0, inversionpointer = mid - lo + 1;
    for (int k = lo; k <= hi; k++)
    {
        if (i > mid) {toMerge[k] = aux[j]; j++;}
        else if (j > hi) {toMerge[k] = aux[i]; i++;}
        else if (aux[j] < aux[i]) {toMerge[k] = aux[j]; j++; numinversions += inversionpointer;}
        else {toMerge[k] = aux[i]; i++; inversionpointer--;}
    }

    return numinversions;
}


int sort_count(int toSort[], int arrSize, int lo, int hi)
{
    if (hi <= lo) return 0;
    int mid = (lo + hi)/2;
    int numInversions = 0;
    numInversions += sort_count(toSort, arrSize, lo, mid);
    numInversions += sort_count(toSort, arrSize,  mid+1, hi);
    numInversions += merge_count(toSort, arrSize, lo, mid, hi);
    return numInversions;
}

int sort_count(int toSort[], int numElem)
{
    int lo = 0, hi = numElem-1;
    return sort_count(toSort, numElem, lo, hi);
}


int main(int argc, const char * argv[])
{
    int x[] = {3, 7, 10, 14, 18, 9, 2, 11, 16, 17, 23, 25};
    cout << sort_count(x, 12);
    return 0;
}

使用向量:

int merge_count(vector <int> toMerge, int arrSize, int lo, int mid, int hi)
{
    int aux[arrSize];
    for (int k = 0; k < arrSize; k++)
        aux[k] = toMerge[k];

    int i = lo, j = mid+1;
    int numinversions = 0, inversionpointer = mid - lo + 1;
    for (int k = lo; k <= hi; k++)
    {
        if (i > mid) {toMerge[k] = aux[j]; j++;}
        else if (j > hi) {toMerge[k] = aux[i]; i++;}
        else if (aux[j] < aux[i]) {toMerge[k] = aux[j]; j++; numinversions += inversionpointer;}
        else {toMerge[k] = aux[i]; i++; inversionpointer--;}
    }

    return numinversions;
}


int sort_count(vector <int> toSort, int arrSize, int lo, int hi)
{
    if (hi <= lo) return 0;
    int mid = (lo + hi)/2;
    int numInversions = 0;
    numInversions += sort_count(toSort, arrSize, lo, mid);
    numInversions += sort_count(toSort, arrSize,  mid+1, hi);
    numInversions += merge_count(toSort, arrSize, lo, mid, hi);
    return numInversions;
}

int sort_count(vector <int> toSort, int numElem)
{
    int lo = 0, hi = numElem-1;
    return sort_count(toSort, numElem, lo, hi);
}

int main(int argc, const char * argv[])
{   
    vector <int> x = {3, 7, 10, 14, 18, 9, 2, 11, 16, 17, 23, 25};
    cout << sort_count(x, 12);
    return 0;
}

两个代码完全相同时,除了所有我所做的是改变每种类型的int arr[]到vector <int> arr合并和排序功能之内.然而,这两个代码产生不同的结果,第一个使用数组输出13,而第二个使用向量输出15.

13是预期的结果,但使用向量不给出该结果.为什么会出现这种奇怪的行为？

Answer 1

您按值传递向量.因此,您在merge_count函数中所做的更改不会反映在原始向量中.

由于数组在传递给函数时会被衰减为指针,因此您对地址位置所做的更改实际上也是在原始数组中完成的.

尝试通过引用传递向量.