0

ベクトル反復子を使用して整数のベクトルをソートするには、MergeSort を実装する必要があります。実装しましたが、次のエラーが発生します: Vector iterator not dereferencable.

mergesort 関数のパラメーターとして (A.begin(),A.end()) を使用します。ここで、A は n 要素を含むベクトルです。

#include <iostream>
#include <vector>

using namespace std;

void swap(vector<int>::iterator first,vector<int>::iterator last)
{
    int temp;
    temp=*first;
    *first=*last;
    *last=temp;
    return;
}


void mergesort(vector<int>::iterator first,vector<int>::iterator last)
{
    if(first==last) return; 
    if(first+1==last)  
    {
        if(*last>*first) swap(first,last);
        return;
    }

    vector<int>::iterator middle;
    middle=first+(last-first)/2;

    mergesort(first,middle);
    mergesort(middle+1,last);

    int a,b,pa,pb;
    vector<int> h;
        //the number of elements in a
    pa=middle-first+1; 
        //the number of elements in b
    pb=last-middle;    
         h.resize(pa+pb);
    a=0; b=0;

    while(a<pa && b<pb)
        if(*(first+a)<*(middle+1+b)) 
          {
              h[a+b]=*(first+a); a++;
          }
        else
          {
              h[a+b]=*(middle+1+b); b++;
          }

    while(a<pa) 
       {
           h[a+b]=*(first+a); a++;
       }
    while(b<pb)
       {
           h[a+b]=*(middle+1+b); b++;
       }

    for(int i=0;i<((a+b)-1);i++)
    *(first+i)=h[i];

    return;
}




int main(){

    vector<int>A;

    for(int i=1000;i>0;i--)
    {
        A.push_back(i);               
           //vector of integer: 1000,999,998 ... 3,2,1
    }

    mergesort(A.begin(),A.end());     
 //sort vector elements from smallest to biggest: 1,2,3...998,999,1000


    system("pause");
    return 0;
}
4

2 に答える 2

2

イテレータの範囲は、最初の要素を参照するイテレータと、1 つ後ろの要素を参照するイテレータとして表現する必要があります。それらが等しい場合、これは空の範囲です。あなたはそれをしていません。

これを修正するには、if(first+1==last)句を返す必要があります。2 番目のmergesort(middle+1,last)呼び出しはmergesort(middle,last). pa等しいはずですmiddle-last。 pb正しく計算されます。-1そして、最後のforループは削除する必要があると思います。

最初のイテレータと最後までのイテレータによって定義された範囲を持つことは、悪い考えです。

于 2012-10-30T19:29:23.807 に答える
1

やったほうがいい

mergesort(A.begin(),A.end()-1);

実際には、end()反復子はベクトルの末尾の後の要素を指しています。ベクトルの最後の要素を指していません。

于 2012-10-30T18:37:31.327 に答える