I'm transitioning my old, dinasour-ish program written with arrays and pointers to vectors and ran into some problem with iterators. I'm using Visual Studio 2005 SP1.
In debug mode the follow message appeared upon reaching the part of the code indicated further below:
Debug Assertion Failed!
expression ("_Myptr > ((_Myvec*)(this->_Mycont))->_Myfirst",0)
I clicked "retry" and was led to vector.h to the following part of this header file:
_Myt& operator--()
{ // predecrement
_SCL_SECURE_VALIDATE(this->_Mycont != NULL);
_SCL_SECURE_VALIDATE_RANGE(_Myptr > ((_Myvec *)(this->_Mycont))->_Myfirst);
--_Myptr;
return (*this);
}My program is pasted below:
void quicksort2(vector<A*>::iterator begin,vector<A*>::iterator end)//sorting program adapted from the famous recursive quicksort method,A is a struct, Wto is a float type member of this struct. the input argument for quicksort2 is simply the range of the vector elements to be sorted.
{
A *temp;
vector<A*>::iterator i=begin,j=end;
double pivot=(*(begin+(end-begin)/2))->Wto;
//partitioning starts;
while(i<=j)
{
while((*i)->Wto>pivot)
i++;
while((*j)->Wto<pivot)
j--;
if(i<=j)
{
temp=*i;
*i=*j;
*j=temp;
i++;j--;
}
}
//the recursive part
if(begin<j)
quicksort2(begin,j);//The error usually occurs here, depending on the input.
if(i<end)
quicksort2(i,end);
}
void test1()//test harness for the functionality of vectors and the modified quicksort algorithm
{
ifstream in;int i;
in.open("test2.txt");
A *ND;
ND=new A[100];
for(i=0;i<100;i++)
in>>ND[i].Wto>>ND[i].Range;
//***********shuffle ND************
random_shuffle(ND,ND+100);
for(i=0;i<100;i++)
cout<<ND[i].Wto<<" "<<ND[i].Range<<endl;
cout<<endl<<endl;
//**********************************
vector<A*> old;
for(i=0;i<100;i++)
old.push_back(ND+i);
vector<A*>::iterator iter=old.begin();
vector<A*>::iterator iter2=old.end()-1;
vector<A*>::iterator iter3=old.begin()+old.size()-1;
//******************quicksort***********
quicksort2(iter,iter2);//this line actually runs okay
quicksort2(old.begin(),old.end()-1);//the second time quicksort2 is called the error mentioned above occurred.
}
int main()// my actual main() function contains more stuff but only test1() is being tested. test1(); comes at the very beginning of main() so the remaining part of the program shouldn't have led to this error
{
test1();
return 0;
}What makes me feel wierd is that if quicksort2 is called only once then no crash occurs. It can be called using iter and iter2 or iter3 or old.begin() and old.end() without any problem but once quicksort2 has been run once then all subsequent calls to this function result in crashes of the same kind.
I read the part about iterators and containers in C++ Primer back and forth twice but still haven't got a clue what's wrong with my use of iterators. The book says iterators can be invalidated if the size of the vector is changed but in my case no re-sizing whatsoever is done in quicksort, only the elements of vector old have been sorted. Even if iter and iter2 are rendered invalid after the first pass, why are old.begin() and old.end() also causing a crash(see code above)? I'v also tried redefining iter and iter2 to old.begin() and old.end()-1 then pass them into quicksort2 but a crash still occurred....
By the way I'm surprised to find Visual Studio's Watch unable to display the values of expressions such as *iter or (*iter)->Wto. Can this be related to my possible misuse of iterators?
