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