This page is a snapshot from the LWG issues list, see the Library Active Issues List for more information and the meaning of CD1 status.

### 307. Lack of reference typedefs in container adaptors

Section: 22.3.10 [list] Status: CD1 Submitter: Howard Hinnant Opened: 2001-03-13 Last modified: 2016-01-28

Priority: Not Prioritized

View all issues with CD1 status.

Discussion:

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

The standard is currently inconsistent in 22.3.10.3 [list.capacity] paragraph 1 and 22.3.10.4 [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.

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

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