[ Copenhagen: This change was discussed before the IS was released and it was deliberately not adopted. Nevertheless, the LWG believes (straw poll: 10-2) that it is a genuine defect. ]

Proposed resolution:

Summary: Add reference and const_reference typedefs to queue, priority_queue and stack. Change return types of "value_type&" to "reference". Change return types of "const value_type&" to "const_reference". Details:

Change 23.2.3.1/1 from:

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

    public:
      explicit queue(const Container& = Container());

      bool      empty() const             { return c.empty(); }
      size_type size()  const             { return c.size(); }
      value_type&       front()           { return c.front(); }
      const value_type& front() const     { return c.front(); }
      value_type&       back()            { return c.back(); }
      const value_type& back() const      { return c.back(); }
      void push(const value_type& x)      { c.push_back(x); }
      void pop()                          { c.pop_front(); }
    };

to:

  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::value_type            value_type;
      typedef typename Container::size_type             size_type;
      typedef          Container                        container_type;
    protected:
      Container c;

    public:
      explicit queue(const Container& = Container());

      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 pop()                          { c.pop_front(); }
    };

Change 23.2.3.2/1 from:

  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::size_type             size_type;
      typedef          Container                        container_type;
    protected:
      Container c;
      Compare comp;

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

      bool      empty() const       { return c.empty(); }
      size_type size()  const       { return c.size(); }
      const value_type& top() const { return c.front(); }
      void push(const value_type& x);
      void pop();
    };
                                  //  no equality is provided
  }

to:

  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:
      explicit priority_queue(const Compare& x = Compare(),
                              const Container& = Container());
      template <class InputIterator>
        priority_queue(InputIterator first, InputIterator last,
                       const Compare& x = Compare(),
                       const Container& = Container());

      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 pop();
    };
                                  //  no equality is provided
  }

And change 23.2.3.3/1 from:

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

    public:
      explicit stack(const Container& = Container());

      bool      empty() const             { return c.empty(); }
      size_type size()  const             { return c.size(); }
      value_type&       top()             { return c.back(); }
      const value_type& top() const       { return c.back(); }
      void push(const value_type& x)      { c.push_back(x); }
      void pop()                          { c.pop_back(); }
    };

    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);
  }

to:

  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& = Container());

      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 pop()                          { c.pop_back(); }
    };

    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);
  }

From reflector message c++std-lib-8330. See also lib-8317.

The standard is currently inconsistent in [list.capacity] paragraph 1 and [list.modifiers] paragraph 1. 23.2.3.3/1, for example, says:

-1- Any sequence supporting operations back(), push_back() and pop_back() can be used to instantiate stack. In particular, vector (lib.vector), list (lib.list) and deque (lib.deque) can be used.

But this is false: vector<bool> can not be used, because the container adaptors return a T& rather than using the underlying container's reference type.

This is a contradiction that can be fixed by:

1. Modifying these paragraphs to say that vector<bool> is an exception.
2. Removing the vector<bool> specialization.
3. Changing the return types of stack and priority_queue to use reference typedef's.

I propose 3. This does not preclude option 2 if we choose to do it later (see issue 96); the issues are independent. Option 3 offers a small step towards support for proxied containers. This small step fixes a current contradiction, is easy for vendors to implement, is already implemented in at least one popular lib, and does not break any code.