Issue 3529: priority_queue(first, last) should construct c with (first, last)

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

3529. `priority_queue(first, last)` should construct `c` with `(first, last)`

Section: 23.6.4 [priority.queue] Status: C++23 Submitter: Arthur O'Dwyer Opened: 2021-03-01 Last modified: 2023-11-22

Priority: Not Prioritized

View all other issues in [priority.queue].

View all issues with C++23 status.

Discussion:

Tim's new constructors for priority_queue (LWG 3506⁽ⁱ⁾) are specified so that when you construct

auto pq = PQ(first, last, a);

it calls this new-in-LWG3506 constructor:

template<class InputIterator, class Alloc>
  priority_queue(InputIterator first, InputIterator last, const Alloc& a);
Effects: Initializes c with first as the first argument, last as the second argument, and a as the third argument, and value-initializes comp; calls make_heap(c.begin(), c.end(), comp).

But the pre-existing constructors are specified so that when you construct

auto pq = PQ(first, last);

it calls this pre-existing constructor:

template<class InputIterator>
  priority_queue(InputIterator first, InputIterator last, const Compare& x = Compare(), Container&& y = Container());
Preconditions: x defines a strict weak ordering ([alg.sorting]).

Effects: Initializes comp with x and c with y (copy constructing or move constructing as appropriate); calls c.insert(c.end(), first, last); and finally calls make_heap(c.begin(), c.end(), comp).

In other words,

auto pq = PQ(first, last);

will default-construct a Container, then move-construct c from that object, then c.insert(first, last), and finally make_heap.

But our new

auto pq = PQ(first, last, a);

will simply construct c with (first, last), then make_heap.

The latter is obviously better.

Also, Corentin's P1425R3 specifies the new iterator-pair constructors for stack and queue to construct c from (first, last). Good.

LWG should refactor the existing constructor overload set so that the existing non-allocator-taking constructors simply construct c from (first, last). This will improve consistency with the resolutions of LWG3506 and P1425, and reduce the surprise factor for users.

[2021-03-12; Reflector poll]

Set status to Tentatively Ready after five votes in favour during reflector poll.

[2021-06-07 Approved at June 2021 virtual plenary. Status changed: Voting → WP.]

Proposed resolution:

This wording is relative to N4878.

Edit 23.6.4.1 [priqueue.overview] as indicated:


template<class InputIterator>
    priority_queue(InputIterator first, InputIterator last, const Compare& x = Compare());
template<class InputIterator>
    priority_queue(InputIterator first, InputIterator last, const Compare& x, const Container& y);
template<class InputIterator>
    priority_queue(InputIterator first, InputIterator last, const Compare& x = Compare(), Container&& y = Container());

Edit 23.6.4.2 [priqueue.cons] as indicated:
```
template<class InputIterator>
    priority_queue(InputIterator first, InputIterator last, const Compare& x = Compare());
```
Preconditions: x defines a strict weak ordering ([alg.sorting]).

Effects: Initializes c with first as the first argument and last as the second argument, and initializes comp with x; then calls make_heap(c.begin(), c.end(), comp).
```
template<class InputIterator>
    priority_queue(InputIterator first, InputIterator last, const Compare& x, const Container& y);
template<class InputIterator>
    priority_queue(InputIterator first, InputIterator last, const Compare& x = Compare(), Container&& y = Container());
```
Preconditions: x defines a strict weak ordering ([alg.sorting]).

Effects: Initializes comp with x and c with y (copy constructing or move constructing as appropriate); calls c.insert(c.end(), first, last); and finally calls make_heap(c.begin(), c.end(), comp).

3529. priority_queue(first, last) should construct c with (first, last)

3529. `priority_queue(first, last)` should construct `c` with `(first, last)`