**Section:** 27.8.8 [alg.heap.operations] **Status:** WP
**Submitter:** Robert Douglas **Opened:** 2017-11-08 **Last modified:** 2023-02-13 10:17:57 UTC

**Priority: **3

**View all other** issues in [alg.heap.operations].

**View all issues with** WP status.

**Discussion:**

In discussion of D0202R3 in Albuquerque, it was observed that `pop_heap` and `sort_heap` had
`constexpr` removed for their requirement of `ValueSwappable`. It was then observed that
`push_heap` and `make_heap` were not similarly marked as having the `ValueSwappable` requirement.
The room believed this was likely a specification error, and asked to open an issue to track it.

*[2017-11 Albuquerque Wednesday night issues processing]*

Priority set to 3; Marshall to investigate

**Previous resolution [SUPERSEDED]:**

This wording is relative to N4700.

Change 27.8.8.2 [push.heap] as indicated:

template<class RandomAccessIterator> void push_heap(RandomAccessIterator first, RandomAccessIterator last); template<class RandomAccessIterator, class Compare> void push_heap(RandomAccessIterator first, RandomAccessIterator last, Compare comp);-1-

Requires:The range[first, last - 1)shall be a valid heap.RandomAccessIteratorshall satisfy the requirements ofValueSwappable(16.4.4.3 [swappable.requirements]). The type of*firstshall satisfy theMoveConstructiblerequirements (Table 23) and theMoveAssignablerequirements (Table 25).Change 27.8.8.4 [make.heap] as indicated:

template<class RandomAccessIterator> void make_heap(RandomAccessIterator first, RandomAccessIterator last); template<class RandomAccessIterator, class Compare> void make_heap(RandomAccessIterator first, RandomAccessIterator last, Compare comp);-1-

Requires:RandomAccessIteratorshall satisfy the requirements ofValueSwappable(16.4.4.3 [swappable.requirements]). The type of*firstshall satisfy theMoveConstructiblerequirements (Table 23) and theMoveAssignablerequirements (Table 25).

*[2022-11-06; Daniel comments and syncs wording with recent working draft]*

For reference, the finally accepted paper was P0202R3 and the constexpr-ification of swap-related algorithms had been realized later by P0879R0 after resolution of CWG 1581 and more importantly CWG 1330.

*[Kona 2022-11-09; Move to Ready]*

*[2023-02-13 Status changed: Voting → WP.]*

**Proposed resolution:**

This wording is relative to N4917.

Change 27.8.8.2 [push.heap] as indicated:

template<class RandomAccessIterator> constexpr void push_heap(RandomAccessIterator first, RandomAccessIterator last); template<class RandomAccessIterator, class Compare> constexpr void push_heap(RandomAccessIterator first, RandomAccessIterator last, Compare comp); template<random_access_iterator I, sentinel_for<I> S, class Comp = ranges::less, class Proj = identity> requires sortable<I, Comp, Proj> constexpr I ranges::push_heap(I first, S last, Comp comp = {}, Proj proj = {}); template<random_access_range R, class Comp = ranges::less, class Proj = identity> requires sortable<iterator_t<R>, Comp, Proj> constexpr borrowed_iterator_t<R> ranges::push_heap(R&& r, Comp comp = {}, Proj proj = {});

-1- Let

`comp`be`less{}`and`proj`be`identity{}`for the overloads with no parameters by those names.-2-

*Preconditions*: The range`[first, last - 1)`is a valid heap with respect to`comp`and`proj`. For the overloads in namespace`std`,`RandomAccessIterator`meets the*Cpp17ValueSwappable*requirements (16.4.4.3 [swappable.requirements]) and the type of`*first`meets the*Cpp17MoveConstructible*requirements (Table 32) and the*Cpp17MoveAssignable*requirements (Table 34).-3-

*Effects*: Places the value in the location`last - 1`into the resulting heap`[first, last)`.-4-

*Returns*:`last`for the overloads in namespace`ranges`.-5-

*Complexity*: At most log(`last - first`) comparisons and twice as many projections.Change 27.8.8.4 [make.heap] as indicated:

template<class RandomAccessIterator> constexpr void make_heap(RandomAccessIterator first, RandomAccessIterator last); template<class RandomAccessIterator, class Compare> constexpr void make_heap(RandomAccessIterator first, RandomAccessIterator last, Compare comp); template<random_access_iterator I, sentinel_for<I> S, class Comp = ranges::less, class Proj = identity> requires sortable<I, Comp, Proj> constexpr I ranges::make_heap(I first, S last, Comp comp = {}, Proj proj = {}); template<random_access_range R, class Comp = ranges::less, class Proj = identity> requires sortable<iterator_t<R>, Comp, Proj> constexpr borrowed_iterator_t<R> ranges::make_heap(R&& r, Comp comp = {}, Proj proj = {});

-1- Let

`comp`be`less{}`and`proj`be`identity{}`for the overloads with no parameters by those names.-2-

*Preconditions*: For the overloads in namespace`std`,`RandomAccessIterator`meets the*Cpp17ValueSwappable*requirements (16.4.4.3 [swappable.requirements]) and the type of`*first`meets the*Cpp17MoveConstructible*(Table 32) and*Cpp17MoveAssignable*(Table 34) requirements.-3-

*Effects*: Constructs a heap with respect to`comp`and`proj`out of the range`[first, last)`.-4-

*Returns*:`last`for the overloads in namespace`ranges`.-5-

*Complexity*: At most 3(`last - first`) comparisons and twice as many projections.