Передача вектора по ссылке заставляет итерационный алгоритм работать по-другому - PullRequest
Новая
       40

Передача вектора по ссылке заставляет итерационный алгоритм работать по-другому

0 голосов
/ 31 мая 2018

Это меня озадачило.Я реализовывал проблему голландского национального флага в C ++.Сначала я забыл передать свой массив по ссылке, но отображал массив на каждом шагу, что помогло мне заключить, что мой алгоритм работал нормально.Чтобы исправить мелкую ошибку, когда вектор не был окончательно разделен, я изменил определение функции, передав вектор в качестве ссылки, что каким-то образом выдало ошибку.

Я никогда раньше не сталкивался с чем-то подобным.Код не является рекурсивным, поэтому во время работы функции не должно иметь значения, выполняется ли она на копии вектора или на фактическом векторе.

Вот код: 

#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

Вы можете видеть, что вывод правильный, вплоть до последнего, который вызывается через главную функцию.Когда я увидел это, я решил передать вектор по ссылке, изменив подпись _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

Как вы можете видеть, этоведет себя ненормально прямо с третьей строки вывода.Я прошу прощения за такой неопределенный вопрос, но я не знаю, как еще искать решение такой необычной проблемы.

1 Ответ

0 голосов
/ 31 мая 2018

В вашем примере pivot == 17 и arr[pivot] демонстрируют неопределенное поведение при доступе к индексу за пределами.

...