vector iterators incompatible

johnson518 (6)
Hi, I have been in trouble by the vector interators incompatible problem for one week plus. I wrote a program to calculate the maximum overlaps along the road network. The program works well if it is under single thread, but if I apply multithreads in order to improve the performance, the program crashes, and always prompt a small window saying vector line 251 "vector iterators incompatible". I really can not locate the place where problem happens. It would be grateful if you could give me some hints on solving this problem. Next is some part of the program where vector and multithreads are applied.



using namespace std;
boost::mutex write_mutex;

Adj_file Adj;
Pnt_file Pnt;
vector<int> Centers;
vector<int> Non_Centers;

vector<Max_Region> Locals;

//******************************comparison functions
inline bool compfun(Qnode a,Qnode b)
{
return (a.ndist<b.ndist);
}
inline bool compdis(Qnode a,Qnode b)
{
return(a.ndist+a.extend<b.ndist+b.extend);
}
inline bool comptimes (temnode a,temnode b)
{
return (a.times>b.times);
}
//******************************comparison functions end

void MeDisFind(const int NumCenter,const int ST_P,const int EN_P) //*****multithreading function
{
int Num_Cens=NumCenter;
int i=0,j=0,k=0;
vector <Qnode> myqueue;
myqueue.reserve(200000);
// for each point outside choosen point set
for(i=ST_P;i<EN_P;i++)
{
vector <Qnode> ready_que;
vector<bool> isvisit(MAXNODE,false);
int Point=Non_Centers[i];
//Pnt_list *p=Pnt.Pnt_dir[Point];
float mindis=MAXFLOAT;
float pos=0.0;
myqueue.clear(); ready_que.clear(); //to avoid overflow
insidestartline(mindis,Point,pos,myqueue);
if(myqueue.size()>=2) //only q and centroid
{
sort(myqueue.begin(),myqueue.end(),compdis);
if(mindis<MAXFLOAT)
{
ready_que.push_back(myqueue[1]);
myqueue.pop_back();
}
cout<<endl<<" i=="<<i<<endl;
while(!myqueue.empty())
{
int myque_Size=myqueue.size();
int readyque_Size=ready_que.size();
Qnode tem=myqueue[0];
// if(tem.ndist>mindis)
// break;
int Ni=tem.path.back(); //node to be expanded.
isvisit[Ni]=true;
if(tem.ndist+0.1<mindis&&tem.node==-1) //only not extension will be considered
{
vector<Adj_record> Ni_adjrecord((Adj.adjlist[Ni]).begin(),(Adj.adjlist[Ni]).end());

for(int j=0;j<Ni_adjrecord.size();j++)
{
int Nj=Ni_adjrecord[j].nj;
if(isvisit[Nj]) //if(isvisit[Nj]&&!p->has_center) //prevent repeated visit
continue;
float elen=Ni_adjrecord[j].edist;
Pnt_list *p=Ni_adjrecord[j].pnt; //not every adjcent edges has points lying on it.
//first check whether it has centers in Ni-->Nj
Qnode tema=tem; //copy problem?
tema.node=-1;
tema.extend=0.0;
//prevent repeated visit
if(Ni==(Pnt.Pnt_dir[Point])->nj && Nj==(Pnt.Pnt_dir[Point])->ni||Ni==(Pnt.Pnt_dir[Point])->ni && Nj==(Pnt.Pnt_dir[Point])->nj)
{
if(tem.path.size()<3)
continue;
}
if(p!=NULL&&p->has_center)
{
tema.extend=extenlen(Ni,Nj,elen,p);
tema.node=Nj;
tema.ndist=tem.ndist;
if(tema.extend+tem.ndist<mindis)
{
mindis=tema.extend+tem.ndist;
}
}
else
{
if(elen+tem.ndist<=mindis)
{
tema.ndist=tem.ndist+elen;
tema.path.push_back(Nj);
}
else if(elen+tem.ndist>mindis)
{
tema.extend=mindis-tem.ndist;
tema.node=Nj;
tema.ndist=tem.ndist;
}
}

if(tema.node!=-1)
{
ready_que.push_back(tema);
}
else
{
myqueue.push_back(tema);
}
p=NULL;
}//for loop
}//if statement end

if(readyque_Size<ready_que.size()||myque_Size<myqueue.size())
{
myqueue.erase(myqueue.begin()); //?????
}
else
{
ready_que.push_back(myqueue[0]);
myqueue.erase(myqueue.begin()); //?????
}

if(myqueue.size()>=2)
{
sort( myqueue.begin(), myqueue.end(),compdis);
}

}//while loop end

myqueue.assign(ready_que.begin(),ready_que.end()); //copy ready_que to myque;
ready_que.clear();
normalizepath(mindis,myqueue);
} //if statement end.

recordcover( Point, pos, mindis, myqueue);

}//for loop end
}

Last edited on
johnson518 (6)
//this page is some routines called by the function MeDisFind(,,) aboved mentioned.

void normalizepath(const float mindis,vector <Qnode> & myqueue) //test const float
{
for(int i=0;i<myqueue.size();i++)
{
if(myqueue[i].node==-1&&myqueue[i].path.size()<3)
continue;
if(myqueue[i].extend+myqueue[i].ndist>mindis)
{
if(myqueue[i].node!=-1)
{
float diff=mindis-myqueue[i].ndist;
myqueue[i].extend=(diff>0? diff : myqueue[i].extend/2);
}
else if(myqueue[i].ndist>mindis && myqueue[i].node==-1)
{
int Ni=(myqueue[i].path).back();
(myqueue[i].path).pop_back();
int Nj=myqueue[i].path.back(); //test pop_back
float extend=mindis-(myqueue[i].ndist-length(Ni,Nj));
myqueue[i].extend=(extend>0 ? extend : 0.0) ;
myqueue[i].node=Nj;
}

}

}
}


void insidestartline(float &mindis,const int startpoint,float &pos, vector <Qnode> & myqueue)
{
//check whether some centers in the same line
int Point=startpoint;
int closepid=Point;
int j=0,k=0;
float dist=0.0;
float diff=MAXFLOAT;

Qnode temq; //temq.path.empty ??
temq.ndist=0;
temq.node=-1;
temq.extend=0.0;
temq.path.push_back(Point);
myqueue.push_back(temq);
Pnt_list *p=Pnt.Pnt_dir[Point];
//take care centroid lying at the same line
for(j=0;j<p->points.size();j++) //binary_search (v.begin(), v.end(), 3)
{
if(p->points[j].pid==Point)
{
dist= p->points[j].pos;
pos=dist;
break;
}
}
if(p->has_center)
{
for(k=0; k<p->points.size();k++) //choose the closest centroid
{
if(p->points[k].is_center&& diff >fabs(dist-(p->points[k].pos)))
{
closepid=p->points[k].pid;
diff=fabs(dist-(p->points[k].pos));
}
}
//myqueue[0].node;
myqueue[0].ndist=diff;
myqueue[0].path.push_back(closepid);
mindis=diff;
}
//put nx ny into the queue if possible
int adj_size=(Adj.adjlist[p->ni]).size();
for(int h=0;h<adj_size;h++)
{
if((Adj.adjlist[p->ni][h]).nj==p->nj)
{
float temdist=(Adj.adjlist[p->ni][h]).edist;
if(dist+0.1<mindis) //avoid floating mistake
{
Qnode tema;
tema.node=-1;
tema.extend=0.0;
tema.ndist=dist;
tema.path.push_back(Point);
tema.path.push_back(p->ni);
myqueue.push_back(tema);
}
if(temdist-dist+0.1<mindis) //avoid floating mistake
{
Qnode temb;
temb.node=-1;
temb.extend=0.0;
temb.ndist=temdist-dist;
temb.path.push_back(Point);
temb.path.push_back(p->nj);
myqueue.push_back(temb);
}
if(!p->has_center)
{
myqueue.erase(myqueue.begin());
}
break;
}
}
p=NULL;
}
void recordcover(const int Point,const float pos,const float mindis, vector <Qnode> & myqueue)
{
Pnt_list *p=Pnt.Pnt_dir[Point];
int nx,ny;
if(myqueue.size()<2) //short dis spans within one line
{
Cover_record corecord;
corecord.begin= pos-mindis;
corecord.end=pos+mindis;
edgecover(p->ni,p->nj,corecord);// (Covers[p->ni][p->nj]).push_back(corecord); //********cover replacement
}
else // dis spans outside one line
{
for(int i=0;i<myqueue.size();i++)
{
if(myqueue[i].node==-1&&myqueue[i].path.size()<3) //only p and q
{
Cover_record tema;
if(pos+0.1<mindis)
{
tema.begin=pos; //MINFLOAT means the begin, MAXFLOAT means the end
tema.end=pos+mindis;
}
else
{
tema.begin= (pos-mindis > 0 ? pos-mindis:pos/2);
tema.end=pos; //MINFLOAT means the begin MAXFLOAT means the end
}
edgecover(p->ni,p->nj,tema);//(Covers[p->ni][p->nj]).push_back(tema); //********cover replacement
continue;
}
//begin
Cover_record temb;
temb.begin=(myqueue[i].path[1]>p->ni? pos:MINFLOAT);
temb.end=(myqueue[i].path[1]>p->ni? MAXFLOAT:pos);
edgecover(p->ni,p->nj,temb); //(Covers[p->ni][p->nj]).push_back(temb); //********cover replacement
myqueue[i].path.erase(myqueue[i].path.begin());
//middle
for(int j=0;j<myqueue[i].path.size()-1;j++)
{
Cover_record temc;
temc.begin=MINFLOAT;
temc.end=MAXFLOAT;
nx=myqueue[i].path[j];
ny=myqueue[i].path[j+1];
if(nx>ny)
{
int exchange=nx;
nx=ny;
ny=exchange;
}
edgecover(nx,ny,temc); // (Covers[nx][ny]).push_back(temc); //********cover replacement
}
//end
if(myqueue[i].node!=-1)
{
Cover_record temd;
nx=myqueue[i].node;
ny=myqueue[i].path.back();
temd.begin=(ny>nx ? length(nx,ny)-myqueue[i].extend:MINFLOAT);
temd.end=(ny>nx ? MAXFLOAT:myqueue[i].extend);
if(nx>ny)
{
int exchange=nx;
nx=ny;
ny=exchange;
}
edgecover(nx,ny,temd); // (Covers[nx][ny]).push_back(temd); //********cover replacement
}

}

}
p=NULL;
myqueue.clear();
}

/*********************************** mislenous*********************************/

inline float length(const int Ni, const int Nj)
{
int i=0;
vector<Adj_record> Ni_adjrecord((Adj.adjlist[Ni]).begin(),(Adj.adjlist[Ni]).end());
for(i=0;i<Ni_adjrecord.size();i++)
{
if(Ni_adjrecord[i].nj==Nj) //**********************************
{
return Ni_adjrecord[i].edist;
break;
}
}
if(i>=Ni_adjrecord.size())
return 0;
}
inline float extenlen(const int Ni, const int Nj,const float elen,const Pnt_list *p) //pointer may have some problem
{
float near=MAXFLOAT, far=MINFLOAT;
for(int i=0;i<p->points.size();i++)
{
if((p->points[i]).is_center)
{
if(near > (p->points[i]).pos)
near=(p->points[i]).pos;
if(far < (p->points[i]).pos)
far=(p->points[i]).pos;
}
}
p=NULL;
if(Ni>Nj)
{
return elen-far;
}
else
{
return near;
}

}
void edgecover(const int Ni, const int Nj,Cover_record tem )
{
vector<Adj_record> Adj_Ni(Adj.adjlist[Ni].begin(),Adj.adjlist[Ni].end());
for(int j=0;j<Adj_Ni.size();j++)
{
if(Adj_Ni[j].nj==Nj)
{
boost::mutex::scoped_lock lock(write_mutex);
(Adj.adjlist[Ni][j]).cover.push_back(tem);
break;
}
}
return;
}
/*********************************** mislenous *********************************/
Last edited on
jsmith (5804)
If the program runs fine single-threaded but does not work multi-threaded, then
it sounds like a synchronization problem. The STL in general is not thread-safe.
Are you sure your synchronization is correct?


johnson518 (6)
Hi Jsmith,
ths for your reply. Actually, the sychronization happened to the funtion:

void edgecover(const int Ni, const int Nj,Cover_record tem )
{
vector<Adj_record> Adj_Ni(Adj.adjlist[Ni].begin(),Adj.adjlist[Ni].end());
for(int j=0;j<Adj_Ni.size();j++)
{
if(Adj_Ni[j].nj==Nj)
{
boost::mutex::scoped_lock lock(write_mutex);
(Adj.adjlist[Ni][j]).cover.push_back(tem);
break;
}
}
return;
}

And this function will be called by the multithreading function:
void MeDisFind(const int NumCenter,const int ST_P,const int EN_P), which is detailed in first floor.
johnson518 (6)
In my main function,
void main()
{
...........
............
............
boost::thread thrd1(boost::bind(&MeDisFind,NumCens, 0,10000));
boost::thread thrd2(boost::bind(&MeDisFind,NumCens, 10000,15000));
boost::thread thrd3(boost::bind(&MeDisFind,NumCens, 15000,20000));
boost::thread thrd4(boost::bind(&MeDisFind,NumCens, 20000,25000));
thrd1.join();
thrd2.join();
thrd3.join();
thrd4.join();
.........
}

jsmith (5804)
I don't think your synchronization is strong enough. You can't have any other threads
holding even iterators into the container while you do a push_back(), because push_back()
on a vector can potentially invalidate every iterator.

So even your edgecover() function isn't threadsafe -- you would need the scoped lock
at the top of the function, before you ever call begin() or end() on the Adj.adjlist[]
vector.
johnson518 (6)
Hi jsmith,
yes, but actually I have tried several times of putting the scoped lock at the top, or even before calling the edgecover(); but still can not work. Sometimes it will prompt a window saying" This may be due to a corruption of the heap, which indicates a buy in xx.exe or any of the DLLs it has loaded" .

I am quite new to boost, so not sure i am applying synchronization into my program by directly calling functions from boost in the right way.
jsmith (5804)
No, my point was that I think even doing what you tried isn't enough because the functions
that call edgecover() are holding iterators too, meaning that those functions also need to
be within the lock.

I have not looked at your code in detail, but the brief glance I did give it, it seems to me
like you need a complete rewrite if you want any kind of parallelism whatsoever.
Topic archived. No new replies allowed.