Issue 307: Lack of reference typedefs in container adaptors (original) (raw)
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: 23.3.11 [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 23.3.11.3 [list.capacity]paragraph 1 and 23.3.11.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 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:
- Modifying these paragraphs to say that vector is an exception.
- Removing the vector specialization.
- 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(i)); 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 > 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 > 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, class Compare = less > 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, class Compare = less > 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 > 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 > 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.]