Re: [Boost-users] [BGL] iterator/descriptor invalidation

Subject: Re: [Boost-users] [BGL] iterator/descriptor invalidation
From: Dmitry Bufistov (dmitry_at_[hidden])
Date: 2008-12-09 17:34:01

Hi,

Andrew Sutton escribió:
>     the documentation of adjacency_list states, that a call to
>     add_vertex() does not invalidate any iterators nor descriptors.
>     However, following code segfaults, because retrieving vertex
[]
> 
> This is a nice, subtle problem that you've found :) Remember that an 
> adjacency list stores a list of incident edges for each vertex. 
Adding a
> vertex (with VertexSet == vecS) can cause a reallocation of the 
> underlying buffer, causing all of those incident edge lists to be 
> reallocated and copied. The edge iterator stores actually stores a pair 
> of iterators into the out-edge list of some vertex... The unfortunate 
> side-effect seems to be that adding  a vertex *can* in fact invalidate 
> an edge iterator. I guess the documentation is wrong.
> 
> Note that this probably won't be the case with VertexSet != vecS since 
> additions don't cause re-allocations.
> 
> I don't see any possible way to work around this other than deferring 
> all of your vertex additions til after the loop.

In the provided example
g.m_vertices.reserve(6)
helps.

--Dmitry