>From a thread on comp.theory:

Suppose iterators first, last are the range of a heap
(make_heap(first, last)), and mid is an iterator pointing into the
heap (first <= mid && mid < last).

If I increase the value of *mid, then with a "normal" heap
implementation, I can repair the heap with
  push_heap(first, mid+1)
which takes O(log N) time.

AFAICS, the standard does not require the "normal" implementation,
meaning that I have no guarantee that the call will actually repair
the heap.  For instance an implementation such as
   push_heap(first, last)
   {
     if(last-first< 10) sort(first, last, greater<T>);
     else
       do_the_normal_push_thing(first,last);
   }
seems to meet the requirements of the standard, but may not repair the
heap.  Since I have to worry about this, I have to use
make_heap(first, last) to repair the heap and this takes O(N) time.
(Alternatively, I write my own heap operations, duplicating the
actual, but not guaranteed, implementation provided by my vendor's
compiler).

Would the standard be better if it required the useful behavior which
is universally implemented?

---
[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://www.jamesd.demon.co.uk/csc/faq.html                       ]