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);
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, which might make a difference if you were using containers
where iterators are not equivalent to plain pointers.
Yechezkel Mett
I agree, storing iterators in containers is fine. Using invalidated
iterators is not fine. There is no difference between using an invalidated
[ comp.lang.c++.moderated. First time posters: Do this! ]