Document number: N1858=05-0118

Howard E. Hinnant
2005-08-26

Rvalue Reference Recommendations for Chapter 23

Contents

Related papers

Rvalue Reference Recommendations for Chapter 20
Rvalue Reference Recommendations for Chapter 21
Rvalue Reference Recommendations for Chapter 24
Rvalue Reference Recommendations for Chapter 25
Rvalue Reference Recommendations for Chapter 26
Rvalue Reference Recommendations for Chapter 27

Introduction

This paper recommends proposed wording with respect to the rvalue reference for the C++0X working draft. This paper restricts its scope to Chapter 23 "Containers library" for the purpose of breaking the library work associated with the rvalue reference up into manageable chunks. This paper largely follows the lead of N1771: Impact of the rvalue reference on the Standard Library, but adds more detail as appropriate.

With the exception of this introduction, all non-proposed wording will have a background color and formatting that

looks like this, so that motivation and description is more easily distinguished from proposed wording.

In the proposed wording below, text to be inserted is formatted like this, while wording to be deleted is formatted like this.

The proposed wording in this paper will give all containers:

23.1 - Container requirements

The changes in this section removes the requirements that the container's value_type be CopyConstructible and CopyAssignable (except where noted). The container's copy constructor and copy assignment operator are specifically excepted in a blanket statement in paragraph 3.

Note that this change is in agreement with lwg issue 276 (Assignable requirement for container value type overly strict), but goes much further. Only a few members of deque, list and vector now need the CopyAssignable requirement.

See N1771 for a compact synopsis of which container members require CopyConstructible and CopyAssignable.

The Assignable requirement has been renamed to CopyAssignable and moved to the requirements section of chapter 20 (20.1.6).

The container requirements are updated to reflect that each container must have a constant complexity move constructor and move assignment operator.

Paragraph 13 gives a nod towards performance by making clients responsible for assuring that container member functions taking rvalues aren't referencing elements of the same container. For example:

vector<string> v(10, "a string");
v.insert(v.begin(), move(v.back())); // undefined behavior: violates 23.1p13

-3- The type of objects stored in these components shall meet the requirements of CopyConstructible types (20.1.3) MoveConstructible and MoveAssignable types. Additionally for some member functions (as noted below), the types must meet the requirements of CopyConstructible and/or CopyAssignable types. The copy constructor of each container requires the contained element type to be CopyConstructible. The copy assignment operator of each sequence container requires the contained type to be both CopyConstructible and CopyAssignable. The copy assignment operator of each associative container requires the contained type to be CopyConstructible.

-4- Table 65 defines the Assignable requirement. Some containers require this property of the types to be stored in the container. T is the type used to instantiate the container, t is a value of T, and u is a value of (possibly const) T.

Delete Table 65 (this requirement has been moved to Chapter 20):

Table 65: Assignable requirements
expression return type post-condition
t == u T& t is equivalent to u

-5- In Tables 66 and 67, X denotes a container class containing objects of type T, a and b denote values of type X, u denotes an identifier, and r denotes a value of X& an lvalue or a const rvalue of type X, and rv denotes a non-const rvalue of type X.

Add two rows to Table 66, Container requirements:

X a = rv   MoveConstructible Equal to the value of rv before construction constant
a = rv X& MoveAssignable a is equal to the value of rv before assignment constant

-13- Those container member functions with rvalue-reference parameters may assume that the reference truly refers to an rvalue, and specifically is not a reference into the same container.

23.2 - Sequences

This section is updated with extra swap signatures for each sequence, and container adaptor. Also the needless global function signatures for vector<bool> are removed. This reflects lwg issue 469, but 469 only addresses the relational operators. The swap overload for vector<bool> is removed by the same rationale.

The extra swap signatures are to allow clients to swap:

but not

This should make it easier to read, write and teach the "shrink to fit with swap" idiom, which up till now can only be coded as:

vector<A>(a).swap(a);

But now can additionally be coded with any of the following expressions:

swap(vector<A>(a), a);
swap(a, vector<A>(a));
a.swap(vector<A>(a));

Note that although the namespace scope swap signatures do prohibit swaping two rvalues, it is still possible to swap two rvalues using the member swap function:

vector<A>(a).swap(vector<A>());

Such code will probably not appear accidently and so this author does not believe that this is problematic. However N1784 does offer a way to solve this problem if it is deemed sufficiently important. It would involve three member swap overloads instead of the current one:

template <class T>
class container
{
    ...
    void swap(container&)  &;
    void swap(container&&) &;
    void swap(container&) &&;
    ...
};

-1- Headers <deque>, <list>, <queue>, <stack>, and <vector>.

Header <deque> synopsis

namespace std {
  template <class T, class Allocator = allocator<T> > class deque;
  template <class T, class Allocator>
    bool operator==
      (const deque<T,Allocator>& x, const deque<T,Allocator>& y);
  template <class T, class Allocator>
    bool operator<
      (const deque<T,Allocator>& x, const deque<T,Allocator>& y);
  template <class T, class Allocator>
    bool operator!=
      (const deque<T,Allocator>& x, const deque<T,Allocator>& y);
  template <class T, class Allocator>
    bool operator>
      (const deque<T,Allocator>& x, const deque<T,Allocator>& y);
  template <class T, class Allocator>
    bool operator>=
      (const deque<T,Allocator>& x, const deque<T,Allocator>& y);
  template <class T, class Allocator>
    bool operator<=
      (const deque<T,Allocator>& x, const deque<T,Allocator>& y);
  template <class T, class Allocator>
    void swap(deque<T,Allocator>& x, deque<T,Allocator>& y);
  template <class T, class Allocator>
    void swap(deque<T,Allocator>&& x, deque<T,Allocator>& y);
  template <class T, class Allocator>
    void swap(deque<T,Allocator>& x, deque<T,Allocator>&& y);
}

Header <list> synopsis

namespace std {
  template <class T, class Allocator = allocator<T> > class list;
  template <class T, class Allocator>
    bool operator==(const list<T,Allocator>& x, const list<T,Allocator>& y);
  template <class T, class Allocator>
    bool operator< (const list<T,Allocator>& x, const list<T,Allocator>& y);
  template <class T, class Allocator>
    bool operator!=(const list<T,Allocator>& x, const list<T,Allocator>& y);
  template <class T, class Allocator>
    bool operator> (const list<T,Allocator>& x, const list<T,Allocator>& y);
  template <class T, class Allocator>
    bool operator>=(const list<T,Allocator>& x, const list<T,Allocator>& y);
  template <class T, class Allocator>
    bool operator<=(const list<T,Allocator>& x, const list<T,Allocator>& y);
  template <class T, class Allocator>
    void swap(list<T,Allocator>& x, list<T,Allocator>& y);
  template <class T, class Allocator>
    void swap(list<T,Allocator>&& x, list<T,Allocator>& y);
  template <class T, class Allocator>
    void swap(list<T,Allocator>& x, list<T,Allocator>&& y);
}

Header <queue> synopsis

namespace std {
  template <class T, class Container = deque<T> > class 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);
  template <class T, class Container>
    void swap(queue<T, Container>&& x,
              queue<T, Container>& y);
  template <class T, class Container>
    void swap(queue<T, Container>& x,
              queue<T, Container>&& y);

  template <class T, class Container = vector<T>,
	    class Compare = less<typename Container::value_type> >
  class priority_queue;
  template <class T, class Container, class Compare>
    void swap(priority_queue<T, Container, Compare>& x,
              priority_queue<T, Container, Compare>& y);
  template <class T, class Container, class Compare>
    void swap(priority_queue<T, Container, Compare>&& x,
              priority_queue<T, Container, Compare>& y);
  template <class T, class Container, class Compare>
    void swap(priority_queue<T, Container, Compare>& x,
              priority_queue<T, Container, Compare>&& y);
}

Header <stack> synopsis

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);
  template <class T, class Container>
    void swap(stack<T, Container>&& x, stack<T, Container>& y);
  template <class T, class Container>
    void swap(stack<T, Container>& x, stack<T, Container>&& y);
}

Header <vector> synopsis

namespace std {
  template <class T, class Allocator = allocator<T> > class vector;
  template <class T, class Allocator>
    bool operator==(const vector<T,Allocator>& x,
		    const vector<T,Allocator>& y);
  template <class T, class Allocator>
    bool operator< (const vector<T,Allocator>& x,
		    const vector<T,Allocator>& y);
  template <class T, class Allocator>
    bool operator!=(const vector<T,Allocator>& x,
		    const vector<T,Allocator>& y);
  template <class T, class Allocator>
    bool operator> (const vector<T,Allocator>& x,
		    const vector<T,Allocator>& y);
  template <class T, class Allocator>
    bool operator>=(const vector<T,Allocator>& x,
		    const vector<T,Allocator>& y);
  template <class T, class Allocator>
    bool operator<=(const vector<T,Allocator>& x,
		    const vector<T,Allocator>& y);
  template <class T, class Allocator>
    void swap(vector<T,Allocator>& x, vector<T,Allocator>& y);
  template <class T, class Allocator>
    void swap(vector<T,Allocator>&& x, vector<T,Allocator>& y);
  template <class T, class Allocator>
    void swap(vector<T,Allocator>& x, vector<T,Allocator>&& y);

  template <class Allocator> class vector<bool,Allocator>;
  template <class Allocator>
    bool operator==(const vector<bool,Allocator>& x,
		    const vector<bool,Allocator>& y);
  template <class Allocator>
    bool operator< (const vector<bool,Allocator>& x,
		    const vector<bool,Allocator>& y);
  template <class Allocator>
    bool operator!=(const vector<bool,Allocator>& x,
		    const vector<bool,Allocator>& y);
  template <class Allocator>
    bool operator> (const vector<bool,Allocator>& x,
		    const vector<bool,Allocator>& y);
  template <class Allocator>
    bool operator>=(const vector<bool,Allocator>& x,
		    const vector<bool,Allocator>& y);
  template <class Allocator>
    bool operator<=(const vector<bool,Allocator>& x,
		    const vector<bool,Allocator>& y);
  template <class Allocator>
    void swap(vector<bool,Allocator>& x, vector<bool,Allocator>& y);
}

23.2.1 - Class template deque

The rationale below applies to all sequences.

Each sequence currently has a constructor similar to the deque constructor:

explicit deque(size_type n, const T& value = T(), const Allocator& = Allocator());

This paper proposes that this constructor be split into two as follows:

explicit deque(size_type n);
deque(size_type n, const T& value, const Allocator& = Allocator());

The rationale for this change is to allow the size_type constructor to work with types which aren't CopyConstructible. That is, the first (proposed) constructor would default construct n value_type's into the container instead of today's behavior of default constructing one value_type and then copy constructing that value n times. This will allow (for example):

deque<unique_ptr<T>> c(100);  // ok, 100 unique_ptr's default constructed

The second (proposed) constructor still requires CopyConstructible and so can not be used with movable but non-copyable types such as unique_ptr.

The member function resize is similarly split into two for the exact same reasons. The second signature still takes its parameter by value instead of by const reference. This does not reflect the author's preference. Rather that is a separate issue and not addressed in this paper.

All member functions which insert (or append, prepend, etc.) a single value_type into the container are overloaded with a member function that accepts that value_type by rvalue reference so that single value_type's can be moved into the container. This not only makes working with heavy weight types much more efficient, it also allows one to insert movable but non-copyable types into the container.

Finally, this paper makes a purely editorial statement by suggesting that redundant template parameters in the member functions be removed. For example:

deque(const deque<T,Allocator>& x);

There is no new functionality being proposed here. I'm simply trying to make the standard a little easier to read.

-2- A deque satisfies all of the requirements of a container and of a reversible container (given in tables in lib.container.requirements) and of a sequence, including the optional sequence requirements (lib.sequence.reqmts). Descriptions are provided here only for operations on deque that are not described in one of these tables or for operations where there is additional semantic information.

namespace std {
  template <class T, class Allocator = allocator<T> >
  class deque {
  public:
    //  types:
    typedef typename Allocator::reference         reference;
    typedef typename Allocator::const_reference   const_reference;
    typedef implementation defined                iterator;        //  See lib.container.requirements
    typedef implementation defined                const_iterator;  //  See lib.container.requirements
    typedef implementation defined                size_type;       //  See lib.container.requirements
    typedef implementation defined                difference_type; //  See lib.container.requirements
    typedef T                                     value_type;
    typedef Allocator                             allocator_type;
    typedef typename Allocator::pointer           pointer;
    typedef typename Allocator::const_pointer     const_pointer;
    typedef std::reverse_iterator<iterator>       reverse_iterator;
    typedef std::reverse_iterator<const_iterator> const_reverse_iterator;

    //  lib.deque.cons construct/copy/destroy:
    explicit deque(const Allocator& = Allocator());
    explicit deque(size_type n);
    explicit deque(size_type n, const T& value = T(),
        const Allocator& = Allocator());
    template <class InputIterator>
      deque(InputIterator first, InputIterator last,
            const Allocator& = Allocator());
    deque(const deque<T,Allocator>& x);
    deque(deque&& x);
   ~deque();
    deque<T,Allocator>& operator=(const deque<T,Allocator>& x);
    deque& operator=(deque&& x);
    template <class InputIterator>
      void assign(InputIterator first, InputIterator last);
    void assign(size_type n, const T& t);
    allocator_type get_allocator() const;

    //  iterators:
    iterator               begin();
    const_iterator         begin() const;
    iterator               end();
    const_iterator         end() const;
    reverse_iterator       rbegin();
    const_reverse_iterator rbegin() const;
    reverse_iterator       rend();
    const_reverse_iterator rend() const;

    //  lib.deque.capacity capacity:
    size_type size() const;
    size_type max_size() const;
    void      resize(size_type sz);
    void      resize(size_type sz, T c = T());
    bool      empty() const;

    //  element access:
    reference       operator[](size_type n);
    const_reference operator[](size_type n) const;
    reference       at(size_type n);
    const_reference at(size_type n) const;
    reference       front();
    const_reference front() const;
    reference       back();
    const_reference back() const;

    //  lib.deque.modifiers modifiers:
    void push_front(const T& x);
    void push_front(T&& x);
    void push_back(const T& x);
    void push_back(T&& x);

    iterator insert(iterator position, const T& x);
    iterator insert(iterator position, T&& x);
    void     insert(iterator position, size_type n, const T& x);
    template <class InputIterator>
      void insert (iterator position,
                   InputIterator first, InputIterator last);

    void pop_front();
    void pop_back();

    iterator erase(iterator position);
    iterator erase(iterator first, iterator last);
    void     swap(deque<T,Allocator>&&);
    void     clear();
  };

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

  //  specialized algorithms:
  template <class T, class Allocator>
    void swap(deque<T,Allocator>& x, deque<T,Allocator>& y);
  template <class T, class Allocator>
    void swap(deque<T,Allocator>&& x, deque<T,Allocator>& y);
  template <class T, class Allocator>
    void swap(deque<T,Allocator>& x, deque<T,Allocator>&& y);
}

23.2.1.1 - deque constructors, copy, and assignment

A description is added to support splitting the size,value,allocator constructor in two. We also need to add an explicit note that the new size,value,allocator constructor requires CopyConstructible since now this requirement is not assumed.

A statement about the CopyConstructible requirement is also added to the member template constructor. Note that this constructor doesn't always require CopyConstructible! (e.g. see move_iterator). This constructor also needs to promise not to dereference each iterator in the input range so that move_iterator can be used here.

Similar changes concerning requirements are made for the assign functions.

explicit deque(const Allocator& = Allocator());

-1- Effects: Constructs an empty deque, using the specified allocator.

-2- Complexity: Constant.


explicit deque(size_type n);

-3- Effects: Constructs a deque with n default constructed elements. [Note: Requires T to be default constructible. --end note]

-4- Complexity: Linear in n.

explicit deque(size_type n, const T& value = T(),
               const Allocator& = Allocator());

-5- Effects: Constructs a deque with n copies of value, using the specified allocator.

-6- Requires: T must be CopyConstructible.

-7- Complexity: Linear in n.

template <class InputIterator>
  deque(InputIterator first, InputIterator last,
        const Allocator& = Allocator());

-8- Effects: Constructs a deque equal to the the range [first, last), using the specified allocator. Each iterator in the range [first, last) is dereferenced exactly once.

-9- Requires: T must be CopyConstructible only if the dereferenced InputIterator returns an lvalue or const rvalue.

-10- Complexity: Makes distance(first, last) calls to the copy constructor of T.

template <class InputIterator>
  void assign(InputIterator first, InputIterator last);

-11- Effects:

erase(begin(), end());
insert(begin(), first, last);

Each iterator in the range [first, last) is dereferenced exactly once.

-12- Requires: T must be CopyConstructible and CopyAssignable only if the dereferenced InputIterator returns an lvalue or const rvalue.

void assign(size_type n, const T& t);

-13- Effects:

erase(begin(), end());
insert(begin(), n, t);

-14- Requires: T must be CopyConstructible and CopyAssignable.

23.2.1.2 - deque capacity

resize is split into two overloads. The first supports moveable but non-copyable types. The second now explicitly requires CopyConstructible. Note that the insert function used in the effects clause requires not only CopyConstructible but also CopyAssignable. But resize will never actually use CopyAssignable and therefore should not require it. Thus the code used to describe the effects of the second resize overload can't be used in an actual implementation.


void resize(size_type sz);

-1- Effects: If sz is less than size() then size() - sz elements are erased from the end of the sequence. Else sz - size() default constructed elements are appended to the sequence.

-2- Requires: T must be default constructible.

void resize(size_type sz, T c = T());

-3- Effects:

if (sz > size())
  insert(end(), sz-size(), c);
else if (sz < size())
  erase(begin()+sz, end());
else
  ;                           // do nothing

-4- Requires: T must be CopyConstructible.

23.2.1.3 - deque modifiers

Descriptions are added for push_front and push_back for the reason of adding the CopyConstructible requirement to the overload taking a const T&, and to introduce the overload taking a T&& parameter.

The insert descriptions are updated with the new overload, and new CopyConstructible and CopyAssignable requirements as appropriate. The "dereference once" promise is also added to the member template overload so that it can be used with iterators such as move_iterator. For example:

deque<string> d1, d2;
...
d2.insert(d2.end(), make_move_iterator(d1.begin()), make_move_iterator(d1.end());

In the above example the string's in d1 are moved as they are appended to d2.


void push_front(const T& x);
void push_front(T&& x);

-1- Effects: Prepends a copy of x to the beginning of the sequence.

-2- Requires: The signature with a const T& parameter requires T to be CopyConstructible.


void push_back(const T& x);
void push_back(T&& x);

-3- Effects: Appends a copy of x to the end of the sequence.

-4- Requires: The signature with a const T& parameter requires T to be CopyConstructible.

iterator insert(iterator position, const T& x);
iterator insert(iterator position, T&& x);
void     insert(iterator position, size_type n, const T& x);
template <class InputIterator>
  void insert(iterator position,
              InputIterator first, InputIterator last);

-3- Effects: An insert in the middle of the deque invalidates all the iterators and references to elements of the deque. An insert at either end of the deque invalidates all the iterators to the deque, but has no effect on the validity of references to elements of the deque. Each iterator in the range [first, last) is dereferenced exactly once.

-4- Notes: If an exception is thrown other than by the copy constructor or assignment operator of T there are no effects. The signatures taking a const T& parameter require T to be CopyConstructible and CopyAssignable. The signature taking InputIterator parameters requires T to be CopyConstructible and CopyAssignable only if the dereferenced InputIterator returns an lvalue or const rvalue.

-5- Complexity: In the worst case, inserting a single element into a deque takes time linear in the minimum of the distance from the insertion point to the beginning of the deque and the distance from the insertion point to the end of the deque. Inserting a single element either at the beginning or end of a deque always takes constant time and causes a single call to the copy constructor of T.

23.2.1.4 - deque specialized algorithms

Simply add the additional swap signatures:

template <class T, class Allocator>
  void swap(deque<T,Allocator>& x, deque<T,Allocator>& y);
template <class T, class Allocator>
  void swap(deque<T,Allocator>&& x, deque<T,Allocator>& y);
template <class T, class Allocator>
  void swap(deque<T,Allocator>& x, deque<T,Allocator>&& y);

-1- Effects:

x.swap(y);

23.2.2 - Class template list

Most of the rationale for the changes to list is the same as for deque. Please refer to the deque rationale for details that are not list-specific.

The splice and merge member functions have been modified to now accept either lvalue or rvalue lists. Otherwise the functionality of these members is unchanged (they already move from their arguments).

-2- A list satisfies all of the requirements of a container and of a reversible container (given in two tables in lib.container.requirements) and of a sequence, including most of the the optional sequence requirements (lib.sequence.reqmts). The exceptions are the operator[] and at member functions, which are not provided.*

[Footnote: These member functions are only provided by containers whose iterators are random access iterators. --- end foonote]

Descriptions are provided here only for operations on list that are not described in one of these tables or for operations where there is additional semantic information.

namespace std {
  template <class T, class Allocator = allocator<T> >
  class list {
  public:
    //  types:
    typedef typename Allocator::reference         reference;
    typedef typename Allocator::const_reference   const_reference;
    typedef implementation defined                iterator;       //  See lib.container.requirements
    typedef implementation defined                const_iterator; //  See lib.container.requirements
    typedef implementation defined                size_type;      //  See lib.container.requirements
    typedef implementation defined                difference_type;//  See lib.container.requirements
    typedef T                                     value_type;
    typedef Allocator                             allocator_type;
    typedef typename Allocator::pointer           pointer;
    typedef typename Allocator::const_pointer     const_pointer;
    typedef std::reverse_iterator<iterator>       reverse_iterator;
    typedef std::reverse_iterator<const_iterator> const_reverse_iterator;

    //  lib.list.cons construct/copy/destroy:
    explicit list(const Allocator& = Allocator());
    explicit list(size_type n);
    explicit list(size_type n, const T& value = T(),
		  const Allocator& = Allocator());
    template <class InputIterator>
      list(InputIterator first, InputIterator last,
	   const Allocator& = Allocator());
    list(const list<T,Allocator>& x);
    list(list&& x);
   ~list();
    list<T,Allocator>& operator=(const list<T,Allocator>& x);
    list& operator=(list&& x);
    template <class InputIterator>
      void assign(InputIterator first, InputIterator last);
    void assign(size_type n, const T& t);
    allocator_type get_allocator() const;

    // iterators:
    iterator               begin();
    const_iterator         begin() const;
    iterator               end();
    const_iterator         end() const;
    reverse_iterator       rbegin();
    const_reverse_iterator rbegin() const;
    reverse_iterator       rend();
    const_reverse_iterator rend() const;

    // lib.list.capacity capacity:
    bool      empty() const;
    size_type size() const;
    size_type max_size() const;
    void      resize(size_type sz);
    void      resize(size_type sz, T c = T());

    // element access:
    reference       front();
    const_reference front() const;
    reference       back();
    const_reference back() const;

    // lib.list.modifiers modifiers:
    void push_front(const T& x);
    void push_front(T&& x);
    void pop_front();
    void push_back(const T& x);
    void push_back(T&& x);
    void pop_back();

    iterator insert(iterator position, const T& x);
    iterator insert(iterator position, T&& x);
    void     insert(iterator position, size_type n, const T& x);
    template <class InputIterator>
      void insert(iterator position, InputIterator first,
		  InputIterator last);

    iterator erase(iterator position);
    iterator erase(iterator position, iterator last);
    void     swap(list<T,Allocator>&&);
    void     clear();

    // lib.list.ops list operations:
    void splice(iterator position, list<T,Allocator>&& x);
    void splice(iterator position, list<T,Allocator>&& x, iterator i);
    void splice(iterator position, list<T,Allocator>&& x, iterator first,
		iterator last);

    void remove(const T& value);
    template <class Predicate> void remove_if(Predicate pred);

    void unique();
    template <class BinaryPredicate>
      void unique(BinaryPredicate binary_pred);

    void merge(list<T,Allocator>&& x);
    template <class Compare> void merge(list<T,Allocator>&& x, Compare comp);

    void sort();
    template <class Compare> void sort(Compare comp);

    void reverse();
  };

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

  //  specialized algorithms:
  template <class T, class Allocator>
    void swap(list<T,Allocator>& x, list<T,Allocator>& y);
  template <class T, class Allocator>
    void swap(list<T,Allocator>&& x, list<T,Allocator>& y);
  template <class T, class Allocator>
    void swap(list<T,Allocator>& x, list<T,Allocator>&& y);
}

23.2.2.1 - list constructors, copy, and assignment

explicit list(const Allocator& = Allocator());

-1- Effects: Constructs an empty list, using the specified allocator.

-2- Complexity: Constant.


explicit list(size_type n);

-3- Effects: Constructs a list with n default constructed elements.

-4- Requires: T must be default constructible.

-5- Complexity: Linear in n.

explicit list(size_type n, const T& value = T(),
              const Allocator& = Allocator());

-6- Effects: Constructs a list with n copies of value, using the specified allocator.

-7- Requires: T must be CopyConstructible.

-8- Complexity: Linear in n.

template <class InputIterator>
list(InputIterator first, InputIterator last,
     const Allocator& = Allocator());

-9- Effects: Constructs a list equal to the range [first, last). Each iterator in the range [first, last) is dereferenced exactly once.

-10- Requires: T must be CopyConstructible only if the dereferenced InputIterator returns an lvalue or const rvalue.

-11- Complexity: Linear in first - last.

template <class InputIterator>
  void assign(InputIterator first, InputIterator last);

-12- Effects:

erase(begin(), end());
insert(begin(), first, last);

Each iterator in the range [first, last) is dereferenced exactly once.

-13- Requires: T must be CopyConstructible and CopyAssignable only if the dereferenced InputIterator returns an lvalue or const rvalue.

void assign(size_type n, const T& t);

-14- Effects:

erase(begin(), end());
insert(begin(), n, t);

-15- Requires: T must be CopyConstructible and CopyAssignable.

23.2.2.2 - list capacity


void resize(size_type sz);

-1- Effects: If sz is less than size() then size() - sz elements are erased from the end of the sequence. Else sz - size() default constructed elements are appended to the sequence.

-2- Requires: T must be default constructible.

void resize(size_type sz, T c = T());

-3- Effects:

if (sz > size())
  insert(end(), sz-size(), c);
else if (sz < size()) {
  iterator i = begin();
  advance(i, sz);
  erase(i, end());
}
else
  ;                           // do nothing

-4- Requires: T must be CopyConstructible.

23.2.2.3 - list modifiers

iterator insert(iterator position, const T& x);
iterator insert(iterator position, T&& x);
void     insert(iterator position, size_type n, const T& x);
template <class InputIterator>
  void insert(iterator position, InputIterator first,
              InputIterator last);
void push_front(const T& x);
void push_front(T&& x);
void push_back(const T& x);
void push_back(T&& x);

-1- Notes: Effects: Does not affect the validity of iterators and references. If an exception is thrown there are no effects. Each iterator in the range [first, last) is dereferenced exactly once.

-2- Requires: The signatures with a const T& parameter require T to be CopyConstructible. The signature taking InputIterator parameters requires T to be CopyConstructible only if the dereferenced InputIterator returns an lvalue or const rvalue.

-3- Complexity: Insertion of a single element into a list takes constant time and exactly one call to the copy constructor or move constructor of T. Insertion of multiple elements into a list is linear in the number of elements inserted, and the number of calls to the copy constructor or move constructor of T is exactly equal to the number of elements inserted.

23.2.2.4 - list operations

-2- list provides three splice operations that destructively move elements from one list to another.

void splice(iterator position, list<T,Allocator>&& x);

-3- Requires: &x != this.

-6- Complexity: Constant time.

void splice(iterator position, list<T,Allocator>&& x, iterator i);

-7- Effects: Inserts an element pointed to by i from list x before position and removes the element from x. The result is unchanged if position == i or position == ++i. Invalidates only the iterators and references to the spliced element.

-10- Complexity: Constant time.

void splice(iterator position, list<T,Allocator>&& x, iterator first,
            iterator last;

-11- Effects: Inserts elements in the range [first, last) before position and removes the elements from x.

-14- Complexity: Constant time if &x == this; otherwise, linear time.

void   merge(list<T,Allocator>&& x);
template <class Compare> void merge(list<T,Allocator>&& x, Compare comp);

Requires: comp defines a strict weak ordering (lib.alg.sorting), and the list and the argument list are both sorted according to this ordering.

23.2.2.5 - list specialized algorithms

template <class T, class Allocator>
  void swap(list<T,Allocator>& x, list<T,Allocator>& y);
template <class T, class Allocator>
  void swap(list<T,Allocator>&& x, list<T,Allocator>& y);
template <class T, class Allocator>
  void swap(list<T,Allocator>& x, list<T,Allocator>&& y);

-1- Effects:

  x.swap(y);

23.2.3 - Container adaptors

The main change to the container adaptors is the addition of swap (which they were completely lacking). Additionally support is added for moving both containers and elements through the adaptors. Finally each adaptor is given a constant complexity move constructor and move assignment operator.

23.2.3.1 - Class template queue

-1- Any sequence supporting operations front(), back(), push_back() and pop_front() can be used to instantiate queue. In particular, list (lib.list) and deque (lib.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::size_type             size_type;
    typedef          Container                        container_type;
  protected:
    Container c;

  public:
    explicit queue(const Container& = Container());
    explicit queue(Container&& = Container());
    queue(queue&& q)            : c(std::move(q.c)) {}
    queue& operator=(queue&& q) { c = std::move(q.c); return *this; }

    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 push(value_type&& x)           { c.push_back(std::move(x)); }
    void pop()                          { c.pop_front(); }
    void swap(queue&& q)                { c.swap(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);
}
operator==

-2- Returns: x.c == y.c.

operator<

-3- Returns: x.c < y.c.


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

-4- Effects: x.swap(y)

23.2.3.2 - Class template priority_queue

-1- Any sequence with random access iterator and supporting operations front(), push_back() and pop_back() can be used to instantiate priority_queue. In particular, vector (lib.vector) and deque (lib.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 (lib.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::size_type             size_type;
    typedef          Container                        container_type;
  protected:
    Container c;
    Compare comp;

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

    priority_queue(priority_queue&&)
    priority_queue& operator=(priority_queue&&)

    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 push(value_type&& x);
    void pop();
    void swap(priority_queue&&);
  };
				// 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);
  template <class T, class Container, class Compare>
    void swap(priority_queue<T, Container, Compare>&& x,
              priority_queue<T, Container, Compare>& y);
  template <class T, class Container, class Compare>
    void swap(priority_queue<T, Container, Compare>& x,
              priority_queue<T, Container, Compare>&& y);
}
23.2.3.2.1 - priority_queue constructors
priority_queue(const Compare& x = Compare(),
               const Container& y = Container());
priority_queue(const Compare& x = Compare(),
                     Container&& y = Container());

-1- Requires: x defines a strict weak ordering (lib.alg.sorting).

-2- Effects: Initializes comp with x and c with y (copy constructing or move constructing from y as appropriate); calls make_heap(c.begin(), c.end(), comp).

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

-3- Requires: x defines a strict weak ordering (lib.alg.sorting).

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

23.2.3.2.2 - priority_queue members
void push(const value_type& x);

-1- Effects:

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

void push(value_type&& x);

-2- Effects:


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

-3- Effects:

        pop_heap(c.begin(), c.end(), comp);
        c.pop_back();
23.2.3.2.3 - priority_queue specialized algorithms

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

-1- Effects: x.swap(y)

23.2.3.3 - Class template stack

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

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());
    explicit stack(const Container&& = Container());
    stack(stack&&);
    stack& operator=(stack&&);

    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 push(      value_type&& x)     { c.push_back(std::move(x)); }
    void pop()                          { c.pop_back(); }
    void swap(stack&& s)                { c.swap(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);
  template <class T, class Container>
    void swap(stack<T, Container>&& x,
              stack<T, Container>& y);
  template <class T, class Container>
    void swap(stack<T, Container>& x,
              stack<T, Container>&& y);
}

23.2.4 - Class template vector

Most of the rationale for the changes to vector is the same as for deque. Please refer to the deque rationale for details that are not vector-specific.

-2- A vector satisfies all of the requirements of a container and of a reversible container (given in two tables in lib.container.requirements) and of a sequence, including most of the optional sequence requirements (lib.sequence.reqmts). The exceptions are the push_front and pop_front member functions, which are not provided. Descriptions are provided here only for operations on vector that are not described in one of these tables or for operations where there is additional semantic information.

namespace std {
  template <class T, class Allocator = allocator<T> >
  class vector {
  public:
    //  types:
    typedef typename Allocator::reference         reference;
    typedef typename Allocator::const_reference   const_reference;
    typedef implementation defined                iterator;       //  See lib.container.requirements
    typedef implementation defined                const_iterator; //  See lib.container.requirements
    typedef implementation defined                size_type;      //  See lib.container.requirements
    typedef implementation defined                difference_type;//  See lib.container.requirements
    typedef T                                     value_type;
    typedef Allocator                             allocator_type;
    typedef typename Allocator::pointer           pointer;
    typedef typename Allocator::const_pointer     const_pointer
    typedef std::reverse_iterator<iterator>       reverse_iterator;
    typedef std::reverse_iterator<const_iterator> const_reverse_iterator;

    //  lib.vector.cons construct/copy/destroy:
    explicit vector(const Allocator& = Allocator());
    explicit vector(size_type n);
    explicit vector(size_type n, const T& value = T(),
        const Allocator& = Allocator());
    template <class InputIterator>
      vector(InputIterator first, InputIterator last,
        const Allocator& = Allocator());
    vector(const vector<T,Allocator>& x);
    vector(vector&&);
   ~vector();
    vector<T,Allocator>& operator=(const vector<T,Allocator>& x);
    vector& operator=(vector&&);
    template <class InputIterator>
      void assign(InputIterator first, InputIterator last);
    void assign(size_type n, const T& u);
    allocator_type get_allocator() const;

    //  iterators:
    iterator               begin();
    const_iterator         begin() const;
    iterator               end();
    const_iterator         end() const;
    reverse_iterator       rbegin();
    const_reverse_iterator rbegin() const;
    reverse_iterator       rend();
    const_reverse_iterator rend() const;

    //  lib.vector.capacity capacity:
    size_type size() const;
    size_type max_size() const;
    void      resize(size_type sz);
    void      resize(size_type sz, T c = T());
    size_type capacity() const;
    bool      empty() const;
    void      reserve(size_type n);

    //  element access:
    reference       operator[](size_type n);
    const_reference operator[](size_type n) const;
    const_reference at(size_type n) const;
    reference       at(size_type n);
    reference       front();
    const_reference front() const;
    reference       back();
    const_reference back() const;

    //  lib.vector.modifiers modifiers:
    void push_back(const T& x);
    void push_back(T&& x);
    void pop_back();
    iterator insert(iterator position, const T& x);
    iterator insert(iterator position, T&& x);
    void     insert(iterator position, size_type n, const T& x);
    template <class InputIterator>
        void insert(iterator position,
                    InputIterator first, InputIterator last);
    iterator erase(iterator position);
    iterator erase(iterator first, iterator last);
    void     swap(vector<T,Allocator>&&);
    void     clear();
  };

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

  //  specialized algorithms:
  template <class T, class Allocator>
    void swap(vector<T,Allocator>& x, vector<T,Allocator>& y);
  template <class T, class Allocator>
    void swap(vector<T,Allocator>&& x, vector<T,Allocator>& y);
  template <class T, class Allocator>
    void swap(vector<T,Allocator>& x, vector<T,Allocator>&& y);
}

23.2.4.1 - vector constructors, copy, and assignment


vector(const Allocator& = Allocator());

-1- Effects: Constructs an empty vector, using the specified allocator.

-2- Complexity: Constant.


explicit vector(size_type n);

-3- Effects: Constructs a vector with n default constructed elements. [Note: Requires T to be default constructible. --end note]

-4- Complexity: Linear in n.


vector(size_type n, const T& value,
       const Allocator& = Allocator());

-5- Effects: Constructs a vector with n copies of value, using the specified allocator.

-6- Requires: T must be CopyConstructible.

-7- Complexity: Linear in n.

vector(const Allocator& = Allocator());
explicit vector(size_type n, const T& value = T(),
                const Allocator& = Allocator());
template <class InputIterator>
  vector(InputIterator first, InputIterator last,
         const Allocator& = Allocator());
vector(const vector<T,Allocator>& x);

-8- Effects: Constructs a vector equal to the the range [first, last), using the specified allocator. Each iterator in the range [first, last) is dereferenced exactly once.

-9- Requires: T must be CopyConstructible only if the dereferenced InputIterator returns an lvalue or const rvalue.

-10- Complexity: The constructor template <class InputIterator> vector(InputIterator first, InputIterator last) mMakes only N calls to the copy constructor of T (where N is the distance between first and last) and no reallocations if iterators first and last are of forward, bidirectional, or random access categories. It makes order N calls to the copy constructor of T and order logN reallocations if they are just input iterators.

template <class InputIterator>
  void assign(InputIterator first, InputIterator last);

-11- Effects:

  erase(begin(), end());
  insert(begin(), first, last);

Each iterator in the range [first, last) is dereferenced exactly once.

-12- Requires: T must be CopyConstructible and CopyAssignable only if the dereferenced InputIterator returns an lvalue or const rvalue.

void assign(size_type n, const T& t);

-13- Effects:

  erase(begin(), end());
  insert(begin(), n, t);

-14- Requires: T must be CopyConstructible and CopyAssignable.

23.2.4.2 - vector capacity

A nothrow requirement is placed on the move constructor of value_type when reserve is called. This is required if reserve is to offer the strong exception guarantee. Currently the standard does not require roll back semantics for reserve. However implementations do offer this guarantee (and it is added here) and implementations would be unable to comply in the presence of a throwing move constructor.

There is also a nothrow requirement for the value_type's move constructor added to resize (both overloads).

void reserve(size_type n);

-2- Requires: The value_type's move constructor (if it exists) must not throw an exception.

-3- Effects: A directive that informs a vector of a planned change in size, so that it can manage the storage allocation accordingly. After reserve(), capacity() is greater or equal to the argument of reserve if reallocation happens; and equal to the previous value of capacity() otherwise. Reallocation happens at this point if and only if the current capacity is less than the argument of reserve().

-4- Complexity: It does not change the size of the sequence and takes at most linear time in the size of the sequence.

-5- Throws: length_error if n > max_size().* If an exception is thrown, there are no effects.

[Footnote: reserve() uses Allocator::allocate() which may throw an appropriate exception. --- end foonote]

-6- Remarks: Reallocation invalidates all the references, pointers, and iterators referring to the elements in the sequence. It is guaranteed that no reallocation takes place during insertions that happen after a call to reserve() until the time when an insertion would make the size of the vector greater than the size specified in the most recent call to reserve().

void swap(vector<T, Allocator>&& x);

-7- Effects: Exchanges the contents and capacity() of *this with that of x.

-8- Complexity: Constant time.


void resize(size_type sz);

-9- Effects: If sz is less than size() then size() - sz elements are erased from the end of the sequence. Else sz - size() default constructed elements are appended to the sequence.

-10- Requires: T must be default constructible. The value_type's move constructor (if it exists) must not throw an exception.

void resize(size_type sz, T c = T());

-11- Effects:

  if (sz > size())
    insert(end(), sz-size(), c);
  else if (sz < size())
    erase(begin()+sz, end());
  else
    ;                           //   do nothing

-12- Requires: T must be CopyConstructible. The value_type's move constructor (if it exists) must not throw an exception.

23.2.4.3 - vector modifiers

In order to comply with the current exception safety guarantees, the value_type's move constructor must not throw an exception during push_back or insert.


void push_back(const T& x);
void push_back(T&& x);

-1- Effects: Appends a copy of x to the end of the sequence.

-2- Requires: The signature with a const T& parameter requires T to be CopyConstructible. The value_type's move constructor (if it exists) must not throw an exception.

iterator insert(iterator position, const T& x);
iterator insert(iterator position, T&& x);
void     insert(iterator position, size_type n, const T& x);
template <class InputIterator>
  void insert(iterator position, InputIterator first, InputIterator last);

-3- Remarks: Causes reallocation if the new size is greater than the old capacity. If no reallocation happens, all the iterators and references before the insertion point remain valid. If an exception is thrown other than by the copy constructor or assignment operator of T there are no effects. Each iterator in the range [first, last) is dereferenced exactly once.

-4- Requires: The signatures taking a const T& parameter require T to be CopyConstructible and CopyAssignable. The signature taking InputIterator parameters requires T to be CopyConstructible and CopyAssignable only if the dereferenced InputIterator returns an lvalue or const rvalue. The value_type's move constructor (if it exists) must not throw an exception.

-5- Complexity: If first and last are forward iterators, bidirectional iterators, or random access iterators, the complexity is linear in the number of elements in the range [first, last) plus the distance to the end of the vector. If they are input iterators, the complexity is proportional to the number of elements in the range [first, last) times the distance to the end of the vector.

iterator erase(iterator position);
iterator erase(iterator first, iterator last);

-6- Effects: Invalidates all the iterators and references after the point of the erase.

-7- Complexity: The destructor of T is called the number of times equal to the number of the elements erased, but the move assignment operator of T is called the number of times equal to the number of elements in the vector after the erased elements.

-8- Throws: Nothing unless an exception is thrown by the copy constructor or assignment operator of T.

23.2.4.4 - vector specialized algorithms

template <class T, class Allocator>
  void swap(vector<T,Allocator>& x, vector<T,Allocator>& y);
template <class T, class Allocator>
  void swap(vector<T,Allocator>&& x, vector<T,Allocator>& y);
template <class T, class Allocator>
  void swap(vector<T,Allocator>& x, vector<T,Allocator>&& y);

-1- Effects:

  x.swap(y);

23.2.5 - Class template vector<bool>

The changes required for vector<bool> are minimal because vector<bool>::value_type copies with the same efficiency as it moves!

-1- To optimize space allocation, a specialization of vector for bool elements is provided:

namespace std {
  template <class Allocator> class vector<bool, Allocator> {
  public:
    //  types:
    typedef bool                                  const_reference;
    typedef implementation defined                iterator;       //  See lib.container.requirements
    typedef implementation defined                const_iterator; //  See lib.container.requirements
    typedef implementation defined                size_type;      //  See lib.container.requirements
    typedef implementation defined                difference_type;//  See lib.container.requirements
    typedef bool                                  value_type;
    typedef Allocator                             allocator_type;
    typedef implementation defined                pointer;
    typedef implementation defined                const_pointer
    typedef std::reverse_iterator<iterator>       reverse_iterator;
    typedef std::reverse_iterator<const_iterator> const_reverse_iterator;

    //  bit reference:
    class reference {
     friend class vector;
     reference();
    public:
     ~reference();
      operator bool() const;
      reference& operator=(const bool x);
      reference& operator=(const reference& x);
      void flip();              //  flips the bit
    };

    //  construct/copy/destroy:
    explicit vector(const Allocator& = Allocator());
    explicit vector(size_type n, const bool& value = bool(),
                    const Allocator& = Allocator());
    template <class InputIterator>
      vector(InputIterator first, InputIterator last,
        const Allocator& = Allocator());
    vector(const vector<bool,Allocator>& x);
    vector(vector&& x);
   ~vector();
    vector<bool,Allocator>& operator=(const vector<bool,Allocator>& x);
    vector& operator=(vector&& x);
    template <class InputIterator>
      void assign(InputIterator first, InputIterator last);
    void assign(size_type n, const T& t);
    allocator_type get_allocator() const;

    //  iterators:
    iterator               begin();
    const_iterator         begin() const;
    iterator               end();
    const_iterator         end() const;
    reverse_iterator       rbegin();
    const_reverse_iterator rbegin() const;
    reverse_iterator       rend();
    const_reverse_iterator rend() const;

    //  capacity:
    size_type size() const;
    size_type max_size() const;
    void      resize(size_type sz, bool c = false);
    size_type capacity() const;
    bool      empty() const;
    void      reserve(size_type n);

    //  element access:
    reference       operator[](size_type n);
    const_reference operator[](size_type n) const;
    const_reference at(size_type n) const;
    reference       at(size_type n);
    reference       front();
    const_reference front() const;
    reference       back();
    const_reference back() const;

    //  modifiers:
    void push_back(const bool& x);
    void pop_back();
    iterator insert(iterator position, const bool& x);
    void     insert (iterator position, size_type n, const bool& x);
    template <class InputIterator>
        void insert(iterator position,
                    InputIterator first, InputIterator last);

    iterator erase(iterator position);
    iterator erase(iterator first, iterator last);
    void swap(vector<bool,Allocator>&&);
    static void swap(reference x, reference y);
    void flip();                //  flips all bits
    void clear();
  };

  //  specialized algorithms:
  template <class Allocator>
    void swap(vector<bool,Allocator>& x, vector<bool,Allocator>& y);
}

-2- reference is a class that simulates the behavior of references of a single bit in vector<bool>.

23.3 - Associative containers

-1- Headers <map> and <set>:

Header <map> synopsis

namespace std {
  template <class Key, class T, class Compare = less<Key>,
            class Allocator = allocator<pair<const Key, T> > >
    class map;
  template <class Key, class T, class Compare, class Allocator>
    bool operator==(const map<Key,T,Compare,Allocator>& x,
                    const map<Key,T,Compare,Allocator>& y);
  template <class Key, class T, class Compare, class Allocator>
    bool operator< (const map<Key,T,Compare,Allocator>& x,
                    const map<Key,T,Compare,Allocator>& y);
  template <class Key, class T, class Compare, class Allocator>
    bool operator!=(const map<Key,T,Compare,Allocator>& x,
                    const map<Key,T,Compare,Allocator>& y);
  template <class Key, class T, class Compare, class Allocator>
    bool operator> (const map<Key,T,Compare,Allocator>& x,
                    const map<Key,T,Compare,Allocator>& y);
  template <class Key, class T, class Compare, class Allocator>
    bool operator>=(const map<Key,T,Compare,Allocator>& x,
                    const map<Key,T,Compare,Allocator>& y);
  template <class Key, class T, class Compare, class Allocator>
    bool operator<=(const map<Key,T,Compare,Allocator>& x,
                    const map<Key,T,Compare,Allocator>& y);
  template <class Key, class T, class Compare, class Allocator>
    void swap(map<Key,T,Compare,Allocator>& x,
              map<Key,T,Compare,Allocator>& y);
  template <class Key, class T, class Compare, class Allocator>
    void swap(map<Key,T,Compare,Allocator>&& x,
              map<Key,T,Compare,Allocator>& y);
  template <class Key, class T, class Compare, class Allocator>
    void swap(map<Key,T,Compare,Allocator>& x,
              map<Key,T,Compare,Allocator>&& y);

  template <class Key, class T, class Compare = less<Key>,
            class Allocator = allocator<pair<const Key, T> > >
    class multimap;
  template <class Key, class T, class Compare, class Allocator>
    bool operator==(const multimap<Key,T,Compare,Allocator>& x,
                    const multimap<Key,T,Compare,Allocator>& y);
  template <class Key, class T, class Compare, class Allocator>
    bool operator< (const multimap<Key,T,Compare,Allocator>& x,
                    const multimap<Key,T,Compare,Allocator>& y);
  template <class Key, class T, class Compare, class Allocator>
    bool operator!=(const multimap<Key,T,Compare,Allocator>& x,
                    const multimap<Key,T,Compare,Allocator>& y);
  template <class Key, class T, class Compare, class Allocator>
    bool operator> (const multimap<Key,T,Compare,Allocator>& x,
                    const multimap<Key,T,Compare,Allocator>& y);
  template <class Key, class T, class Compare, class Allocator>
    bool operator>=(const multimap<Key,T,Compare,Allocator>& x,
                    const multimap<Key,T,Compare,Allocator>& y);
  template <class Key, class T, class Compare, class Allocator>
    bool operator<=(const multimap<Key,T,Compare,Allocator>& x,
                    const multimap<Key,T,Compare,Allocator>& y);
  template <class Key, class T, class Compare, class Allocator>
    void swap(multimap<Key,T,Compare,Allocator>& x,
              multimap<Key,T,Compare,Allocator>& y);
  template <class Key, class T, class Compare, class Allocator>
    void swap(multimap<Key,T,Compare,Allocator>&& x,
              multimap<Key,T,Compare,Allocator>& y);
  template <class Key, class T, class Compare, class Allocator>
    void swap(multimap<Key,T,Compare,Allocator>& x,
              multimap<Key,T,Compare,Allocator>&& y);
}

Header <set> synopsis

namespace std {
  template <class Key, class Compare = less<Key>,
            class Allocator = allocator<Key> >
    class set;
  template <class Key, class Compare, class Allocator>
    bool operator==(const set<Key,Compare,Allocator>& x,
                    const set<Key,Compare,Allocator>& y);
  template <class Key, class Compare, class Allocator>
    bool operator< (const set<Key,Compare,Allocator>& x,
                    const set<Key,Compare,Allocator>& y);
  template <class Key, class Compare, class Allocator>
    bool operator!=(const set<Key,Compare,Allocator>& x,
                    const set<Key,Compare,Allocator>& y);
  template <class Key, class Compare, class Allocator>
    bool operator> (const set<Key,Compare,Allocator>& x,
                    const set<Key,Compare,Allocator>& y);
  template <class Key, class Compare, class Allocator>
    bool operator>=(const set<Key,Compare,Allocator>& x,
                    const set<Key,Compare,Allocator>& y);
  template <class Key, class Compare, class Allocator>
    bool operator<=(const set<Key,Compare,Allocator>& x,
                    const set<Key,Compare,Allocator>& y);
  template <class Key, class Compare, class Allocator>
    void swap(set<Key,Compare,Allocator>& x,
              set<Key,Compare,Allocator>& y);
  template <class Key, class Compare, class Allocator>
    void swap(set<Key,Compare,Allocator>&& x,
              set<Key,Compare,Allocator>& y);
  template <class Key, class Compare, class Allocator>
    void swap(set<Key,Compare,Allocator>& x,
              set<Key,Compare,Allocator>&& y);

  template <class Key, class Compare = less<Key>,
            class Allocator = allocator<Key> >
    class multiset;
  template <class Key, class Compare, class Allocator>
    bool operator==(const multiset<Key,Compare,Allocator>& x,
                    const multiset<Key,Compare,Allocator>& y);
  template <class Key, class Compare, class Allocator>
    bool operator< (const multiset<Key,Compare,Allocator>& x,
                    const multiset<Key,Compare,Allocator>& y);
  template <class Key, class Compare, class Allocator>
    bool operator!=(const multiset<Key,Compare,Allocator>& x,
                    const multiset<Key,Compare,Allocator>& y);
  template <class Key, class Compare, class Allocator>
    bool operator> (const multiset<Key,Compare,Allocator>& x,
                    const multiset<Key,Compare,Allocator>& y);
  template <class Key, class Compare, class Allocator>
    bool operator>=(const multiset<Key,Compare,Allocator>& x,
                    const multiset<Key,Compare,Allocator>& y);
  template <class Key, class Compare, class Allocator>
    bool operator<=(const multiset<Key,Compare,Allocator>& x,
                    const multiset<Key,Compare,Allocator>& y);
  template <class Key, class Compare, class Allocator>
    void swap(multiset<Key,Compare,Allocator>& x,
              multiset<Key,Compare,Allocator>& y);
  template <class Key, class Compare, class Allocator>
    void swap(multiset<Key,Compare,Allocator>&& x,
              multiset<Key,Compare,Allocator>& y);
  template <class Key, class Compare, class Allocator>
    void swap(multiset<Key,Compare,Allocator>& x,
              multiset<Key,Compare,Allocator>&& y);
}

23.3.1 - Class template map

Most of the rationale for the changes to map is the same as for deque. Please refer to the deque rationale for details that are not map-specific.

-2- A map satisfies all of the requirements of a container and of a reversible container (lib.container.requirements) and of an associative container (lib.associative.reqmts). A map also provides most operations described in (lib.associative.reqmts) for unique keys. This means that a map supports the a_uniq operations in (lib.associative.reqmts) but not the a_eq operations. For a map<Key,T> the key_type is Key and the value_type is pair<const Key,T>. Descriptions are provided here only for operations on map that are not described in one of those tables or for operations where there is additional semantic information.

namespace std {
  template <class Key, class T, class Compare = less<Key>,
            class Allocator = allocator<pair<const Key, T> > >
  class map {
  public:
    //  types:
    typedef Key                                   key_type;
    typedef T                                     mapped_type;
    typedef pair<const Key, T>                    value_type;
    typedef Compare                               key_compare;
    typedef Allocator                             allocator_type;
    typedef typename Allocator::reference         reference;
    typedef typename Allocator::const_reference   const_reference;
    typedef implementation defined                iterator;       //  See lib.container.requirements
    typedef implementation defined                const_iterator; //  See lib.container.requirements
    typedef implementation defined                size_type;      //  See lib.container.requirements
    typedef implementation defined                difference_type;//  See lib.container.requirements
    typedef typename Allocator::pointer           pointer;
    typedef typename Allocator::const_pointer     const_pointer;
    typedef std::reverse_iterator<iterator>       reverse_iterator;
    typedef std::reverse_iterator<const_iterator> const_reverse_iterator;

    class value_compare
      : public binary_function<value_type,value_type,bool> {
    friend class map;
    protected:
      Compare comp;
      value_compare(Compare c) : comp(c) {}
    public:
      bool operator()(const value_type& x, const value_type& y) const {
        return comp(x.first, y.first);
      }
    };

    //  lib.map.cons construct/copy/destroy:
    explicit map(const Compare& comp = Compare(),
                 const Allocator& = Allocator());
    template <class InputIterator>
      map(InputIterator first, InputIterator last,
          const Compare& comp = Compare(), const Allocator& = Allocator());
    map(const map<Key,T,Compare,Allocator>& x);
    map(map&& x);
   ~map();
    map<Key,T,Compare,Allocator>&
      operator=(const map<Key,T,Compare,Allocator>& x);
    map& operator=(map&& x);
    allocator_type get_allocator() const;

    //  iterators:
    iterator               begin();
    const_iterator         begin() const;
    iterator               end();
    const_iterator         end() const;
    reverse_iterator       rbegin();
    const_reverse_iterator rbegin() const;
    reverse_iterator       rend();
    const_reverse_iterator rend() const;

    //  capacity:
    bool      empty() const;
    size_type size() const;
    size_type max_size() const;

    //  lib.map.access element access:
    T& operator[](const key_type& x);
    T& operator[](key_type&& x);

    //  modifiers:
    pair<iterator, bool> insert(const value_type& x);
    template <class P> pair<iterator, bool> insert(P&& x);
    iterator             insert(iterator position, const value_type& x);
    template <class P> iterator insert(iterator position, P&& x);
    template <class InputIterator>
      void insert(InputIterator first, InputIterator last);

    void      erase(iterator position);
    size_type erase(const key_type& x);
    void      erase(iterator first, iterator last);
    void swap(map<Key,T,Compare,Allocator>&&);
    void clear();

    //  observers:
    key_compare   key_comp() const;
    value_compare value_comp() const;

    //  lib.map.ops map operations:
    iterator       find(const key_type& x);
    const_iterator find(const key_type& x) const;
    size_type      count(const key_type& x) const;

    iterator       lower_bound(const key_type& x);
    const_iterator lower_bound(const key_type& x) const;
    iterator       upper_bound(const key_type& x);
    const_iterator upper_bound(const key_type& x) const;

    pair<iterator,iterator>
        equal_range(const key_type& x);
    pair<const_iterator,const_iterator>
        equal_range(const key_type& x) const;
  };

  template <class Key, class T, class Compare, class Allocator>
    bool operator==(const map<Key,T,Compare,Allocator>& x,
                    const map<Key,T,Compare,Allocator>& y);
  template <class Key, class T, class Compare, class Allocator>
    bool operator< (const map<Key,T,Compare,Allocator>& x,
                    const map<Key,T,Compare,Allocator>& y);
  template <class Key, class T, class Compare, class Allocator>
    bool operator!=(const map<Key,T,Compare,Allocator>& x,
                    const map<Key,T,Compare,Allocator>& y);
  template <class Key, class T, class Compare, class Allocator>
    bool operator> (const map<Key,T,Compare,Allocator>& x,
                    const map<Key,T,Compare,Allocator>& y);
  template <class Key, class T, class Compare, class Allocator>
    bool operator>=(const map<Key,T,Compare,Allocator>& x,
                    const map<Key,T,Compare,Allocator>& y);
  template <class Key, class T, class Compare, class Allocator>
    bool operator<=(const map<Key,T,Compare,Allocator>& x,
                    const map<Key,T,Compare,Allocator>& y);

  //  specialized algorithms:
  template <class Key, class T, class Compare, class Allocator>
    void swap(map<Key,T,Compare,Allocator>& x,
              map<Key,T,Compare,Allocator>& y);
  template <class Key, class T, class Compare, class Allocator>
    void swap(map<Key,T,Compare,Allocator>&& x,
              map<Key,T,Compare,Allocator>& y);
  template <class Key, class T, class Compare, class Allocator>
    void swap(map<Key,T,Compare,Allocator>& x,
              map<Key,T,Compare,Allocator>&& y);
}

23.3.1.1 - map constructors, copy, and assignment

template <class InputIterator>
  map(InputIterator first, InputIterator last,
      const Compare& comp = Compare(), const Allocator& = Allocator());

-3- Requires: Does not require CopyConstructible of either key_type or mapped_type if the dereferenced InputIterator returns a non-const rvalue pair<key_type,mapped_type>. Otherwise CopyConstructible is required for both key_type and mapped_type.

-4- Effects: Constructs an empty map using the specified comparison object and allocator, and inserts elements from the range [first, last).

-5- Complexity: Linear in N if the range [first, last) is already sorted using comp and otherwise N log N, where N is last - first.

23.3.1.2 - map element access

A operator[] overload has been added that accepts rvalue key_types. This allows heavy and/or non-copyable key_types to be added to the map using operator[].

T& operator[](const key_type& x);

-1- Effects: If there is no key equivalent to x in the map, inserts value_type(x, T()) into the map.

-2- Requires: key_type must be CopyConstructible. mapped_type must be default constructible.

-3- Returns: A reference to the mapped_type corresponding to x in *this.

-4- Complexity: logarithmic.


T& operator[](key_type&& x);

-5- Requires: mapped_type must be default constructible.

-6- Effects: If there is no key equivalent to x in the map, inserts value_type(std::move(x), T()) into the map (without requiring x to be CopyConstructible).

-7- Returns: A reference to the mapped_type corresponding to x in *this.

-8- Complexity: logarithmic.

23.3.1.3 - map modifiers

Two of the insert signatures are new. They have been added to allow moving from rvalue types other than value_type, which are convertible to value_type. When P instantiates as an lvalue, the argument is copied into the map, else it is moved into the map (const qualifiers permitting).

pair<iterator, bool> insert(const value_type& x);
template <class P> pair<iterator, bool> insert(P&& x);
iterator             insert(iterator position, const value_type& x);
template <class P> iterator insert(iterator position, P&& x);
template <class InputIterator>
  void insert(InputIterator first, InputIterator last);

-1- Requires: Those signatures taking a const value_type& parameter requires both the key_type and the mapped_type to be CopyConstructible. The signatures taking a P&& parameter require P to be convertible to value_type. If P is instantiated as a reference type, then the argument x is copied from. Otherwise x is considered to be an rvalue as it is converted to value_type and inserted into the map. Specifically, in such cases CopyConstructible is not required of key_type or mapped_type unless the conversion from P specifically requires it (e.g. if P is a tuple<const key_type, mapped_type>, then key_type must be CopyConstructible). The signature taking InputIterator parameters does not require CopyConstructible of either key_type or mapped_type if the dereferenced InputIterator returns a non-const rvalue pair<key_type,mapped_type>. Otherwise CopyConstructible is required for both key_type and mapped_type.

23.3.1.34 - map operations

iterator       find(const key_type& x);
const_iterator find(const key_type& x) const;

iterator       lower_bound(const key_type& x);
const_iterator lower_bound(const key_type& x) const;

iterator       upper_bound(const key_type& x);
const_iterator upper_bound(const key_type &x) const;

pair<iterator, iterator>
  equal_range(const_key_type &x);
pair<const_iterator, const_iterator>
  equal_range(const key_type& x) const;

-1- The find, lower_bound, upper_bound and equal_range member functions each have two versions, one const and the other non-const. In each case the behavior of the two functions is identical except that the const version returns a const_iterator and the non-const version an iterator (lib.associative.reqmts).

23.3.1.45 - map specialized algorithms

template <class Key, class T, class Compare, class Allocator>
  void swap(map<Key,T,Compare,Allocator>& x,
            map<Key,T,Compare,Allocator>& y);
template <class Key, class T, class Compare, class Allocator>
  void swap(map<Key,T,Compare,Allocator>&& x,
            map<Key,T,Compare,Allocator>& y);
template <class Key, class T, class Compare, class Allocator>
  void swap(map<Key,T,Compare,Allocator>& x,
            map<Key,T,Compare,Allocator>&& y);

-1- Effects:

  x.swap(y);

23.3.2 - Class template multimap

See the map description for rationale.

-2- A multimap satisfies all of the requirements of a container and of a reversible container (lib.container.requirements) and of an associative container (lib.associative.reqmts). A multimap also provides most operations described in (lib.associative.reqmts) for equal keys. This means that a multimap supports the a_eq operations in (lib.associative.reqmts) but not the a_uniq operations. For a multimap<Key,T> the key_type is Key and the value_type is pair<const Key,T>. Descriptions are provided here only for operations on multimap that are not described in one of those tables or for operations where there is additional semantic information.

namespace std {
  template <class Key, class T, class Compare = less<Key>,
            class Allocator = allocator<pair<const Key, T> > >
  class multimap {
  public:
    //  types:
    typedef Key                                   key_type;
    typedef T                                     mapped_type;
    typedef pair<const Key,T>                     value_type;
    typedef Compare                               key_compare;
    typedef Allocator                             allocator_type;
    typedef typename Allocator::reference         reference;
    typedef typename Allocator::const_reference   const_reference;
    typedef implementation defined                iterator;       //  See lib.container.requirements
    typedef implementation defined                const_iterator; //  See lib.container.requirements
    typedef implementation defined                size_type;      //  See lib.container.requirements
    typedef implementation defined                difference_type;//  See lib.container.requirements
    typedef typename Allocator::pointer           pointer;
    typedef typename Allocator::const_pointer     const_pointer;
    typedef std::reverse_iterator<iterator>       reverse_iterator;
    typedef std::reverse_iterator<const_iterator> const_reverse_iterator;

    class value_compare
      : public binary_function<value_type,value_type,bool> {
    friend class multimap;
    protected:
      Compare comp;
      value_compare(Compare c) : comp(c) {}
    public:
      bool operator()(const value_type& x, const value_type& y) const {
        return comp(x.first, y.first);
      }
    };

    //  construct/copy/destroy:
    explicit multimap(const Compare& comp = Compare(),
                      const Allocator& = Allocator());
    template <class InputIterator>
      multimap(InputIterator first, InputIterator last,
               const Compare& comp = Compare(),
               const Allocator& = Allocator());
    multimap(const multimap<Key,T,Compare,Allocator>& x);
    multimap(multimap&& x);
   ~multimap();
    multimap<Key,T,Compare,Allocator>&
      operator=(const multimap<Key,T,Compare,Allocator>& x);
    multimap& operator=(multimap&& x);
    allocator_type get_allocator() const;

    //  iterators:
    iterator               begin();
    const_iterator         begin() const;
    iterator               end();
    const_iterator         end() const;
    reverse_iterator       rbegin();
    const_reverse_iterator rbegin() const;
    reverse_iterator       rend();
    const_reverse_iterator rend() const;

    //  capacity:
    bool           empty() const;
    size_type      size() const;
    size_type      max_size() const;

    //  modifiers:
    iterator insert(const value_type& x);
    template <class P> iterator insert(P&& x);
    iterator insert(iterator position, const value_type& x);
    template <class P> iterator insert(iterator position, P&& x);
    template <class InputIterator>
      void insert(InputIterator first, InputIterator last);

    void      erase(iterator position);
    size_type erase(const key_type& x);
    void      erase(iterator first, iterator last);
    void swap(multimap<Key,T,Compare,Allocator>&&);
    void clear();

    //  observers:
    key_compare    key_comp() const;
    value_compare  value_comp() const;

    //  map operations:
    iterator       find(const key_type& x);
    const_iterator find(const key_type& x) const;
    size_type      count(const key_type& x) const;

    iterator       lower_bound(const key_type& x);
    const_iterator lower_bound(const key_type& x) const;
    iterator       upper_bound(const key_type& x);
    const_iterator upper_bound(const key_type& x) const;

    pair<iterator,iterator>
      equal_range(const key_type& x);
    pair<const_iterator,const_iterator>
      equal_range(const key_type& x) const;
  };

  template <class Key, class T, class Compare, class Allocator>
    bool operator==(const multimap<Key,T,Compare,Allocator>& x,
                    const multimap<Key,T,Compare,Allocator>& y);
  template <class Key, class T, class Compare, class Allocator>
    bool operator< (const multimap<Key,T,Compare,Allocator>& x,
                    const multimap<Key,T,Compare,Allocator>& y);
  template <class Key, class T, class Compare, class Allocator>
    bool operator!=(const multimap<Key,T,Compare,Allocator>& x,
                    const multimap<Key,T,Compare,Allocator>& y);
  template <class Key, class T, class Compare, class Allocator>
    bool operator> (const multimap<Key,T,Compare,Allocator>& x,
                    const multimap<Key,T,Compare,Allocator>& y);
  template <class Key, class T, class Compare, class Allocator>
    bool operator>=(const multimap<Key,T,Compare,Allocator>& x,
                    const multimap<Key,T,Compare,Allocator>& y);
  template <class Key, class T, class Compare, class Allocator>
    bool operator<=(const multimap<Key,T,Compare,Allocator>& x,
                    const multimap<Key,T,Compare,Allocator>& y);

  //  specialized algorithms:
  template <class Key, class T, class Compare, class Allocator>
    void swap(multimap<Key,T,Compare,Allocator>& x,
              multimap<Key,T,Compare,Allocator>& y);
  template <class Key, class T, class Compare, class Allocator>
    void swap(multimap<Key,T,Compare,Allocator>&& x,
              multimap<Key,T,Compare,Allocator>& y);
  template <class Key, class T, class Compare, class Allocator>
    void swap(multimap<Key,T,Compare,Allocator>& x,
              multimap<Key,T,Compare,Allocator>&& y);
}

23.3.1.1 - multimap constructors, copy, and assignment

template <class InputIterator>
  multimap(InputIterator first, InputIterator last,
           const Compare& comp = Compare(),
           const Allocator& = Allocator()0;

-3- Requires: Does not require CopyConstructible of either key_type or mapped_type if the dereferenced InputIterator returns a non-const rvalue pair<key_type,mapped_type>. Otherwise CopyConstructible is required for both key_type and mapped_type.

-4- Effects: Constructs an empty multimap using the specified comparison object and allocator, and inserts elements from the range [first, last).

-5- Complexity: Linear in N if the range [first, last). is already sorted using comp and otherwise N log N, where N is last - first.

23.3.2.2 - multimap modifiers


iterator insert(const value_type& x);
template <class P> iterator insert(P&& x);
iterator insert(iterator position, const value_type& x);
template <class P> iterator insert(iterator position, P&& x);
template <class InputIterator>
  void insert(InputIterator first, InputIterator last);

-1- Requires: Those signatures taking a const value_type& parameter requires both the key_type and the mapped_type to be CopyConstructible. The signatures taking a P&& parameter require P to be convertible to value_type. If P is instantiated as a reference type, then the argument x is copied from. Otherwise x is considered to be an rvalue as it is converted to value_type and inserted into the map. Specifically, in such cases CopyConstructible is not required of key_type or mapped_type unless the conversion from P specifically requires it (e.g. if P is a tuple<const key_type, mapped_type>, then key_type must be CopyConstructible). The signature taking InputIterator parameters does not require CopyConstructible of either key_type or mapped_type if the dereferenced InputIterator returns a non-const rvalue pair<key_type,mapped_type>. Otherwise CopyConstructible is required for both key_type and mapped_type.

23.3.2.23 - multimap operations

iterator       find(const key_type &x);
const_iterator find(const key_type& x) const;

iterator       lower_bound(const key_type& x);
const_iterator lower_bound(const key_type& x) const;

pair<iterator, iterator>
  equal_range(const key_type& x);
pair<const_iterator, const_iterator>
  equal_range(const_key_type& x) const;

-1- The find, lower_bound, upper_bound, and equal_range member functions each have two versions, one const and one non-const. In each case the behavior of the two versions is identical except that the const version returns a const_iterator and the non-const version an iterator (lib.associative.reqmts).

23.3.2.34 - multimap specialized algorithms

template <class Key, class T, class Compare, class Allocator>
  void swap(multimap<Key,T,Compare,Allocator>& x,
            multimap<Key,T,Compare,Allocator>& y);
template <class Key, class T, class Compare, class Allocator>
  void swap(multimap<Key,T,Compare,Allocator>&& x,
            multimap<Key,T,Compare,Allocator>& y);
template <class Key, class T, class Compare, class Allocator>
  void swap(multimap<Key,T,Compare,Allocator>& x,
            multimap<Key,T,Compare,Allocator>&& y);

-1- Effects:

  x.swap(y);

23.3.3 - Class template set

See the map description for rationale.

-2- A set satisfies all of the requirements of a container and of a reversible container (lib.container.requirements), and of an associative container (lib.associative.reqmts). A set also provides most operations described in (lib.associative.reqmts) for unique keys. This means that a set supports the a_uniq operations in (lib.associative.reqmts) but not the a_eq operations. For a set<Key> both the key_type and value_type are Key. Descriptions are provided here only for operations on set that are not described in one of these tables and for operations where there is additional semantic information.

namespace std {
  template <class Key, class Compare = less<Key>,
            class Allocator = allocator<Key> >
  class set {
  public:
    //  types:
    typedef Key                                   key_type;
    typedef Key                                   value_type;
    typedef Compare                               key_compare;
    typedef Compare                               value_compare;
    typedef Allocator                             allocator_type;
    typedef typename Allocator::reference         reference;
    typedef typename Allocator::const_reference   const_reference;
    typedef implementation defined                iterator;       //  See lib.container.requirements
    typedef implementation defined                const_iterator; //  See lib.container.requirements
    typedef implementation defined                size_type;      //  See lib.container.requirements
    typedef implementation defined                difference_type;//  See lib.container.requirements
    typedef typename Allocator::pointer           pointer;
    typedef typename Allocator::const_pointer     const_pointer;
    typedef std::reverse_iterator<iterator>       reverse_iterator;
    typedef std::reverse_iterator<const_iterator> const_reverse_iterator;

    //  lib.set.cons construct/copy/destroy:
    explicit set(const Compare& comp = Compare(),
                 const Allocator& = Allocator());
    template <class InputIterator>
      set(InputIterator first, InputIterator last,
          const Compare& comp = Compare(), const Allocator& = Allocator());
    set(const set<Key,Compare,Allocator>& x);
    set(set&& x);
   ~set();
    set<Key,Compare,Allocator>& operator=
      (const set<Key,Compare,Allocator>& x);
    set& operator=(set&& x);
    allocator_type get_allocator() const;

    //  iterators:
    iterator               begin();
    const_iterator         begin() const;
    iterator               end();
    const_iterator         end() const;
    reverse_iterator       rbegin();
    const_reverse_iterator rbegin() const;
    reverse_iterator       rend();
    const_reverse_iterator rend() const;

    //  capacity:
    bool          empty() const;
    size_type     size() const;
    size_type     max_size() const;

    //  modifiers:
    pair<iterator,bool> insert(const value_type& x);
    pair<iterator,bool> insert(value_type&& x);
    iterator            insert(iterator position, const value_type& x);
    iterator            insert(iterator position, value_type&& x);
    template <class InputIterator>
        void insert(InputIterator first, InputIterator last);

    void      erase(iterator position);
    size_type erase(const key_type& x);
    void      erase(iterator first, iterator last);
    void swap(set<Key,Compare,Allocator>&&);
    void clear();

    //  observers:
    key_compare   key_comp() const;
    value_compare value_comp() const;

    //  set operations:
    iterator  find(const key_type& x) const;
    size_type count(const key_type& x) const;

    iterator  lower_bound(const key_type& x) const;
    iterator  upper_bound(const key_type& x) const;
    pair<iterator,iterator> equal_range(const key_type& x) const;
  };

  template <class Key, class Compare, class Allocator>
    bool operator==(const set<Key,Compare,Allocator>& x,
                    const set<Key,Compare,Allocator>& y);
  template <class Key, class Compare, class Allocator>
    bool operator< (const set<Key,Compare,Allocator>& x,
                    const set<Key,Compare,Allocator>& y);
  template <class Key, class Compare, class Allocator>
    bool operator!=(const set<Key,Compare,Allocator>& x,
                    const set<Key,Compare,Allocator>& y);
  template <class Key, class Compare, class Allocator>
    bool operator> (const set<Key,Compare,Allocator>& x,
                    const set<Key,Compare,Allocator>& y);
  template <class Key, class Compare, class Allocator>
    bool operator>=(const set<Key,Compare,Allocator>& x,
                    const set<Key,Compare,Allocator>& y);
  template <class Key, class Compare, class Allocator>
    bool operator<=(const set<Key,Compare,Allocator>& x,
                    const set<Key,Compare,Allocator>& y);

  //  specialized algorithms:
  template <class Key, class Compare, class Allocator>
    void swap(set<Key,Compare,Allocator>& x,
              set<Key,Compare,Allocator>& y);
  template <class Key, class Compare, class Allocator>
    void swap(set<Key,Compare,Allocator>&& x,
              set<Key,Compare,Allocator>& y);
  template <class Key, class Compare, class Allocator>
    void swap(set<Key,Compare,Allocator>& x,
              set<Key,Compare,Allocator>&& y);
}

23.3.3.1 - set constructors, copy, and assignment

explicit set(const Compare& comp = Compare(),
             const Allocator& = Allocator());

-1- Effects: Constructs an empty set using the specified comparison objects and allocator.

-2- Complexity: Constant.

template <class InputIterator>
  set(InputIterator first, InputIterator last,
      const Compare& comp = Compare(), const Allocator& = Allocator());

-3- Requires: Key must be CopyConstructible only if the dereferenced InputIterator returns an lvalue or const rvalue.

-4- Effects: Constructs an empty set using the specified comparison object and allocator, and inserts elements from the range [first, last).

-5- Complexity: Linear in N if the range [first, last) is already sorted using comp and otherwise N log N, where N is last - first>.

23.3.3.2 - set modifiers


pair<iterator,bool> insert(const value_type& x);
pair<iterator,bool> insert(value_type&& x);
iterator            insert(iterator position, const value_type& x);
iterator            insert(iterator position, value_type&& x);
template <class InputIterator>
    void insert(InputIterator first, InputIterator last);

-1- Requires: Those signatures taking const value_type& parameters require Key to be CopyConstructible. The signature taking InputIterator parameters requires Key to be CopyConstructible only if the dereferenced InputIterator returns an lvalue or const rvalue.

23.3.3.23 - set specialized algorithms

template <class Key, class Compare, class Allocator>
  void swap(set<Key,Compare,Allocator>& x,
            set<Key,Compare,Allocator>& y);
template <class Key, class Compare, class Allocator>
  void swap(set<Key,Compare,Allocator>&& x,
            set<Key,Compare,Allocator>& y);
template <class Key, class Compare, class Allocator>
  void swap(set<Key,Compare,Allocator>& x,
            set<Key,Compare,Allocator>&& y);

-1- Effects:

  x.swap(y);

23.3.4 - Class template multiset

See the map description for rationale.

-2- A multiset satisfies all of the requirements of a container and of a reversible container (lib.container.requirements), and of an associative container (lib.associative.reqmts). multiset also provides most operations described in (lib.associative.reqmts) for duplicate keys. This means that a multiset supports the a_eq operations in (lib.associative.reqmts) but not the a_uniq operations. For a multiset<Key> both the key_type and value_type are Key. Descriptions are provided here only for operations on multiset that are not described in one of these tables and for operations where there is additional semantic information.

namespace std {
  template <class Key, class Compare = less<Key>,
            class Allocator = allocator<Key> >
  class multiset {
  public:
    //  types:
    typedef Key                                   key_type;
    typedef Key                                   value_type;
    typedef Compare                               key_compare;
    typedef Compare                               value_compare;
    typedef Allocator                             allocator_type;
    typedef typename Allocator::reference         reference;
    typedef typename Allocator::const_reference   const_reference;
    typedef implementation defined                iterator;       //  See lib.container.requirements
    typedef implementation defined                const_iterator; //  See lib.container.requirements
    typedef implementation defined                size_type;      //  See lib.container.requirements
    typedef implementation defined                difference_type;//  See lib.container.requirements
    typedef typename Allocator::pointer           pointer;
    typedef typename Allocator::const_pointer     const_pointer;
    typedef std::reverse_iterator<iterator>       reverse_iterator;
    typedef std::reverse_iterator<const_iterator> const_reverse_iterator;

    //  construct/copy/destroy:
    explicit multiset(const Compare& comp = Compare(),
                      const Allocator& = Allocator());
    template <class InputIterator>
      multiset(InputIterator first, InputIterator last,
               const Compare& comp = Compare(),
               const Allocator& = Allocator());
    multiset(const multiset<Key,Compare,Allocator>& x);
    multiset(multiset&& x);
   ~multiset();
    multiset<Key,Compare,Allocator>&
        operator=(const multiset<Key,Compare,Allocator>& x);
    multiset& operator=(multiset&& x);
    allocator_type get_allocator() const;

    //  iterators:
    iterator               begin();
    const_iterator         begin() const;
    iterator               end();
    const_iterator         end() const;
    reverse_iterator       rbegin();
    const_reverse_iterator rbegin() const;
    reverse_iterator       rend();
    const_reverse_iterator rend() const;

    //  capacity:
    bool          empty() const;
    size_type     size() const;
    size_type     max_size() const;

    //  modifiers:
    iterator insert(const value_type& x);
    iterator insert(value_type&& x);
    iterator insert(iterator position, const value_type& x);
    iterator insert(iterator position, value_type&& x);
    template <class InputIterator>
      void insert(InputIterator first, InputIterator last);

    void      erase(iterator position);
    size_type erase(const key_type& x);
    void      erase(iterator first, iterator last);
    void swap(multiset<Key,Compare,Allocator>&&);
    void clear();

    //  observers:
    key_compare   key_comp() const;
    value_compare value_comp() const;

    //  set operations:
    iterator  find(const key_type& x) const;
    size_type count(const key_type& x) const;

    iterator  lower_bound(const key_type& x) const;
    iterator  upper_bound(const key_type& x) const;
    pair<iterator,iterator> equal_range(const key_type& x) const;
  };

  template <class Key, class Compare, class Allocator>
    bool operator==(const multiset<Key,Compare,Allocator>& x,
                    const multiset<Key,Compare,Allocator>& y);
  template <class Key, class Compare, class Allocator>
    bool operator< (const multiset<Key,Compare,Allocator>& x,
                    const multiset<Key,Compare,Allocator>& y);
  template <class Key, class Compare, class Allocator>
    bool operator!=(const multiset<Key,Compare,Allocator>& x,
                    const multiset<Key,Compare,Allocator>& y);
  template <class Key, class Compare, class Allocator>
    bool operator> (const multiset<Key,Compare,Allocator>& x,
                    const multiset<Key,Compare,Allocator>& y);
  template <class Key, class Compare, class Allocator>
    bool operator>=(const multiset<Key,Compare,Allocator>& x,
                    const multiset<Key,Compare,Allocator>& y);
  template <class Key, class Compare, class Allocator>
    bool operator<=(const multiset<Key,Compare,Allocator>& x,
                    const multiset<Key,Compare,Allocator>& y);

  //  specialized algorithms:
  template <class Key, class Compare, class Allocator>
    void swap(multiset<Key,Compare,Allocator>& x,
              multiset<Key,Compare,Allocator>& y);
  template <class Key, class Compare, class Allocator>
    void swap(multiset<Key,Compare,Allocator>&& x,
              multiset<Key,Compare,Allocator>& y);
  template <class Key, class Compare, class Allocator>
    void swap(multiset<Key,Compare,Allocator>& x,
              multiset<Key,Compare,Allocator>&& y);
}

23.3.4.1 - multiset constructors, copy, and assignment

explicit multiset(const Compare& comp = Compare(),
                  const Allocator& = Allocator());

-1- Effects: Constructs an empty set using the specified comparison object and allocator.

-2- Complexity: Constant.

template <class InputIterator>
  multiset(InputIterator first, last,
           const Compare& comp = Compare(), const Allocator& = Allocator());

-3- Requires: Key must be CopyConstructible only if the dereferenced InputIterator returns an lvalue or const rvalue.

-4- Effects: Constructs an empty multiset using the specified comparison object and allocator, and inserts elements from the range [first, last).

-5- Complexity: Linear in N if the range [first, last) is already sorted using comp and otherwise N log N, where N is last - first.

23.3.4.2 - multiset modifiers


iterator insert(const value_type& x);
iterator insert(value_type&& x);
iterator insert(iterator position, const value_type& x);
iterator insert(iterator position, value_type&& x);
template <class InputIterator>
  void insert(InputIterator first, InputIterator last);

-1- Requires: Those signatures taking const value_type& parameters require Key to be CopyConstructible. The signature taking InputIterator parameters requires Key to be CopyConstructible only if the dereferenced InputIterator returns an lvalue or const rvalue.

23.3.4.23 - multiset specialized algorithms

template <class Key, class Compare, class Allocator>
  void swap(multiset<Key,Compare,Allocator>& x,
            multiset<Key,Compare,Allocator>& y);
template <class Key, class Compare, class Allocator>
  void swap(multiset<Key,Compare,Allocator>&& x,
            multiset<Key,Compare,Allocator>& y);
template <class Key, class Compare, class Allocator>
  void swap(multiset<Key,Compare,Allocator>& x,
            multiset<Key,Compare,Allocator>&& y);

-1- Effects:

  x.swap(y);