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.

### 3506. Missing allocator-extended constructors for `priority_queue`

Section: 22.6.5 [priority.queue] Status: WP Submitter: Tim Song Opened: 2020-11-21 Last modified: 2021-06-07

Priority: 3

View all other issues in [priority.queue].

View all issues with WP status.

Discussion:

`priority_queue` has two constructor templates taking a pair of input iterators in addition to a comparator and a container, but it does not have allocator-extended constructors corresponding to these constructor templates:

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

[2020-11-29; Reflector prioritization]

Set priority to 3 during reflector discussions. It has been pointed out that this issue is related to LWG 1199, LWG 2210, and LWG 2713.

[2021-02-17 Tim adds PR]

[2021-02-26; LWG telecon]

Set status to Tentatively Ready after discussion and poll.

F | A | N
--- | --- | ---
11 | 0 | 0

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

Proposed resolution:

This wording is relative to N4878.

1. Add the following paragraph at the end of 22.6.1 [container.adaptors.general]:

   > -6- The exposition-only alias template `iter-value-type` defined in 22.3.1 [sequences.general] may appear in deduction guides for container adaptors.

2. Modify 22.6.5 [priority.queue], class template `priority_queue` synopsis, as indicated:

   >     namespace std {
   >       template<class T, class Container = vector<T>,
   >                 class Compare = less<typename Container::value_type>>
   >       class priority_queue {

   >       // […]

   >       public:
   >         priority_queue() : priority_queue(Compare()) {}
   >         explicit priority_queue(const Compare& x) : priority_queue(x, Container()) {}
   >         priority_queue(const Compare& x, const Container&);
   >         priority_queue(const Compare& x, Container&&);
   >         template<class InputIterator>
   >           priority_queue(InputIterator first, InputIterator last, const Compare& x,
   >                           const Container&);
   >         template<class InputIterator>
   >           priority_queue(InputIterator first, InputIterator last,
   >                           const Compare& x = Compare(), Container&& = Container());
   >         template<class Alloc> explicit priority_queue(const Alloc&);
   >         template<class Alloc> priority_queue(const Compare&, const Alloc&);
   >         template<class Alloc> priority_queue(const Compare&, const Container&, const Alloc&);
   >         template<class Alloc> priority_queue(const Compare&, Container&&, const Alloc&);
   >         template<class Alloc> priority_queue(const priority_queue&, const Alloc&);
   >         template<class Alloc> priority_queue(priority_queue&&, const Alloc&);
   >         template<class InputIterator, class Alloc>
   >           priority_queue(InputIterator, InputIterator, const Alloc&);
   >         template<class InputIterator, class Alloc>
   >           priority_queue(InputIterator, InputIterator, const Compare&, const Alloc&);
   >         template<class InputIterator, class Alloc>
   >           priority_queue(InputIterator, InputIterator, const Compare&, const Container&, const Alloc&);
   >         template<class InputIterator, class Alloc>
   >           priority_queue(InputIterator, InputIterator, const Compare&, Container&&, const Alloc&);

   >       // […]

   >       };

   >       template<class Compare, class Container>
   >         priority_queue(Compare, Container)
   >           -> priority_queue<typename Container::value_type, Container, Compare>;

   >       template<class InputIterator,
   >                 class Compare = less<typename iterator_traitsiter-value-type<InputIterator>::value_type>,
   >                 class Container = vector<typename iterator_traitsiter-value-type<InputIterator>::value_type>>
   >         priority_queue(InputIterator, InputIterator, Compare = Compare(), Container = Container())
   >           -> priority_queue<typename iterator_traitsiter-value-type<InputIterator>::value_type, Container, Compare>;

   >       template<class Compare, class Container, class Allocator>
   >         priority_queue(Compare, Container, Allocator)
   >           -> priority_queue<typename Container::value_type, Container, Compare>;

   >       template<class InputIterator, class Allocator>
   >         priority_queue(InputIterator, InputIterator, Allocator)
   >           -> priority_queue<iter-value-type<InputIterator>,
   >                             vector<iter-value-type<InputIterator>, Allocator>,
   >                             less<iter-value-type<InputIterator>>>;

   >       template<class InputIterator, class Compare, class Allocator>
   >         priority_queue(InputIterator, InputIterator, Compare, Allocator)
   >           -> priority_queue<iter-value-type<InputIterator>,
   >                             vector<iter-value-type<InputIterator>, Allocator>, Compare>;

   >       template<class InputIterator, class Compare, class Container, class Allocator>
   >         priority_queue(InputIterator, InputIterator, Compare, Container, Allocator)
   >           -> priority_queue<typename Container::value_type, Container, Compare>;

   >       // […]
   >     }

3. Add the following paragraphs to 22.6.5.3 [priqueue.cons.alloc]:

   >     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)`.

   >     template<class InputIterator, class Alloc>
   >       priority_queue(InputIterator first, InputIterator last, const Compare& compare, const Alloc& a);

   > > -?- Effects: Initializes `c` with `first` as the first argument, `last` as the second argument, and `a` as the third argument, and initializes `comp` with `compare`; calls `make_heap(c.begin(), c.end(), comp)`.

   >     template<class InputIterator, class Alloc>
   >       priority_queue(InputIterator first, InputIterator last, const Compare& compare, const Container& cont, const Alloc& a);

   > > -?- Effects: Initializes `c` with `cont` as the first argument and `a` as the second argument, and initializes `comp` with `compare`; calls `c.insert(c.end(), first, last)`; and finally calls `make_heap(c.begin(), c.end(), comp)`.

   >     template<class InputIterator, class Alloc>
   >       priority_queue(InputIterator first, InputIterator last, const Compare& compare, Container&& cont, const Alloc& a);

   > > -?- Effects: Initializes `c` with `std::move(cont)` as the first argument and `a` as the second argument, and initializes `comp` with `compare`; calls `c.insert(c.end(), first, last)`; and finally calls `make_heap(c.begin(), c.end(), comp)`.