23 Containers library [containers]

23.6 Container adaptors [container.adaptors]

23.6.1 In general [container.adaptors.general]

The headers <queue> and <stack> define the container adaptors queue, priority_queue, and stack.

The container adaptors each take a Container template parameter, and each constructor takes a Container reference argument. This container is copied into the Container member of each adaptor. If the container takes an allocator, then a compatible allocator may be passed in to the adaptor's constructor. Otherwise, normal copy or move construction is used for the container argument.

For container adaptors, no swap function throws an exception unless that exception is thrown by the swap of the adaptor's Container or Compare object (if any).

23.6.2 Header <queue> synopsis [queue.syn]

#include <initializer_list>

namespace std {

  template <class T, class Container = deque<T> > class queue;
  template <class T, class Container = vector<T>,
    class Compare = less<typename Container::value_type> >
      class priority_queue;

  template <class T, class Container>
    bool operator==(const queue<T, Container>& x,const queue<T, Container>& y);
  template <class T, class Container>
    bool operator< (const queue<T, Container>& x,const queue<T, Container>& y);
  template <class T, class Container>
    bool operator!=(const queue<T, Container>& x,const queue<T, Container>& y);
  template <class T, class Container>
    bool operator> (const queue<T, Container>& x,const queue<T, Container>& y);
  template <class T, class Container>
    bool operator>=(const queue<T, Container>& x,const queue<T, Container>& y);
  template <class T, class Container>
    bool operator<=(const queue<T, Container>& x,const queue<T, Container>& y);

  template <class T, class Container>
    void swap(queue<T, Container>& x, queue<T, Container>& y) noexcept(noexcept(x.swap(y)));
  template <class T, class Container, class Compare>
    void swap(priority_queue<T, Container, Compare>& x,
              priority_queue<T, Container, Compare>& y) noexcept(noexcept(x.swap(y)));
}

23.6.3 Class template queue [queue]

23.6.3.1 queue definition [queue.defn]

Any sequence container supporting operations front(), back(), push_back() and pop_front() can be used to instantiate queue. In particular, list ([list]) and deque ([deque]) can be used.

namespace std {
  template <class T, class Container = deque<T> >
  class queue {
  public:
    typedef typename Container::value_type            value_type;
    typedef typename Container::reference             reference;
    typedef typename Container::const_reference       const_reference;
    typedef typename Container::size_type             size_type;
    typedef          Container                        container_type;
  protected:
    Container c;

  public:
    explicit queue(const Container&);
    explicit queue(Container&& = Container());
    template <class Alloc> explicit queue(const Alloc&);
    template <class Alloc> queue(const Container&, const Alloc&);
    template <class Alloc> queue(Container&&, const Alloc&);
    template <class Alloc> queue(const queue&, const Alloc&);
    template <class Alloc> queue(queue&&, const Alloc&);

    bool              empty() const     { return c.empty(); }
    size_type         size()  const     { return c.size(); }
    reference         front()           { return c.front(); }
    const_reference   front() const     { return c.front(); }
    reference         back()            { return c.back(); }
    const_reference   back() const      { return c.back(); }
    void push(const value_type& x)      { c.push_back(x); }
    void push(value_type&& x)           { c.push_back(std::move(x)); }
    template <class... Args> void emplace(Args&&... args)
      { c.emplace_back(std::forward<Args>(args)...); }
    void pop()                          { c.pop_front(); }
    void swap(queue& q) noexcept(noexcept(swap(c, q.c)))
      { using std::swap; swap(c, q.c); }
  };

  template <class T, class Container>
    bool operator==(const queue<T, Container>& x, const queue<T, Container>& y);
  template <class T, class Container>
    bool operator< (const queue<T, Container>& x, const queue<T, Container>& y);
  template <class T, class Container>
    bool operator!=(const queue<T, Container>& x, const queue<T, Container>& y);
  template <class T, class Container>
    bool operator> (const queue<T, Container>& x, const queue<T, Container>& y);
  template <class T, class Container>
    bool operator>=(const queue<T, Container>& x, const queue<T, Container>& y);
  template <class T, class Container>
    bool operator<=(const queue<T, Container>& x, const queue<T, Container>& y);

  template <class T, class Container>
    void swap(queue<T, Container>& x, queue<T, Container>& y) noexcept(noexcept(x.swap(y)));

  template <class T, class Container, class Alloc>
    struct uses_allocator<queue<T, Container>, Alloc>
      : uses_allocator<Container, Alloc>::type { };
}

23.6.3.2 queue constructors [queue.cons]

explicit queue(const Container& cont);

Effects: Initializes c with cont.

explicit queue(Container&& cont = Container());

Effects: Initializes c with std::move(cont).

23.6.3.3 queue constructors with allocators [queue.cons.alloc]

If uses_allocator<container_type, Alloc>::value is false the constructors in this subclause shall not participate in overload resolution.

template <class Alloc> explicit queue(const Alloc& a);

Effects: Initializes c with a.

template <class Alloc> queue(const container_type& cont, const Alloc& a);

Effects: Initializes c with cont as the first argument and a as the second argument.

template <class Alloc> queue(container_type&& cont, const Alloc& a);

Effects: Initializes c with std::move(cont) as the first argument and a as the second argument.

template <class Alloc> queue(const queue& q, const Alloc& a);

Effects: Initializes c with q.c as the first argument and a as the second argument.

template <class Alloc> queue(queue&& q, const Alloc& a);

Effects: Initializes c with std::move(q.c) as the first argument and a as the second argument.

23.6.3.4 queue operators [queue.ops]

template <class T, class Container> bool operator==(const queue<T, Container>& x, const queue<T, Container>& y);

Returns: x.c == y.c.

template <class T, class Container> bool operator!=(const queue<T, Container>& x, const queue<T, Container>& y);

Returns: x.c != y.c.

template <class T, class Container> bool operator< (const queue<T, Container>& x, const queue<T, Container>& y);

Returns: x.c < y.c.

template <class T, class Container> bool operator<=(const queue<T, Container>& x, const queue<T, Container>& y);

Returns: x.c <= y.c.

template <class T, class Container> bool operator> (const queue<T, Container>& x, const queue<T, Container>& y);

Returns: x.c > y.c.

template <class T, class Container> bool operator>=(const queue<T, Container>& x, const queue<T, Container>& y);

Returns: x.c >= y.c.

23.6.3.5 queue specialized algorithms [queue.special]

template <class T, class Container> void swap(queue<T, Container>& x, queue<T, Container>& y) noexcept(noexcept(x.swap(y)));

Effects: x.swap(y).

23.6.4 Class template priority_queue [priority.queue]

Any sequence container with random access iterator and supporting operations front(), push_back() and pop_back() can be used to instantiate priority_queue. In particular, vector ([vector]) and deque ([deque]) can be used. Instantiating priority_queue also involves supplying a function or function object for making priority comparisons; the library assumes that the function or function object defines a strict weak ordering ([alg.sorting]).

namespace std {
  template <class T, class Container = vector<T>,
    class Compare = less<typename Container::value_type> >
  class priority_queue {
  public:
    typedef typename Container::value_type            value_type;
    typedef typename Container::reference             reference;
    typedef typename Container::const_reference       const_reference;
    typedef typename Container::size_type             size_type;
    typedef          Container                        container_type;
  protected:
    Container c;
    Compare comp;

  public:
    priority_queue(const Compare& x, const Container&);
    explicit priority_queue(const Compare& x = Compare(), Container&& = 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&);

    bool      empty() const       { return c.empty(); }
    size_type size()  const       { return c.size(); }
    const_reference   top() const { return c.front(); }
    void push(const value_type& x);
    void push(value_type&& x);
    template <class... Args> void emplace(Args&&... args);
    void pop();
    void swap(priority_queue& q) noexcept(
        noexcept(swap(c, q.c)) && noexcept(swap(comp, q.comp)))
      { using std::swap; swap(c, q.c); swap(comp, q.comp); }
  };
  // no equality is provided
  template <class T, class Container, class Compare>
    void swap(priority_queue<T, Container, Compare>& x,
              priority_queue<T, Container, Compare>& y) noexcept(noexcept(x.swap(y)));

  template <class T, class Container, class Compare, class Alloc>
    struct uses_allocator<priority_queue<T, Container, Compare>, Alloc>
      : uses_allocator<Container, Alloc>::type { };
}

23.6.4.1 priority_queue constructors [priqueue.cons]

priority_queue(const Compare& x, const Container& y); explicit priority_queue(const Compare& x = Compare(), Container&& y = Container());

Requires: x shall define a strict weak ordering ([alg.sorting]).

Effects: Initializes comp with x and c with y (copy constructing or move constructing as appropriate); calls make_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());

Requires: x shall define a strict weak ordering ([alg.sorting]).

Effects: Initializes comp with x and c with y (copy constructing or move constructing as appropriate); calls c.insert(c.end(), first, last); and finally calls make_heap(c.begin(), c.end(), comp).

23.6.4.2 priority_queue constructors with allocators [priqueue.cons.alloc]

If uses_allocator<container_type, Alloc>::value is false the constructors in this subclause shall not participate in overload resolution.

template <class Alloc> explicit priority_queue(const Alloc& a);

Effects: Initializes c with a and value-initializes comp.

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

Effects: Initializes c with a and initializes comp with compare.

template <class Alloc> priority_queue(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.

template <class Alloc> priority_queue(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.

template <class Alloc> priority_queue(const priority_queue& q, const Alloc& a);

Effects: Initializes c with q.c as the first argument and a as the second argument, and initializes comp with q.comp.

template <class Alloc> priority_queue(priority_queue&& q, const Alloc& a);

Effects: Initializes c with std::move(q.c) as the first argument and a as the second argument, and initializes comp with std::move(q.comp).

23.6.4.3 priority_queue members [priqueue.members]

void push(const value_type& x);

Effects:

c.push_back(x);
push_heap(c.begin(), c.end(), comp);

void push(value_type&& x);

Effects:

c.push_back(std::move(x));
push_heap(c.begin(), c.end(), comp);

template <class... Args> void emplace(Args&&... args)

Effects:

c.emplace_back(std::forward<Args>(args)...);
push_heap(c.begin(), c.end(), comp);

void pop();

Effects:

pop_heap(c.begin(), c.end(), comp);
c.pop_back();

23.6.4.4 priority_queue specialized algorithms [priqueue.special]

template <class T, class Container, Compare> void swap(priority_queue<T, Container, Compare>& x, priority_queue<T, Container, Compare>& y) noexcept(noexcept(x.swap(y)));

Effects: x.swap(y).

23.6.5 Class template stack [stack]

Any sequence container supporting operations back(), push_back() and pop_back() can be used to instantiate stack. In particular, vector ([vector]), list ([list]) and deque ([deque]) can be used.

23.6.5.1 Header <stack> synopsis [stack.syn]

#include <initializer_list>

namespace std {

  template <class T, class Container = deque<T> > class stack;
  template <class T, class Container>
    bool operator==(const stack<T, Container>& x,const stack<T, Container>& y);
  template <class T, class Container>
    bool operator< (const stack<T, Container>& x,const stack<T, Container>& y);
  template <class T, class Container>
    bool operator!=(const stack<T, Container>& x,const stack<T, Container>& y);
  template <class T, class Container>
    bool operator> (const stack<T, Container>& x,const stack<T, Container>& y);
  template <class T, class Container>
    bool operator>=(const stack<T, Container>& x,const stack<T, Container>& y);
  template <class T, class Container>
    bool operator<=(const stack<T, Container>& x,const stack<T, Container>& y);
  template <class T, class Container>
    void swap(stack<T, Container>& x, stack<T, Container>& y) noexcept(noexcept(x.swap(y)));
}

23.6.5.2 stack definition [stack.defn]

namespace std {
  template <class T, class Container = deque<T> >
  class stack {
  public:
    typedef typename Container::value_type            value_type;
    typedef typename Container::reference             reference;
    typedef typename Container::const_reference       const_reference;
    typedef typename Container::size_type             size_type;
    typedef          Container                        container_type;
  protected:
    Container c;

  public:
    explicit stack(const Container&);
    explicit stack(Container&& = Container());
    template <class Alloc> explicit stack(const Alloc&);
    template <class Alloc> stack(const Container&, const Alloc&);
    template <class Alloc> stack(Container&&, const Alloc&);
    template <class Alloc> stack(const stack&, const Alloc&);
    template <class Alloc> stack(stack&&, const Alloc&);

    bool      empty() const             { return c.empty(); }
    size_type size()  const             { return c.size(); }
    reference         top()             { return c.back(); }
    const_reference   top() const       { return c.back(); }
    void push(const value_type& x)      { c.push_back(x); }
    void push(value_type&& x)           { c.push_back(std::move(x)); }
    template <class... Args> void emplace(Args&&... args)
      { c.emplace_back(std::forward<Args>(args)...); }
    void pop()                          { c.pop_back(); }
    void swap(stack& s) noexcept(noexcept(swap(c, s.c)))
      { using std::swap; swap(c, s.c); }
  };

  template <class T, class Container>
    bool operator==(const stack<T, Container>& x, const stack<T, Container>& y);
  template <class T, class Container>
    bool operator< (const stack<T, Container>& x, const stack<T, Container>& y);
  template <class T, class Container>
    bool operator!=(const stack<T, Container>& x, const stack<T, Container>& y);
  template <class T, class Container>
    bool operator> (const stack<T, Container>& x, const stack<T, Container>& y);
  template <class T, class Container>
    bool operator>=(const stack<T, Container>& x, const stack<T, Container>& y);
  template <class T, class Container>
    bool operator<=(const stack<T, Container>& x, const stack<T, Container>& y);
  template <class T, class Container>
    void swap(stack<T, Container>& x, stack<T, Container>& y) noexcept(noexcept(x.swap(y)));

  template <class T, class Container, class Alloc>
    struct uses_allocator<stack<T, Container>, Alloc>
      : uses_allocator<Container, Alloc>::type { };
}

23.6.5.3 stack constructors [stack.cons]

explicit stack(const Container& cont);

Effects: Initializes c with cont.

explicit stack(Container&& cont = Container());

Effects: Initializes c with std::move(cont).

23.6.5.4 stack constructors with allocators [stack.cons.alloc]

If uses_allocator<container_type, Alloc>::value is false the constructors in this subclause shall not participate in overload resolution.

template <class Alloc> explicit stack(const Alloc& a);

Effects: Initializes c with a.

template <class Alloc> stack(const container_type& cont, const Alloc& a);

Effects: Initializes c with cont as the first argument and a as the second argument.

template <class Alloc> stack(container_type&& cont, const Alloc& a);

Effects: Initializes c with std::move(cont) as the first argument and a as the second argument.

template <class Alloc> stack(const stack& s, const Alloc& a);

Effects: Initializes c with s.c as the first argument and a as the second argument.

template <class Alloc> stack(stack&& s, const Alloc& a);

Effects: Initializes c with std::move(s.c) as the first argument and a as the second argument.

23.6.5.5 stack operators [stack.ops]

template <class T, class Container> bool operator==(const stack<T, Container>& x, const stack<T, Container>& y);

Returns: x.c == y.c.

template <class T, class Container> bool operator!=(const stack<T, Container>& x, const stack<T, Container>& y);

Returns: x.c != y.c.

template <class T, class Container> bool operator< (const stack<T, Container>& x, const stack<T, Container>& y);

Returns: x.c < y.c.

template <class T, class Container> bool operator<=(const stack<T, Container>& x, const stack<T, Container>& y);

Returns: x.c <= y.c.

template <class T, class Container> bool operator> (const stack<T, Container>& x, const stack<T, Container>& y);

Returns: x.c > y.c.

template <class T, class Container> bool operator>=(const stack<T, Container>& x, const stack<T, Container>& y);

Returns: x.c >= y.c.

23.6.5.6 stack specialized algorithms [stack.special]

template <class T, class Container> void swap(stack<T, Container>& x, stack<T, Container>& y) noexcept(noexcept(x.swap(y)));

Effects: x.swap(y).