Boost logo

Boost :

From: Jeremy Siek (jsiek_at_[hidden])
Date: 2004-04-06 09:24:05

Hi Vladimir,

On Apr 6, 2004, at 1:07 AM, Vladimir Prus wrote:
> But really, we've got only two variants:
> 1. Use pointers and bear this overhead
> 2. Store cached value of index inside vertex_descriptor, as you
> suggest in
> the other post. In this case we have space overhead.

True, though vertex_descriptor's are not stored in memory very often...
usually appear as local variables, so the space is just consuming more

> So, it seems we can't have nice-for-users 'v->value' or *v syntax
> without
> overhead. It's the question which kind of overhead is better.
> BTW, what about vertex_descriptor stability. If we use vector for
> storage,
> it means the addresses can change when we *add* vertex, which would
> invalidate already stored vertex descriptors. Does this mean we need
> to use
> list/deque for the 'easy-to-use' graph type?

That's a good question. Invalidation is certainly not user friendly.

BTW, there's another issue with the idea of automatically assigning
when VertexList!=vecS. If we want to make sure the indices stay in the
range [0,num_vertices(g)) in the face of adding and removing vertices,
there will be a price to pay in terms of renumbering vertices or
recycling indices.


Jeremy Siek <jsiek_at_[hidden]>
Ph.D. Student, Indiana University Bloomington
Graduating in August 2004 and looking for work
C++ Booster (

Boost list run by bdawes at, gregod at, cpdaniel at, john at