Consistent Insertion into Standard Containers

Document Number: n2206(07-0066)
2007-03-09
Alisdair Meredith <alisdair.meredith@uk.renaultf1.com>

Motivation

The standard library offers a variety of containers that strive to offer a consistent interface. One common feature is the ability to insert elements into the container, and where efficiently supported there are special functions to insert at the beginning or end. However, these operations are not consistently overloaded to accept the same set of values. This leads to unfulfilled user expectations, and in the worst cases (such as container adapters) inefficent code that is easily worked around by the user supplying their own replacement adapter.

By supplying the missing overloads, implementers can use additional information to provide more effient implementations for range operations, or stronger exception-safety semantics. This paper does make either of these a requirement though.

Recommended changes

All sequence containers with an insert member function should have overloads that accept single values and ranges of values marked by an iterator pair. If concept-based overloading is adopted, it would be further recommended to overload on a single range/view value as well.

All sequence containers with a push_back member function should have overloads that accept single values and ranges of values marked by an iterator pair. If concept-based overloading is adopted, it would be further recommended to overload on a single range/view value as well.

All sequence containers with a push_front member function should have overloads that accept single values and ranges of values marked by an iterator pair. If concept-based overloading is adopted, it would be further recommended to overload on a single range/view value as well.

All sequence-adapters with a push member function should have overloads that accept single values and ranges of values marked by an iterator pair. If concept-based overloading is adopted, it would be further recommended to overload on a single range/view value as well. These overloads will call the appropiately function in the adapted type i.e. stack would call the appropariate push_back overload while queue would call push_front

All sequence-adapters have a constructor template that accepts ranges of values marked by an iterator pair. If concept-based overloading is adopted, it would be further recommended to overload on a single range/view value as well.

It is noted that the associative containers already have the appropriate interface.

Optional changes

Many containers overload their insert function to accept a number of values marked by a count, and a value to copy. To maintain a consistent interface, these might be overloaded as well.

Normative changes

Add the following overloads to the deque template:
  • template <InputIterator> void push_back( InputIterator first, InputIterator last )
  • void push_back( size_type n, const T & value )
  • template <InputIterator> void push_front( InputIterator first, InputIterator last )
  • void push_front( size_type n, const T & value )
  • Add the following overloads to the list template:

  • template <InputIterator> void push_back( InputIterator first, InputIterator last )
  • void push_back( size_type n, const T & value )
  • template <InputIterator> void push_front( InputIterator first, InputIterator last )
  • void push_front( size_type n, const T & value )
  • Add the following overloads to the vector template:

  • template <InputIterator> void push_back( InputIterator first, InputIterator last )
  • void push_back( size_type n, const T & value )
  • Add the following overloads to the priority_queue template:

  • template <InputIterator> void push( InputIterator first, InputIterator last )
  • void push( size_type n, const T & value )
  • Add the following overloads to the queue template:

  • template <InputIterator> queue( InputIterator first, InputIterator last )
  • template <InputIterator> void push( InputIterator first, InputIterator last )
  • void push( size_type n, const T & value )
  • Add the following overloads to the stack template:

  • template <InputIterator> stack( InputIterator first, InputIterator last )
  • template <InputIterator> void push( InputIterator first, InputIterator last )
  • void push( size_type n, const T & value )