pop_heap
over-constrains inputSection: 26.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.
Change 26.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 validnon-emptyheap.RandomAccessIterator
shall satisfy the requirements ofValueSwappable
(16.4.4.3 [swappable.requirements]). The type of*first
shall satisfy the requirements ofMoveConstructible
(Table 23) and ofMoveAssignable
(Table 25).