Geek Answers Handbook

Vector iterators are incompatible

I am currently working on a graphics library for C ++ and am now stuck at the point where I am getting an assertion error in debug mode at runtime. I also looked at another question here, but none of the questions and answers led me to a solution. After reading in some forums, it seems that this error occurs because iterators become invalid as soon as the vector content changes. (e.g. when using erase() ). But, as you can see in my code, I do not change the vector, just repeating.

Error in line I marked with //ASSERTION . It is strange that neighbor_it does not point to the first object in (*vertex_it)->neighbors( ), but to 0xfeeefeee . When debugging the code, I clearly see that the vector of neighbors contains at least one element. Should neighbor_it point to the first object in this vector?

For more information: m_vertices is the vector of all vertices in the graph, and vertex::neighbors() returns the vector of edges (which have a pointer to a neighboring / target vertex). In this method, I want to remove all edges pointing to a specific vertex. Returns true if the corresponding edge is found and deleted, false if there is no edge pointing to p_vertex .

 bool graph::remove_edges_pointing_to( vertex* p_vertex ) { bool res = false; std::vector<vertex*>::iterator vertex_it = m_vertices.begin(); // iterate through all vertices while( vertex_it != m_vertices.end() ) { // iterator on first element of neighbors of vertex std::vector<edge*>::iterator neighbor_it = (*vertex_it)->neighbors().begin(); // iterate through all successors of each vertex while( neighbor_it != (*vertex_it)->neighbors().end() ) //ASSERTION { if( (*neighbor_it)->dest() == p_vertex ) { if( (*vertex_it)->remove_edge( *neighbor_it ) ) { res = true; } } neighbor_it++; } vertex_it++; } return res; }

EDIT: (Solution)

Ok, here is my new code that works correctly. remove_edge() now returns an iterator for the next object in the vector from which it removed the edge. In addition, neighbors() now returns a reference to the corresponding vector.

 bool graph::remove_edges_pointing_to( vertex* p_vertex ) { bool res = false; std::vector<vertex*>::iterator vertex_it = m_vertices.begin(); // iterate through all vertices while( vertex_it != m_vertices.end() ) { // iterator on first element of neighbors of vertex std::vector<edge*>::iterator neighbor_it = (*vertex_it)->neighbors().begin(); // iterate through all successors of each vertex while( neighbor_it != (*vertex_it)->neighbors().end() ) { if( (*neighbor_it)->dest() == p_vertex ) { neighbor_it = (*vertex_it)->remove_edge( *neighbor_it ); res = true; } else { neighbor_it++; } } vertex_it++; } return res; }

Thanks again for your answers! :)

+4
source share
2 answers

My assumption, given the limited context you specified, is that neighbours() returns a copy of std::vector<edge*> instead of a link, i.e. std::vector<edge*>& . Therefore, after begin() call to the temporary object is deleted, and the resulting iterator points to garbage.

+11
source

I would suggest that remove_edge modifies the base container neighbor_it , thereby invalidating it, but I cannot be sure without seeing more of your code.

If so, a possible solution would be to return the iterator to the next element after the deleted one, as is done, for example, std::vector::erase .

+1
source

More articles:


All Articles