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

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

Section: 22.6.5 [priority.queue] Status: WP Submitter: Arthur O'Dwyer Opened: 2021-03-01 Last modified: 2021-06-12

Priority: Not Prioritized

View all other issues in [priority.queue].

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

  1. Edit 22.6.5.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());
    
  2. Edit 22.6.5.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).