为什么我在合并排序中得到向量下标超出范围错误？

Question

void merge(vector<int> dst,vector<int> first,vector<int> second) 
{ 
    int i=0,j=0; 

    while(i<first.size()&&j<second.size()) 
    { 
     if(first[i]<second[j]) 
     { 
      dst.push_back(first[i]); 
      i++; 
     } 
     else 
     { 
      dst.push_back(second[j]); 
      j++; 
     } 
    } 
    while(i<first.size() 
    dst.push_back(first[i++]); 

    while(j<second.size()) 
    dst.push_back(second[j++]); 
} 

void mergeSort(vector<int> &a) 
{ 
    size_t sz = a.size(); 
    cin.get(); 
    if(sz>1) 
    { 
     vector<int> first(&a[0],&a[sz/2]); 
     vector<int> second(&a[(sz/2)+1],&a[sz-1]); 

     mergeSort(first); 
     mergeSort(second); 

     merge(a,first,second); 
    } 
} 

void MergeSort(int* a,size_t size) 
{ 
    vector<int> s(&a[0],&a[size-1]); 
    mergeSort(s); 
} 

有人能帮助我这个代码有什么问题吗？我得到矢量下标超出范围错误。

Answer 1

您的子矢量指定不正确。
记住迭代器指定从开始到结尾的一个。

所以这会错过向量中的中间元素和最后一个元素。
并且还未定义长度的非常短的矢量2

vector<int> first(&a[0],&a[sz/2]); 
    vector<int> second(&a[(sz/2)+1],&a[sz-1]); 

试想一下，如果一个是矢量{A，B，C，d}

first: {A,B} 0 -> 2 (where 2 is one past the end so index 0 and 1_ 
    second: {}  3 -> 3 (Since one past the end equals the start it is empty} 

或尝试更大的矢量：{A ，B，C，d，E，F，G，H，I}

first: {A, B, C, D} 0 -> 4 (4 is one past the end so index 0,1,2,3) 
    second: {F, G, H}  5 -> 8 (8 is one past the end so index 5,6,7) 

，或者尝试使用更小的矢量：{A，B}

first: {A} 0 -> 1 
    second: {BANG} 2 -> 1 

应该是：

int* st = &a[0]; 
    // Using pointer arithmatic because it was too late at night 
    // to work out if &a[sz] is actually legal or not. 
    vector<int> first (st,  st+sz/2]); // sz/2 Is one past the end. 
    vector<int> second(st+sz/2, st+sz ); // First element is sz/2 
              // one past the end is sz 

传递到合并的载体（）。 dst参数必须通过引用传递，因为它是out参数。但是还要注意，第一个和第二个参数是常量，所以我们可以通过const引用传递（以避免复制步骤）。

void merge(vector<int>& dst,vector<int> const& first,vector<int> const& second) 

而且合并功能：

是推动价值为DST。但是dst已经完全来自数据。因此，在我们进行合并之前，必须清除目标。

mergeSort(first); 
    mergeSort(second); 

    // Must clear a before we start pushing stuff into. 
    a.clear(); // Add this line. 
    merge(a,first,second); 

Answer 2

如果sz == 2，&a[(sz/2)+1]会尝试取一个[2]的地址，这会给你这个错误。

Answer 3

马丁是正确的，问题是附配向量的构造器：

原始向量：1 9 7 9

iter1：2， iter2：8

vector<int> v(iter1, iter2); //new vector: 2 7 2 1 9 

http://www.cppreference.com/wiki/stl/vector/vector_constructors

和谈论合并排序等排序算法，从来就发现了一个非常有用的网站：

http://www.sorting-algorithms.com/merge-sort