0

I need to implement MergeSort to sort vector of integer using vector iterators. I implemented it but I'm getting this error: Vector iterator not dereferencable.

As parameters for mergesort function I use (A.begin(),A.end()) where A is my vector which contain n elements.

#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;
}
1

2 Answers 2

2

Iterator ranges should be expressed as an iterator referring to the first element, and an iterator referring to one-past-the-end. If they are equal, this is an empty range. You aren't doing that.

To fix this, the if(first+1==last) clause should just return. The second mergesort(middle+1,last) call should be mergesort(middle,last). pa should just equal middle-last. pb is calculated correctly. And I think the -1 in the last for loop should be removed.

Having a range defined by iterator to first and iterator to last is a bad idea.

1

You should do

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

Actually, the end() iterator points an element after the end of the vector. It doesn't point to the last element of the vector.

1
  • 3
    No, you shouldn't do that. Follow the pattern that iterator ranges contain the first element, and an iterator to one-past-the-end element. Commented Oct 30, 2012 at 19:24

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.