Title
Missing allocator-extended constructors for priority_queue
Status
ready
Section
[priority.queue]
Submitter
Tim Song

Created on 2020-11-21.00:00:00 last changed 1 month ago

Messages

Date: 2021-02-26.17:32:09

Proposed resolution:

This wording is relative to N4878.

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

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

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

Date: 2021-02-15.00:00:00

[ 2021-02-26; LWG telecon ]

Set status to Tentatively Ready after discussion and poll.

FAN
1100

Date: 2021-02-17.00:00:00

[ 2021-02-17 Tim adds PR ]

Date: 2020-11-15.00:00:00

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

Date: 2020-11-21.00:00:00

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());
History
Date User Action Args
2021-02-26 17:32:09adminsetmessages: + msg11708
2021-02-26 17:32:09adminsetstatus: new -> ready
2021-02-18 03:34:02adminsetmessages: + msg11687
2021-02-18 03:34:02adminsetmessages: + msg11686
2020-11-29 13:57:40adminsetmessages: + msg11636
2020-11-21 00:00:00admincreate