This page is a snapshot from the LWG issues list, see the Library Active Issues List for more information and the meaning of Open status.

### 3029. `pop_heap` over-constrains input

Section: 25.8.8.3 [pop.heap] Status: Open Submitter: Mathias Stearn Opened: 2017-11-04 Last modified: 2020-09-06

Priority: 3

View all issues with Open status.

Discussion:

The spec for `<algorithms>` `pop_heap` includes

> -1- Requires: The range `[first, last)` shall be a valid non-empty heap.

This has the unfortunate consequence that to pop a value and push a new value is substantially less efficient than necessary. The popped value must be extracted by `pop_heap` (using up to 2 log `N` compares and swaps), and then, in `push_heap`, the new value must be inserted (for up to `N` compares and swaps, but more usually something like log `N`).

Simply relaxing the requirement to

> -1- Requires: The range `[first, last - 1)` shall be a valid heap.

enables use of `pop_heap` in an integrated push-and-pop operation, with less than half the number of expected compare and swap operations. Furthermore, if, as is often the case, the newly pushed value would have ended up at position `first`, the push/pop operation could complete in time `𝒪(1)`, instead of (3 log `N`).

The effect of the proposed relaxation on existing library implementations would be minimal in the extreme, and on existing user code nil. The base algorithm code remains exactly identical. The only changes needed would be to any instrumentation in a debugging version of the library, which would just need to relax its check, and to test suites that should exercise the newly tolerated input.

Users today are tempted to get the improved performance by relying on existing implementations' tacit tolerance of input that only satisfies the proposed, relaxed requirements. In fact, the cppreference.com page on `pop_heap` offers no hint that this usage is not already allowed. This change would bless such reliance as formally permitted.

After this change, minor extensions to `std::priority_queue` would enable it to take advantage of the newly efficient operation, perhaps:

>     void pop_push(const Type&);
>     void pop_push(Type&&);
>     template <class... Args> void pop_emplace(Args&&... args);

These will appear in a formal proposal if the resolution is accepted.

[2017-11 Albuquerque Wednesday night issues processing]

Priority set to 3

[2017-11 Albuquerque Saturday issues processing]

status to Open; Marshall to review

Proposed resolution:

This wording is relative to N4700.

1. Change 25.8.8.3 [pop.heap] as indicated:

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

   > > -1- Requires: The range `[first, last - 1)` shall be a valid non-empty heap. `RandomAccessIterator` shall satisfy the requirements of `ValueSwappable` (16.4.4.3 [swappable.requirements]). The type of `*first` shall satisfy the requirements of `MoveConstructible` (Table 23) and of `MoveAssignable` (Table 25).