std: out_of_range dans mergesort

Question

d'abord je dois dire que je suis nouveau dans l'algorithme et C++. Après avoir écrit ce code dans vim et quand je débogue ce code C++, j'ai rencontré le error:std:out_of_range et je n'ai aucune idée d'où est l'erreur. donc je suis ici, et je suis très reconnaissant si je reçois votre help.thx

#include <iostream> 
#include <cstdio> 
#include <ctime> 
#include <cmath> 
#include <vector> 
#include <iterator> 
#include <algorithm> 
using namespace std; 
void merge(vector<int> &a, int first, int mid, int last) 
{ 
    a.resize(last - first + 1); 
    int n1 = mid - first + 1; 
    int n2 = last - mid; 
    vector<int> larray(n1, 0); 
    vector<int> rarray(n2, 0); 
    for (int i = 0; i != n1; ++i) 
     larray.at(i) = a.at(first + i); 
    for (int i = 0; i != n2; ++i) 
     rarray.at(i) = a.at(mid + 1 + i); 
    int i = 0; 
    int j = 0; 
    int k = 0; 
    while (i < n1 && j < n2) 
    { 
     if (larray.at(k) <= rarray.at(i)) 
      a[k++] = larray[i++]; 
     else 
      a[k++] = rarray[j++]; 
    } 
    while (i < n1) 
     a[k++] = larray[i++]; 
    while (j < n2) 
     a[k++] = rarray[j++]; 
} 

void MegerSort(vector<int> &a, int first, int last) 
{ 
    if (first < last) 
    { 
     int mid = (first + last)/2; 
     MegerSort(a, first, mid); 
     MegerSort(a, mid + 1, last); 
     merge(a, first, mid, last); 
    } 
} 

int main() 
{ 
    vector<int> array; 
    srand(unsigned(time(0))); 
    for (int i = 0; i != 10; ++i) 
     array.push_back(rand() % 10); 
    for (vector<int>::iterator it = array.begin(); it != array.end(); ++it) 
     cout<<*it<<" "; 
    cout<<endl; 
    MegerSort(array, 0, 9); 
    for (vector<int>::iterator it = array.begin(); it != array.end(); ++it) 
     cout<<*it<<" "; 
    return 0; 
} 

Answer 1

Je pense qu'il ya un problème a.resize(last - first + 1);. Tu ne devrais pas faire ça.

Supposons que vous appelez

void merge(vector<int> &a, int first, int mid, int last)

avec first = 6, mid = 7 et last = 8.

puis après le redimensionnement, a a une taille = (8 - 6 + 1) = 3.

Donc cela va être

de problèmes

rarray.at(i) = a.at(mid + 1 + i); vous voyez mid + 1 = 8