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