Re: [boost] mutually recursive container and iterators problem

From: David Abrahams (abrahams_at_[hidden])
Date: 2000-07-04 21:25:49

----- Original Message -----
From: <jsiek_at_[hidden]>

> The problem is that I want to be able to insert/erase things out of
> both containers, and to do this in O(1) I need the iterators (not
> pointers to elements, or integer indices).
>
> In a normal adjacency list graph this isn't a problem, since I can
> just use an integer to get to the vertices. But in an adjacency-list,
> removing vertices is expensive. I want dynamic_graph to have O(1)
> vertex and edge insertion/removal.

Yep, I see the issue. It turns out that to get wide portability across
compilers, a container's iterators must be typedefs for non-nested types, so
you could probably get what you want from the STLport. Unfortunately, that
doesn't help _you_ much with respect to portability across lib
implementations.

I think this is just one of many refinements one would want from the
standard library containers (along the lines of, e.g., using const_iterators
to specify insertion positions). Each one arises out of real, but relatively
obscure situations. In my experience it takes a lot of work to convince
people that the refinements are even useful, much less important. That
doesn't mean we shouldn't try, though. ;)

-Dave