Re: Vector of iterators?
On 15 Mar, 03:14, Yechezkel Mett <ymett.on.use...@gmail.com> wrote:
On Mar 11, 9:55 pm, Rune Allnor <all...@tele.ntnu.no> wrote:
I have an application that implements a Doubly Connected
Edge List (DCEL):
struct edge_t {
size_t origin;
size_t next;
size_t previous;
size_t inverse;
};
std::vector<point_t> points;
std::vector<edge_t> edges;
Starting from some edge, one traverses the data structure by
nested function calls. For instance, "the point at the origin of the
previous of the current edge's inverse edge" would be referred
to as something like
point_t p = points[edges[edges[edges[n].inverse].previous].origin];
where n is the indes of the current edge. This becomes very
messy very quickly, so I was wondering if it might be possible
to somehow implement the edge list in terms of iterators:
class edge_t;
typedef std::vector<point_t>::iterator pi_t;
typedef std::vector<edge_t>::iterator ei_t;
struct egde_t {
pi_t origin;
ei_t next;
ei_t previous;
ei_t inverse;
};
If so, it might be possible to simplify the above dereference
to something like
point_t p = *(n.inverse().prev().origin);
point_t p = *(n->inverse->prev->origin);
Would this be guaranteed to work with the above declarations?
If so, iterators are a bit more flexible than I was aware.
My question is: What are the dangers of inserting iterators
in collections? I am aware that the vector the iterator refers
to could do some internal reorganizations of memory, invalidating
stored iterators, but in this particular case memory requirements
are deterministic, and everything can be allocated and initialized
up front, never to (need to) change again for the duration of the
algorithm.
So long as you're sure that the iterators won't be invalidated, it
seems perfectly fine to me. Note that plain pointers would work just
as well,
Plain pointers and iterators suffer from the same achilles
heel, which is that they rely on the memory footprint of the
container to stay fixed. If it is unsafe to use one, it is
also unsafe to use the other.
which might make a difference if you were using containers
where iterators are not equivalent to plain pointers.
The container in this partiular application is a std::vector.
Don't think weird iterator implementations would be a problem
there. But of course, I could be wrong...
Rune
--
[ See http://www.gotw.ca/resources/clcm.htm for info about ]
[ comp.lang.c++.moderated. First time posters: Do this! ]