通过引用传递向量使迭代算法运行不同

Question

这个让我很困惑。我正在用 C++ 实现荷兰国旗问题。我忘记了最初通过引用传递我的数组，但在每一步都显示了数组，这帮助我得出结论，我的算法工作正常。为了修复 vector 最终没有被分区的微小错误，我更改了函数定义以将 vector 作为参考传递，这不知何故产生了错误。

我以前从未遇到过这样的事情。代码不是递归的，因此虽然函数是运行，但它是向量副本上的运行还是实际向量上的运行并不重要。

代码如下：

#include<iostream>
#include<vector>
#include<algorithm>
#include<iomanip>

using namespace std;

void optArr(vector<int> arr){
    for(auto i: arr){
        cout<<setw(3)<<i<<" ";
    }
    cout<<endl;
}

void _partition(vector<int> arr, int lo, int hi, int &i, int &k){  //Vector passed by value
    i=lo-1, k=hi+1;
    int ptr=lo, pivot=arr[hi];
    while(ptr<k){
        optArr(arr);
        cout<<"i: "<<i<<" ptr: "<<ptr<<" k: "<<k<<endl;
        if(arr[ptr]<pivot){
            swap(arr[++i],arr[ptr++]);
        }else if(arr[ptr] == arr[pivot]){
            ptr++;
        }else{
            swap(arr[--k],arr[ptr]);
        }
    }
}



int main(){
    vector<int> arr = {57,22,85,17,11,04,17,93,1,17,25,17};
    int i,k;
    _partition(arr, 0, arr.size()-1, i, k);
    optArr(arr);
    cout<<"i: "<<i<<" ptr: "<<0<<" k: "<<k<<endl;

    return 0;
}

而向量按值传递时的输出：

 57  22  85  17  11   4  17  93   1  17  25  17
i: -1 ptr: 0 k: 12
 17  22  85  17  11   4  17  93   1  17  25  57
i: -1 ptr: 0 k: 11
 17  22  85  17  11   4  17  93   1  17  25  57
i: -1 ptr: 1 k: 11
 17  25  85  17  11   4  17  93   1  17  22  57
i: -1 ptr: 1 k: 10
 17  17  85  17  11   4  17  93   1  25  22  57
i: -1 ptr: 1 k: 9
 17  17  85  17  11   4  17  93   1  25  22  57
i: -1 ptr: 2 k: 9
 17  17   1  17  11   4  17  93  85  25  22  57
i: -1 ptr: 2 k: 8
  1  17  17  17  11   4  17  93  85  25  22  57
i: 0 ptr: 3 k: 8
  1  17  17  17  11   4  17  93  85  25  22  57
i: 0 ptr: 4 k: 8
  1  11  17  17  17   4  17  93  85  25  22  57
i: 1 ptr: 5 k: 8
  1  11   4  17  17  17  17  93  85  25  22  57
i: 2 ptr: 6 k: 8
  1  11   4  17  17  17  17  93  85  25  22  57
i: 2 ptr: 7 k: 8
 57  22  85  17  11   4  17  93   1  17  25  17
i: 2 ptr: 0 k: 7

可以看到输出是正确的，一直到最后一个，是通过main函数调用的。当我看到这个时，我决定通过将 _partition 签名修改为：void _partition(vector<int> &arr, int lo, int hi, int &i, int &k)

来通过引用传递向量

这产生了以下输出：

 57  22  85  17  11   4  17  93   1  17  25  17
i: -1 ptr: 0 k: 12
 17  22  85  17  11   4  17  93   1  17  25  57
i: -1 ptr: 0 k: 11
 25  22  85  17  11   4  17  93   1  17  17  57
i: -1 ptr: 0 k: 10
 17  22  85  17  11   4  17  93   1  25  17  57
i: -1 ptr: 0 k: 9
  1  22  85  17  11   4  17  93  17  25  17  57
i: -1 ptr: 0 k: 8
  1  22  85  17  11   4  17  93  17  25  17  57
i: 0 ptr: 1 k: 8
  1  93  85  17  11   4  17  22  17  25  17  57
i: 0 ptr: 1 k: 7
  1  17  85  17  11   4  93  22  17  25  17  57
i: 0 ptr: 1 k: 6
  1   4  85  17  11  17  93  22  17  25  17  57
i: 0 ptr: 1 k: 5
  1   4  85  17  11  17  93  22  17  25  17  57
i: 1 ptr: 2 k: 5
  1   4  11  17  85  17  93  22  17  25  17  57
i: 1 ptr: 2 k: 4
  1   4  11  17  85  17  93  22  17  25  17  57
i: 2 ptr: 3 k: 4
  1   4  11  17  85  17  93  22  17  25  17  57
i: 2 ptr: 0 k: 3

如您所见，从第三行输出开始就表现异常。对于这样一个含糊的问题，我深表歉意，但我不知道还能如何寻找解决这种不寻常问题的方法。

Answer 1

在您的示例中，pivot == 17 和 arr[pivot] 通过越界访问索引表现出未定义的行为。

通过引用传递向量使迭代算法运行不同

Passing vector by reference makes iterative algorithm run differently

reference

vector

pass-by-reference

c++11

通过引用传递向量使迭代算法 运行 不同

Passing vector by reference makes iterative algorithm run differently

reference

vector

pass-by-reference

c++11

通过引用传递向量使迭代算法运行不同