Prev: List initialization: a weird example
Next: pointer to object destructor
From: Rune Allnor on 11 Mar 2010 02:55
Hi all.

First of all: I *know* I am playing with fire with this one;
I just want to get some impression of how bad burns I'm risking.

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);

which is actually comprehensable to a human reader. I know
there are a lot of technical details that need to be addressed
(like if it is possible to define an iterator to a class that have
not
yet been declared, or how to do away with the iterator dereference
operator '*' internal to the expression), but leave those for now.

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.

If (well, after) this idea has been torn apart by the experts - are
there other ways to simplify the semantics as indicated?

Rune

--
[ See http://www.gotw.ca/resources/clcm.htm for info about ]
[ comp.lang.c++.moderated. First time posters: Do this! ]

From: Yechezkel Mett on 14 Mar 2010 11:14
On Mar 11, 9:55 pm, Rune Allnor <all...(a)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


--
[ See http://www.gotw.ca/resources/clcm.htm for info about ]
[ comp.lang.c++.moderated. First time posters: Do this! ]

From: Rune Allnor on 14 Mar 2010 20:37
On 15 Mar, 03:14, Yechezkel Mett <ymett.on.use...(a)gmail.com> wrote:
> On Mar 11, 9:55 pm, Rune Allnor <all...(a)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! ]

From: Yechezkel Mett on 15 Mar 2010 08:03
On Mar 15, 1:37 pm, Rune Allnor <all...(a)tele.ntnu.no> wrote:
> On 15 Mar, 03:14, Yechezkel Mett <ymett.on.use...(a)gmail.com> wrote:
> > On Mar 11, 9:55 pm, Rune Allnor <all...(a)tele.ntnu.no> wrote:
>
> > > 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.

Why not?

But I have just realised that you're instantiating the vector on
edge_t before it's defined, which the standard doesn't allow. I would
recommend just using pointers. You can get back from a pointer to an
iterator like this:

i = v.begin() + (p - &*v.begin());

where i is an iterator, v is a vector and p is a pointer. On the other
hand, I can't see anything useful an iterator would give you here over
a pointer.

Yechezkel Mett


--
[ See http://www.gotw.ca/resources/clcm.htm for info about ]
[ comp.lang.c++.moderated. First time posters: Do this! ]

From: Leigh Johnston on 15 Mar 2010 08:02


"Yechezkel Mett" <ymett.on.usenet(a)gmail.com> wrote in message
news:7e47a8eb-9a1c-41a8-b53a-414185ce299d(a)q21g2000yqm.googlegroups.com...
> On Mar 11, 9:55 pm, Rune Allnor <all...(a)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
iterator if it is a static, is a local variable, is a member variable or is
a container element).

/Leigh


--
[ See http://www.gotw.ca/resources/clcm.htm for info about ]
[ comp.lang.c++.moderated. First time posters: Do this! ]

 | 
Pages: 1
Prev: List initialization: a weird example
Next: pointer to object destructor