Boost logo

Boost :

Subject: Re: [boost] GSoC 2010: Heaps and Queues
From: Dan Larkin (danielhlarkin_at_[hidden])
Date: 2010-04-08 22:23:21

Andrew Sutton wrote:
> Maybe this approach allows too much freedom. I suppose you could also offer
> a method:
> void update(iterator pos, const T& x); // *pos = x; update(pos);
> That would prevent modifying operations in between updates.

This runs into the reference copying issue again. This assumes that T
has a well-behaved and efficient copy-constructor, and does a full
replacement of x rather than allowing for a partial update. I'm not
convinced that the extra safety offers enough of a benefit over allowing
the user to update it on their own:

*x = newValue;

Or, perhaps some more complex structure that would drive my point home a
bit more effectively:

x->field[999] = newValue;

As long as the library is explicit about the fact that updating data
will temporarily void the heap property until an update() call is made
on the data in question, it should work much better this way.

That said, I think the issue of iterator behavior inside the heap will
be quite an issue. Iterator-value association should not be a major
issue to maintain (or the iterators would be rather useless otherwise).
  Structural changes could definitely alter the order of traversal, but
again, that should be okay given adequate warning about which heap
operations could result in changes.

Working up another revision currently. Hopefully it'll be the final
one, since it's due in less than 24 hours, but who knows. And, of
course, I'll be around for plenty of extra questioning in the interim
period if the proposal leaves anything out. :D

Dan Larkin

Boost list run by bdawes at, gregod at, cpdaniel at, john at