Movatterモバイル変換

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

3529.priority_queue(first, last) should constructc with(first, last)

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

Priority:Not Prioritized

View all otherissues in [priority.queue].

View all issues withC++23 status.

Discussion:

Tim's new constructors forpriority_queue (LWG3506⁽ⁱ⁾)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:Initializesc withfirst as the first argument,last as the second argument,anda as the third argument,and value-initializescomp;callsmake_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:Initializescomp withxandc withy(copy constructing or move constructing as appropriate);callsc.insert(c.end(), first, last);and finally callsmake_heap(c.begin(), c.end(), comp).

In other words,

auto pq = PQ(first, last);

will default-construct aContainer,then move-constructc from that object,thenc.insert(first, last),and finallymake_heap.

But our new

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

will simply constructc with(first, last),thenmake_heap.

The latter is obviously better.

Also, Corentin'sP1425R3specifies the new iterator-pair constructors forstack andqueueto constructc from(first, last). Good.

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

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

2. 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:Initializesc withfirst as the first argument andlast as the second argument, and initializescomp withx; then callsmake_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:Initializescomp withx andc withy (copy constructing ormove constructing as appropriate); callsc.insert(c.end(), first, last);and finally callsmake_heap(c.begin(), c.end(), comp).