Hello,

do you have any comment on the following? Suggestion, advice,
improvement, flame?
I started discussing this in clc++m, message <8aba5fa9-28c2-4451-
a6dd-8b369c969429@l35g2000pra.googlegroups.com>.

Additional heap functions

(based on n2723, since concepts are going away)

In the synopsis of [algorithms], after pop_heap, add:

template<class RandomAccessIterator>
   void remove_heap(RandomAccessIterator first, RandomAccessIterator
last,
                 RandomAccessIterator target);
template<class RandomAccessIterator, class Compare>
   void remove_heap(RandomAccessIterator first, RandomAccessIterator
last,
                 RandomAccessIterator target, Compare comp);

template<class RandomAccessIterator>
   void update_heap(RandomAccessIterator first, RandomAccessIterator
last,
                 RandomAccessIterator target);
template<class RandomAccessIterator, class Compare>
   void update_heap(RandomAccessIterator first, RandomAccessIterator
last,
                 RandomAccessIterator target, Compare comp);


In [alg.heap.operations], before [make.heap], add:

remove_heap

template<class RandomAccessIterator>
   void remove_heap(RandomAccessIterator first, RandomAccessIterator
last,
                 RandomAccessIterator target);
template<class RandomAccessIterator, class Compare>
   void remove_heap(RandomAccessIterator first, RandomAccessIterator
last,
                 RandomAccessIterator target, Compare comp);

Effects: Swaps the value in the location target with the value in the
location last - 1 and makes [first,last - 1) into a heap. The range
[first,target) is not affected.

Requires: The range [first,last) shall be a valid heap and target
shall be in
this range. The type of *first shall satisfy the Swappable
requirements (37),
the MoveConstructible requirements (Table 33), and the the
MoveAssignable
requirements (Table 35).

Complexity: At most 2 * log(last - first) comparisons.


update_heap

template<class RandomAccessIterator>
   void update_heap(RandomAccessIterator first, RandomAccessIterator
last,
                 RandomAccessIterator target);
template<class RandomAccessIterator, class Compare>
   void update_heap(RandomAccessIterator first, RandomAccessIterator
last,
                 RandomAccessIterator target, Compare comp);

Effects: Makes [first,last) into a heap. If !(*target < old) or comp
(*target,
old)==false, [target+1,last) is not affected. If !(old < *target) or
comp(old,
*target)==false, [first,target) is not affected.

Requires: target shall be in the range [first,last). For some possibly
different value "old" of *target, the range [first,last) shall be a
valid
heap. The type of *first shall satisfy the Swappable requirements
(37), the
MoveConstructible requirements (Table 33), and the the MoveAssignable
requirements (Table 35).

Complexity: At most 2 * log(last - first) comparisons.




Justification:

these 2 operations currently require a possibly linear time call to
make_heap,
whereas they can easily be made logarithmic time.

I expect the most frequent use will be:
read first
*first=new_value
update_heap(first,last,first)

which is a small but nice time improvement over:
pop_heap
read last-1
*(last-1)=new_value
push_heap(first,last)

(from 3*log(n) down to somewhere between constant and 2*log(n))

The main argument against adding these functions is that since the STL
heap is
array-based and not tree-based, operations on it invalidate pointers
to its
elements. It then looks like the pointer target was obtained by
linearly
traversing the array, so we shouldn't be so worried about getting a
good
complexity for the removal. However,
- the operations to find the pointer target may be much faster than
the
   comparisons and moves that happen when we change the structure
- it is possible to update an external pointer in the move assignment
of an
   array element.

Future:
- push_heap and update_heap could return an iterator to the new
position (I
   don't currently need it, but it could be useful, and is essentially
free)
- provide an interface for these functions in priority_queue
- it should be possible to call these functions with iterator first
and last
   and const_iterator target, but for now I am just copying std::rotate
which
   doesn't allow it.

Doubts:
- I don't know about requiring Swappable, as it is already implied by
the 2
   other requirements, I just copied it from pop_heap (for some reason
   pop and sort require it but not push or make).
- I don't know exactly how much to specify the effects of the
functions. It is
   useful to specify enough, to have some guarantees on which iterators
are not
   invalidated. On the other hand, saying it is a heap kind of defines
the
   implementation, so details may not be needed.
- the name of the functions can change (delete_heap, erase_heap,
purge_heap?
   *_from_heap?), I am not set on this one. However, overloading
pop_heap to
   handle remove_heap makes it hard to provide a version that doesn't
require
   comp.
- the only other occurence of 3 iterators on the same range I found is
   std::rotate, where arguments are in order first, middle, last.
However, here
   I think it more natural to first pass the range and then the element
to
   remove. I don't really care though.
- I don't like the name "last" for the past-the-end variable, but that
is what is used
   everywhere in the standard. Looking at the rest of the standard,
maybe target
   should be pos(ition) instead.

--
[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@netlab.cs.rpi.edu]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://www.comeaucomputing.com/csc/faq.html                      ]