Issue 3506: Missing allocator-extended constructors for priority

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.

3506. Missing allocator-extended constructors for `priority_queue`

Section: 23.6.4 [priority.queue] Status: C++23 Submitter: Tim Song Opened: 2020-11-21 Last modified: 2023-11-22

Priority: 3

View all other issues in [priority.queue].

View all issues with C++23 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.

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

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

Modify 23.6.4 [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>;

  // […]
}

Add the following paragraphs to 23.6.4.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).

3506. Missing allocator-extended constructors for priority_queue

3506. Missing allocator-extended constructors for `priority_queue`