Re: [boost] GSoC 2010: Heaps and Queues

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;
update(x);

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

x->field[999] = newValue;
update(x);

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