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

### 3032. `ValueSwappable` requirement missing for `push_heap` and `make_heap`

Section: 27.8.8 [alg.heap.operations] Status: Ready Submitter: Robert Douglas Opened: 2017-11-08 Last modified: 2022-11-10

Priority: 3

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

View all issues with Ready 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.

> 1. 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. `RandomAccessIterator` shall satisfy the requirements of `ValueSwappable` (16.4.4.3 [swappable.requirements]). The type of `*first` shall satisfy the `MoveConstructible` requirements (Table 23) and the `MoveAssignable` requirements (Table 25).

> 2. 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: `RandomAccessIterator` shall satisfy the requirements of `ValueSwappable` (16.4.4.3 [swappable.requirements]). The type of `*first` shall satisfy the `MoveConstructible` requirements (Table 23) and the `MoveAssignable` requirements (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]

Proposed resolution:

This wording is relative to N4917.

1. 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.

2. 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.