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

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(i)) 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 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 xand 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 P1425R3specifies the new iterator-pair constructors forstack and queueto construct c from (first, last). Good.

LWG should refactor the existing constructor overload set so that the existing non-allocator-taking constructors simply construct cfrom (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.

  1. Edit 23.6.4.1 [priqueue.overview] as indicated:

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

  2. Edit 23.6.4.2 [priqueue.cons] as indicated:

    template
    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
    priority_queue(InputIterator first, InputIterator last, const Compare& x, const Container& y);
    template
    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).