vector iterators incompatible

问题:

I'm currently working on a graph library for C++ and now got stuck at a point where I get an assertion error in debug mode during runtime. I also had a look an some other question here on SO but none of the questions and answers lead me to a solution. After reading in some forums I have the impression that this error happens because iterators become invalid as soon as the vector content is changed. (for example when using erase()) But as you can see in my code, I'm not modifying the vector, just iterating.

The error is in the line I marked with //ASSERTION. The strange thing is that neighbor_it doesn't point to the first object in (*vertex_it)->neighbors() but to 0xfeeefeee. When debugging through the code I can clearly see that the neighbors-vector contains at least one item. Shouldn't neighbor_it point to the first object in this vector?

For further information: m_vertices is a vector of all vertices in a graph and vertex::neighbors() returns a vector of edges (which have a pointer to the neighbor/destination vertex). In this method I want to remove all edges pointing to a certain vertex. Returns true if an according edge has been found and removed, 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)

Alright, here is my new code which works properly. remove_edge() now returns an iterator to the next object in the vector it removed the edge from. In addition neighbors() now returns a reference to the according 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! :)

回答1:

My guess, given limited context you provided, is that neighbours() returns copy of std::vector<edge*>, instead of reference, i.e. std::vector<edge*>&. So after begin() call temporary object is disposed, and obtained iterator points to rubbish.

回答2:

I would guess that remove_edge modifies the underlying container of neighbor_it, thereby invalidating it, but I cannot be certain without seeing more of your code.

If this is a case, a possible solution would be to return an iterator to the next element after the deleted one, as done for instance by std::vector::erase.