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: 24.6.7 [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.

FAN
1100

[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 24.6.1 [container.adaptors.general]:

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

  2. Modify 24.6.7 [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 24.6.7.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).