Re: [boost] GSoC 2010: Heaps and Queues

Subject: Re: [boost] GSoC 2010: Heaps and Queues
From: Andrew Sutton (andrew.n.sutton_at_[hidden])
Date: 2010-04-08 08:11:39

> Okay, so once again, focusing on studying for my exam tonight right now,
> but just doing a bit of research to get the gears turning in the background.
>  Standard iterator functionality requires '++', '--', '==', 'begin()', and
> 'end()', correct?  Did I miss anything?
>

Begin and end are specific to a Container or Range (capitalization indicates
a Concept), but more or less, right. Iterators also support dereferencing
(*x if x has Iterator type).

> Other than that, I'm still a confused about the behavior of iterators
> within partially ordered data structures.  It's one thing to have a pointer
> abstraction, but traversal seems to be an issue.  In particular, if any
> changes to the structure are made during the traversal, the structure could
> re-arrange itself in such a way that individual nodes could be traversed
> multiple times before others are visited once, without any changes to the
> node value itself.  This seems like poor behavior to me, and I'm not sure
> what to do with it.  Perhaps someone could shed some light on the issue?

That's a good observation, and has some interesting implications. By
exposing an iterator (or pointer) into the heap, you admit the possibility
that a user can modify an object in such a way that the heap property will
be violated. For example,

*x = 5; // Oops.

Let's assume that this makes *x the minimum value in the heap. If x doesn't
refer to the top of the heap, then we've violated the heap property.
Conceivable, you could do two things:

1. Automatically update the heap if the user changes a value thru an
iterator. This is a really bad idea for a number of reasons, but mostly
because it's hard to generically trap modifying writes. Second, as you've
observed, it could have some unknown side-effects on other iterators into
the heap. Maybe they're invalid, maybe they now point to different values. I
don't know.

2. Let the use update the modified value on their own. This means that heap
will, for a short time, be invalid, but there aren't any complex side
effects until the programmer invokes them.

Of course, if I'd read the subsequent posts, then these questions would have
already been answered :)

Andrew Sutton
andrew.n.sutton_at_[hidden]