Document number: N1771=05-0031

David Abrahams
Peter Dimov
Doug Gregor
Howard E. Hinnant
Andreas Hommel
Alisdair Meredith
2005-03-03

Impact of the rvalue reference on the Standard Library

Introduction

The purpose of this document is to survey and recommend changes to the standard library (and anticipated library components) assuming that the rvalue reference proposal documented by N1377, N1690 and N1770 becomes part of the C++ language.

The remainder of this paper sweeps through the library chapters, and through TR1, noting anticipated changes. The paper does not provide proposed wording, though some of the wording found below may approach proposed wording.

20.1 - Requirements

20.1.3 - Copy construction (and assignment)

It is anticipated that new requirements MoveConstructible and MoveAssignable will be introduced, and contrasted with the current CopyConstructible and Assignable requirements. The Swappable requirement is also introduced, brought in from the proposed resolution of LWG issue 226 (N1523).

In the following Tables, T is a type to be supplied by a C++ program, t and t1 are lvalues of type T, rv is an rvalue of type T, and u is a value (lvalue or rvalue) of type const T.

MoveConstructible requirements
expression post-condition
T(rv) T(rv) is equivalent to the value of rv before the construction

CopyConstructible requirements
expression post-condition
T(rv) T(rv) is equivalent to the value of rv before the construction
T(t) T(t) is equivalent to t, the value of t is not altered
T(u) T(u) is equivalent to u, the value of u is not altered

[Footnote: Note that a type that satisfies the CopyConstructible requirements also satisfies the MoveConstructible requirements.]

MoveAssignable requirements
expression return type return value post-condition
t = rv T& t t is equivalent to the value of rv before the assignment

CopyAssignable requirements
expression return type return value post-condition
t = rv T& t t is equivalent to the value of rv before the assignment
t = t1 T& t t is equivalent to t1, the value of t1 is not altered
t = u T& t t is equivalent to u, the value of u is not altered

[Footnote: Note that a type that satisfies the CopyAssignable requirements also satisfies the MoveAssignable requirements.]

Swappable requirements
expression post-condition
swap(t, u) t has the value originally held by u, and u has the value originally held by t

The swappable requirement is met by satisfying one or more of the following conditions:

[Footnote: Note that a type that satisfies the CopyConstructible and CopyAssignable requirements also satisfies the Swappable requirements.]

20.1.5 - Allocator requirements

Add rows to the Descriptive variable definitions:

V A type convertible to T
v A value of type V

Add row to the requirements table:

a.construct(p,v) (not used) Effect: ::new((void*)p) T(std::forward<V>(v))

The new construct overload is typically implemented as a member template function. It obsoletes the current non-member template construct member, but the current construct member is retained for binary backwards compatibility. The new overload allows containers to move construct rvalues from single element insert functions. It also allows convertible types V to be used to construct types T. This is necessary (for example) in map which must move construct a pair<const key, value> from an rvalue pair<key, value>, because it is not possible to move from a pair<const key, value>.

Allocators that are not move-aware, and don't meet this requirement will continue to work in move-aware containers of types meeting the CopyConstructible requirement. But they will fail at compile time for move-aware containers of types only meeting the MoveConstructible requirement. That is, if you want to put moveable but non-copyable types into a move-aware container, the container's allocator must have this construct overload.

20.2 - Utility components

synopsis

Add:

template <class T> struct identity {typedef T type;};
template <class T> T&& inline forward(typename identity<T>::type&& t)      {return t;}
template <class T> typename remove_reference<T>::type&& inline move(T&& t) {return t;}

These simply return their argument, and are used as helper functions in both library and client code.

The move function's main job is to cast an lvalue to an rvalue. move will always return an rvalue reference. In contrast, forward will not always return an rvalue reference, and the client must specify the template argument. forward will return an lvalue reference if the specified template argument is an lvalue reference, otherwise it will return an rvalue. This behavior works in concert with the template deduction rules for rvalue references to assure perfect forwarding.

Transition note for library vendors:

To support compilers which have not yet implemented the rvalue reference, vendors can instead implement these as:

template <class T> struct identity {typedef T type;};
template <class T>
    T& inline forward(typename identity<T>::type& t) {return t;}
template <class T>
    T& inline move(T& t) {return t;}
template <class T>
    const T& inline move(const T& t) {return t;}

The functions won't move or forward when written this way, but their existence will make it easier to write higher level code which uses move and forward. When ported to a compiler implementing the rvalue reference, only the move and forward need be changed. The (properly written) higher level library code will work in either environment, but use copy semantics (for example) in older compilers and use move semantics with the newer compiler. See example algorithm insertion_sort.

20.2.2 - Pairs

template <class T1, class T2>
struct pair
{
    typedef T1 first_type;
    typedef T2 second_type;

    T1 first;
    T2 second;
    pair();
    pair(const T1& x, const T2& y);
    template <class U, class V> pair(U&& x, V&& y);
    pair(pair&& p);
    template <class U, class V> pair(const pair<U, V> &p);
    template <class U, class V> pair(pair<U, V>&& p);
    pair& operator=(pair&& p);
    template <class U, class V> pair& operator=(pair<U, V>&& p);
};

The intent is for the move constructor and move assignment of pair to forward its arguments to T1 and T2's constructor and assignment as rvalues. Also note that movable but non-copyable types can now be put into pair (which in turn will make pair movable but non-copyable).

20.4.1 - The default allocator

Add:
   template <class U> void construct(pointer p, U&& val);

Effects: ::new((void*)p) T(std::forward<U>(val))

20.4.5 - Class template auto_ptr

Deprecate this section, but add unqiue_ptr:

struct apply_delete
{
    template <class T>
    void operator() (T* ptr) {typedef char incomplete[sizeof(T)]; delete ptr;}
};

struct apply_array_delete
{
    template <class T>
    void operator() (T* ptr) {typedef char incomplete[sizeof(T)]; delete [] ptr;}
};

template <class T, bool b = is_array<T>::value>
struct default_delete
{
    typedef apply_delete type;
};

template <class T>
struct default_delete<T, true>
{
    typedef apply_array_delete type;
};

template<class T, class D = typename default_delete<T>::type>
class unique_ptr
{
public:
    typedef T element_type;
    typedef D deleter_type;

    unique_ptr();

    explicit unique_ptr(T* p);

    unique_ptr(T* p, const deleter_type& d);
    unique_ptr(T* p, deleter_type&& d);

    unique_ptr(unique_ptr&& a);
    template <class U, class E>
        unique_ptr(unique_ptr<U, E>&& a);

    unique_ptr& operator=(unique_ptr&& a);

    template <class U, class E>
        unique_ptr& operator=(unique_ptr<U, E>&& a);

    ~unique_ptr();

    T& operator*() const;
    T* operator->() const;
    T* get() const;
    T* release();
    void reset(T* p = 0);
    void swap(unique_ptr&& a);
    deleter_type&       get_deleter();
    const deleter_type& get_deleter() const;

private: // express these in better standardeze
    struct bool_type {int dummy_;};
public:
    operator int bool_type::*() const;
    unique_ptr(int bool_type::*);
    unique_ptr& operator=(int bool_type::*);

private:
    // disable copy from lvalue
    unique_ptr(const unique_ptr& a);
        template <class U, class E> unique_ptr(const unique_ptr<U, E>& a);
    unique_ptr& operator=(const unique_ptr& a);
        template <class U, class E> unique_ptr& operator=(const unique_ptr<U, E>& a);
};

template<class T, class D>
class unique_ptr<T[], D>
{
public:
    typedef T element_type;
    typedef D deleter_type;

    unique_ptr();

    explicit unique_ptr(T*);
    unique_ptr(T* p, const deleter_type& d);
    unique_ptr(T* p, deleter_type&& d);

    unique_ptr(unique_ptr&& a);
    unique_ptr& operator=(unique_ptr&& a);

    ~unique_ptr();

    T& operator[](size_t i) const;
    T* get() const;
    T* release();
    void reset(T* p = 0);
    void swap(unique_ptr&& a);
    deleter_type&       get_deleter();
    const deleter_type& get_deleter() const;

private: // express these in better standardeze
    struct bool_type {int dummy_;};
public:
    operator int bool_type::*() const;
    unique_ptr(int bool_type::*);
    unique_ptr& operator=(int bool_type::*);

private:
    // disable copy from lvalue
    unique_ptr(const unique_ptr& a);
    unique_ptr& operator=(const unique_ptr& a);
};

unique_ptr really deserves (and will get) its own proposal. Nevertheless, it is included here for completeness. It is a very important library component with respect to the rvalue reference and move semantics.

unique_ptr is an auto_ptr replacement that is not fully backwards compatible. Thus the need to deprecate auto_ptr and introduce the new name (unique_ptr), instead of just fixing auto_ptr. The main similarities and differences between unique_ptr and auto_ptr include:

21 - Strings library

Summary: Make string move constructible and move assignable. Allow swap to work with rvalues. And allow string I/O to work with rvalue streams.

Add to string synopsis:

    basic_string(basic_string&& str);
    basic_string& operator=(basic_string&& str);
    basic_string& assign(basic_string&& str);
    void swap(basic_string&&& str);

And at namespace scope change/add:

template <class charT, class traits, class Allocator>
     void swap(basic_string<charT,traits,Allocator>&& lhs,
               basic_string<charT,traits,Allocator>& rhs);

template <class charT, class traits, class Allocator>
     void swap(basic_string<charT,traits,Allocator>& lhs,
               basic_string<charT,traits,Allocator>&& rhs);

template <class charT, class traits, class Allocator>
   basic_ostream<charT, traits>&
    operator>>(basic_ostream<charT, traits>&&& is,
               basic_string<charT,traits,Allocator>& str);
template <class charT, class traits, class Allocator>
  basic_ostream<charT, traits>&
    operator<<(basic_ostream<charT, traits>&&& os,
               const basic_string<charT,traits,Allocator>& str);
template <class charT, class traits, class Allocator>
   basic_istream<charT,traits>&
     getline(basic_istream<charT,traits>&&& is,
             basic_string<charT,traits,Allocator>& str,
             charT  delim);
template <class charT, class traits, class Allocator>
   basic_istream<charT,traits>&
     getline(basic_istream<charT,traits>&&& is,
             basic_string<charT,traits,Allocator>& str);

template <class charT, class traits, class Allocator>
    basic_string<charT,traits,Allocator>&&
      operator+(basic_string<charT,traits,Allocator>&& lhs,
                const basic_string<charT,traits,Allocator>& rhs);
template <class charT, class traits, class Allocator>
    basic_string<charT,traits,Allocator>&&
      operator+(const basic_string<charT,traits,Allocator>& lhs,
                basic_string<charT,traits,Allocator>&& rhs);
template <class charT, class traits, class Allocator>
    basic_string<charT,traits,Allocator>&&
      operator+(basic_string<charT,traits,Allocator>&& lhs,
                basic_string<charT,traits,Allocator>&& rhs);

23 - Containers library

Summary: Make all containers move constructible and move assignable. Furthermore allow a subset of their functionality to work with movable but non-copyable types (such as the proposed unique_ptr).

23.1 - Container requirements

-3- The type of objects stored in these components must meet the requirements of 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.

If the contained value_type alters the value of the source (even if the source is an rvalue) when constructing or assigning, then the operation must not throw an exception.

Delete 23.1p4 (assignable requirements). This is now covered in 20.1.

Add two rows to the table of Container requirements in 23.1p5:

X(rv)   Equal to the value of rv before construction constant
a = rv   a is equal to the value of rv before assignment constant

The following synopsis of the containers has comments indicating those members requiring stronger requirements than MoveConstructible and MoveAssignable. CC indicates CopyConstructible and CA indicates CopyAssignable. Those members not commented will work for types supporting only MoveConstructible and MoveAssignable. New and modified functions are indicated in bold.

Those members with a parameter of T&& x may assume that x is not a reference into the container.

23.2.1 - Class template deque

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;
    typedef implementation defined                const_iterator;
    typedef implementation defined                size_type;
    typedef implementation defined                difference_type;
    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);  // Does not require CC
    deque(size_type n, const T& value,
          const Allocator& = Allocator());  // CC
    template <class InputIterator>
      deque(InputIterator first, InputIterator last,
            const Allocator& = Allocator());  // CC only if InputIterator returns lvalue
    deque(const deque& x);  // CC
    deque(deque&& x);
   ~deque();
    deque& operator=(const deque& x);  // CC and CA
    deque& operator=(deque&& x);
    template <class InputIterator>
      void assign(InputIterator first,
                  InputIterator last);  // CC and CA only if InputIterator returns lvalue
    void assign(size_type n, const T& t);  // CC and CA
    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);  // Does not require CC
    void      resize(size_type sz, T c);  // CC
    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);  // CC
    void push_front(T&& x);
    void push_back(const T& x);  // CC
    void push_back(T&& x);

    iterator insert(iterator position, const T& x);  // CC and CA
    iterator insert(iterator position, T&& x);
    void     insert(iterator position, size_type n, const T& x);  // CC and CA
    template <class InputIterator>
      void insert (iterator position,
                   InputIterator first,
                   InputIterator last);  // CC and CA only if InputIterator returns lvalue

    void pop_front();
    void pop_back();

    iterator erase(iterator position);
    iterator erase(iterator first, iterator last);
    void     swap(deque&&);
    void     clear();
};


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.2 - Class template list

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;
    typedef implementation defined                const_iterator;
    typedef implementation defined                size_type;
    typedef implementation defined                difference_type;
    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);  // Does not require CC
    list(size_type n, const T& value,
         const Allocator& = Allocator());  // CC
    template <class InputIterator>
      list(InputIterator first, InputIterator last,
           const Allocator& = Allocator());  // CC only if InputIterator returns lvalue
    list(const list& x);  // CC
    list(list&& x);
   ~list();
    list& operator=(const list& x);  // CC and CA
    list& operator=(list&& x);
    template <class InputIterator>
      void assign(InputIterator first,
                  InputIterator last);  // CC and CA only if InputIterator returns lvalue

    void assign(size_type n, const T& t);  // CC and CA
    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);  // Does not require CC
    void      resize(size_type sz, T c);  // CC

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

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

    iterator insert(iterator position, const T& x);  // CC
    iterator insert(iterator position, T&& x);
    void     insert(iterator position, size_type n, const T& x);  // CC
    template <class InputIterator>
      void insert(iterator position, InputIterator first,
                  InputIterator last);  // CC only if InputIterator returns lvalue

    iterator erase(iterator position);
    iterator erase(iterator position, iterator last);
    void     swap(list&&);
    void     clear();

    //  lib.list.ops list operations:
    void splice(iterator position, list&& x);
    void splice(iterator position, list&& x, iterator i);
    void splice(iterator position, list&& 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&& x);
    template <class Compare> void merge(list&& x , Compare comp);

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

    void reverse();
};


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.3.1 - Class template queue

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&);    // CC
    explicit queue(Container&& = Container());

    queue(const queue&);  // CC
    queue(queue&&);
    queue& operator=(const queue&);    // CC and CA
    queue& operator=(queue&&);

    bool      empty() const;
    size_type size()  const;
    value_type&       front();
    const value_type& front() const;
    value_type&       back();
    const value_type& back() const;
    void push(const value_type& x);  // CC
    void push(value_type&& x);
    void pop();

    void swap(queue&&);
};


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

23.2.3.2 - Class template priority_queue

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

    priority_queue(const priority_queue&);  // CC
    priority_queue(priority_queue&&);
    priority_queue& operator=(const priority_queue&);  // CC and CA
    priority_queue& operator=(priority_queue&&);

    bool      empty() const;
    size_type size()  const;
    const value_type& top() const;
    void push(const value_type& x);  // CC
    void push(value_type&& x);
    void pop();
    void swap(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);

23.2.3.3 - Class template stack


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

    bool      empty() const;
    size_type size()  const;
    value_type&       top();
    const value_type& top() const;
    void push(const value_type& x);  // CC
    void push(value_type&& x);
    void pop();

    void swap(stack&&);
};


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

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;
    typedef implementation defined                const_iterator;
    typedef implementation defined                size_type;
    typedef implementation defined                difference_type;
    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);  // Does not require CC
    vector(size_type n, const T& value,
           const Allocator& = Allocator());  // CC
    template <class InputIterator>
      vector(InputIterator first, InputIterator last,
             const Allocator& = Allocator());  // CC only if InputIterator returns lvalue
    vector(const vector& x);  // CC
    vector(vector&& x);
   ~vector();
    vector& operator=(const vector& x);  // CC and CA
    vector& operator=(vector&& x);
    template <class InputIterator>
      void assign(InputIterator first,
                  InputIterator last);  // CC and CA only if InputIterator returns lvalue
    void assign(size_type n, const T& u);  // CC and CA
    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);  // Does not require CC
    void      resize(size_type sz, T c);  // CC
    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);  // CC
    void push_back(T&& x);
    void pop_back();
    iterator insert(iterator position, const T& x);  // CC and CA
    iterator insert(iterator position, T&& x);
    void     insert(iterator position, size_type n, const T& x);  // CC and CA
    template <class InputIterator>
        void insert(iterator position,
                    InputIterator first,
                    InputIterator last); // CC and CA only if InputIterator returns lvalue
    iterator erase(iterator position);
    iterator erase(iterator first, iterator last);
    void     swap(vector&&);
    void     clear();
};


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.5 - Class vector<bool>

template <class Allocator> class vector<bool, Allocator> {
  public:
    //  types:
    typedef bool                                  const_reference;
    typedef implementation defined                iterator;
    typedef implementation defined                const_iterator;
    typedef implementation defined                size_type;
    typedef implementation defined                difference_type;
    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());
    vector(size_type n, const bool& value, const Allocator& = Allocator());
    template <class InputIterator>
      vector(InputIterator first, InputIterator last,
             const Allocator& = Allocator());
    vector(const vector& x);
    vector(vector&& x);
   ~vector();
    vector& operator=(const vector& 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&&);
    static void swap(reference x, reference y);
    void flip();                //  flips all bits
    void clear();
};

23.3.1 - Class template map

Note below that for map and multimap that there are two new insert overloads, both taking a pair with a non-const key_type. One can not move from a const key_type, and therefore to be able to move a key_type into the (multi)map, a pair<key_type, mapped_type> must be used. There are overloads for both a const lvalue pair<key_type, mapped_type>, and a non-const rvalue pair<key_type, mapped_type> so that lvalue pair<key_type, mapped_type>'s will not be moved from.

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;
    typedef implementation defined                const_iterator;
    typedef implementation defined                size_type;
    typedef implementation defined                difference_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;

    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& a = Allocator());
    template <class InputIterator>
      map(InputIterator first, InputIterator last,
          const Compare& comp = Compare(),
          const Allocator& a = Allocator());  // CC only if InputIterator returns lvalue
    map(const map& x);  // CC
    map(map&& x);
   ~map();
    map& operator=(const map& x);  // CC
    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);  // CC for key_type only
    T& operator[](key_type&& x);

    //  modifiers:
    pair<iterator, bool> insert(const value_type& x);  // CC
    pair<iterator, bool> insert(const pair<key_type,mapped_type>& x);  // CC
    pair<iterator, bool> insert(pair<key_type,mapped_type>&& x);
    iterator insert(iterator position, const value_type& x);  // CC
    iterator insert(iterator position, const pair<key_type,mapped_type>& x);  // CC
    iterator insert(iterator position, pair<key_type,mapped_type>&& x);
    template <class InputIterator>
      void insert(InputIterator first,
                  InputIterator last);  // CC only if InputIterator returns lvalue

    void      erase(iterator position);
    size_type erase(const key_type& x);
    void      erase(iterator first, iterator last);
    void swap(map&&);
    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>
    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.2 - Class template multimap

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;
    typedef implementation defined                const_iterator;
    typedef implementation defined                size_type;
    typedef implementation defined                difference_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;

    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()); // CC only if InputIterator returns lvalue
    multimap(const multimap& x);  // CC
    multimap(multimap&& x);
   ~multimap();
    multimap& operator=(const multimap& x);  // CC
    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);  // CC
    iterator insert(const pair<key_type,mapped_type>& x);  // CC
    iterator insert(pair<key_type,mapped_type>&& x);
    iterator insert(iterator position, const value_type& x);  // CC
    iterator insert(iterator position, const pair<key_type,mapped_type>& x);  // CC
    iterator insert(iterator position, pair<key_type,mapped_type>&& x);
    template <class InputIterator>
      void insert(InputIterator first,
                  InputIterator last);  // CC only if InputIterator returns lvalue

    void      erase(iterator position);
    size_type erase(const key_type& x);
    void      erase(iterator first, iterator last);
    void swap(multimap&&);
    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>
    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.3 - Class template set

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;
    typedef implementation defined                const_iterator;
    typedef implementation defined                size_type;
    typedef implementation defined                difference_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.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());  // CC only if InputIterator returns lvalue
    set(const set& x);  // CC
    set(set&& x);
   ~set();
    set& operator= (const set& x);  // CC
    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);  // CC
    pair<iterator,bool> insert(value_type&& x);
    iterator            insert(iterator position, const value_type& x);  // CC
    iterator            insert(iterator position, value_type&& x);
    template <class InputIterator>
        void insert(InputIterator first,
                    InputIterator last);  // CC only if InputIterator returns lvalue

    void      erase(iterator position);
    size_type erase(const key_type& x);
    void      erase(iterator first, iterator last);
    void swap(set&&);
    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>
    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.4 - Class template multiset

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;
    typedef implementation defined                const_iterator;
    typedef implementation defined                size_type;
    typedef implementation defined                difference_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;

    //  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()); // CC only if InputIterator returns lvalue
    multiset(const multiset& x);  // CC
    multiset(multiset&& x);
   ~multiset();
    multiset& operator=(const multiset& x);  // CC
    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);  // CC
    iterator insert(value_type&& x);
    iterator insert(iterator position, const value_type& x);  // CC
    iterator insert(iterator position, value_type&& x);
    template <class InputIterator>
      void insert(InputIterator first,
                  InputIterator last);  // CC only if InputIterator returns lvalue

    void      erase(iterator position);
    size_type erase(const key_type& x);
    void      erase(iterator first, iterator last);
    void swap(multiset&&);
    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>
    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);

24 - Iterators library

A new iterator adaptor is needed which returns an rvalue reference instead of an lvalue reference on dereference. Ideally this iterator adaptor will be part of a more general iterator adaptor package. However for the purposes of this paper, the iterator adaptor can be considered a standalone adaptor like the existing standard iterator adaptors. The proposed adaptor also does not fit neatly into an existing iterator category. It is a read-once iterator, but can have up to random access traversal characteristics.

template <class Iterator>
class move_iterator
{
public:
    typedef Iterator                                              iterator_type;
    typedef typename iterator_traits<Iterator>::difference_type   difference_type;
    typedef typename iterator_traits<Iterator>::pointer           pointer;
    typedef typename iterator_traits<Iterator>::value_type        value_type;
    typedef typename iterator_traits<Iterator>::iterator_category iterator_category;
    typedef value_type&&                                          reference;

    move_iterator();
    explicit move_iterator(iterator_type i);
    template <class U> move_iterator(const move_iterator<U>& u);

    iterator_type base() const;
    reference operator*() const;
    pointer   operator->() const;

    move_iterator& operator++();
    move_iterator  operator++(int);
    move_iterator& operator--();
    move_iterator  operator--(int);

    move_iterator  operator+ (difference_type n) const;
    move_iterator& operator+=(difference_type n);
    move_iterator  operator- (difference_type n) const;
    move_iterator& operator-=(difference_type n);
    reference operator[](difference_type n) const;
};

template <class Iterator>
bool
operator==(const move_iterator<Iterator>& x, const move_iterator<Iterator>& y);

template <class Iterator>
bool
operator!=(const move_iterator<Iterator>& x, const move_iterator<Iterator>& y);

template <class Iterator>
bool
operator< (const move_iterator<Iterator>& x, const move_iterator<Iterator>& y);

template <class Iterator>
bool
operator<=(const move_iterator<Iterator>& x, const move_iterator<Iterator>& y);

template <class Iterator>
bool
operator> (const move_iterator<Iterator>& x, const move_iterator<Iterator>& y);

template <class Iterator>
bool
operator>=(const move_iterator<Iterator>& x, const move_iterator<Iterator>& y);

template <class Iterator>
typename move_iterator<Iterator>::difference_type
operator-(const move_iterator<Iterator>& x, const move_iterator<Iterator>& y);

template <class Iterator>
move_iterator<Iterator>
operator+(typename move_iterator<Iterator>::difference_type n,
          const move_iterator<Iterator>& x);

template <class Iterator>
move_iterator<Iterator>
make_move_iterator(const Iterator& i);

Given the above tool, "copying" algorithms can be turned into "moving" algorithms by adapting the iterators appropriately. For example:

vector<unique_ptr<int> > v1, v2;
...
remove_copy(make_move_iterator(v1.begin()), make_move_iterator(v1.end()),
            back_inserter(v2), unique_ptr<int>());

This call to remove_copy moves all non-null unique_ptr's from v1 to v2.

The following modifications to the existing iterator adaptors allows them to work with movable but non-copyable types that are presented to the assignment operator as an rvalue (as in the remove_copy example above).

24.4.2.1 - Class template back_insert_iterator

template <class Container>
class back_insert_iterator :
    public iterator<output_iterator_tag,void,void,void,void> {
protected:
    Container* container;

public:
    typedef Container container_type;
    explicit back_insert_iterator(Container& x);
    back_insert_iterator<Container>&
      operator=(typename Container::const_reference value);
    back_insert_iterator<Container>&
      operator=(typename Container::value_type&& value);

    back_insert_iterator<Container>& operator*();
    back_insert_iterator<Container>& operator++();
    back_insert_iterator<Container>  operator++(int);
};

24.4.2.3 - Class template front_insert_iterator

template <class Container>
class front_insert_iterator :
    public iterator<output_iterator_tag,void,void,void,void> {
protected:
    Container* container;

public:
    typedef Container container_type;
    explicit front_insert_iterator(Container& x);
    front_insert_iterator<Container>&
      operator=(typename Container::const_reference value);
    front_insert_iterator<Container>&
      operator=(typename Container::value_type&& value);

    front_insert_iterator<Container>& operator*();
    front_insert_iterator<Container>& operator++();
    front_insert_iterator<Container>  operator++(int);
};

24.4.2.5 - Class template insert_iterator

template <class Container>
class insert_iterator :
    public iterator<output_iterator_tag,void,void,void,void> {
protected:
    Container* container;
    typename Container::iterator iter;

public:
    typedef Container container_type;
    insert_iterator(Container& x, typename Container::iterator i);
    insert_iterator<Container>&
      operator=(typename Container::const_reference value);
    insert_iterator<Container>&
      operator=(typename Container::value_type&& value);

    insert_iterator<Container>& operator*();
    insert_iterator<Container>& operator++();
    insert_iterator<Container>& operator++(int);
};

25 - Algorithms library

There are two new algorithms, one with a slightly altered signature, and several with relaxed requirements (no longer requiring CopyConstructible or CopyAssignable) so that ranges of movable but non-copyable elemens (such as unique_ptr) can be operated on.

template <class InputIterator, class OutputIterator>
    OutputIterator move(InputIterator first, InputIterator last,
                        OutputIterator result);

template <class BidirectionalIterator1, class BidirectionalIterator2>
    BidirectionalIterator2
      move_backward(BidirectionalIterator1 first, BidirectionalIterator1 last,
                    BidirectionalIterator2 result);

move and move_backward are two new algorithms to augment copy and copy_backward. They require only that the value_type be MoveAssignable (recall that CopyAssignable types are MoveAssignable). Strictly speaking the functionality could be obtained with the combination of copy (or copy_backward) and move_iterator, however the anticipated frequency of use of these functions indicates that the syntactic convenience of these functions is warranted.

The table below summarizes the following five requirements for each algorithm in <algorithm>. Other requirements on the algorithms are ignored in this table.

The table below is a contract between clients and the implementation. The client must supply types that meet the minimum requirements. The type may also meet additional requirements. The implementation may assume that the supplied client type meets all of the requirements listed for an algorithm. But the implementation is not required to exercise all of the requirements. However the implementation is banned from using requirements not listed for the algorithm.

Those algorithms with the Swappable requirement may call swap unqualified, allowing for argument dependent lookup to find a swap in the client's namespace. Those algorithms without the Swappable requirement must not call swap unqualified. Furthermore, those algorithms without both MoveConstructible and MoveAssignable must not call swap qualified as the standard swap has these requirements.

Any algorithm may call any other algorithm qualified if the called algorithm's requirements are a subset of the calling algorithm's requirements (including std::swap).

No algorithm may call another algorithm unqualified unless such a call is part of a concept requirement of the algorithm (Swappable being the only example discussed).

Note that the requirements listed below allow many algorithms to operate on ranges of movable but non-copyable types such as unique_ptr. Furthermore, a few algorithms will operate on types supporting only the Swappable requirement (even if they are neither movable nor copyable).

The non-mutating algorithms have no requirements along these lines, but are listed below for completeness.

Summary of algorithm requirements
algorithm S MC MA CC CA Remarks
for_each            
find            
find_if            
find_end            
find_first_of            
adjacent_find            
count            
count_if            
mismatch            
equal            
search            
search_n            
copy         X  
copy_backward         X  
move     X     This is a new algorithm
move_backward     X     This is a new algorithm
swap   X X      
swap_ranges X          
iter_swap X          
transform     X   X If the operation returns an rvalue, only MA is required
replace         X  
replace_if         X  
replace_copy         X CA applies only to the output range

Summary of algorithm requirements (continued)
algorithm S MC MA CC CA Remarks
replace_copy_if         X CA applies only to the output range
fill         X  
fill_n         X  
generate     X   X If the generator returns an rvalue, only MA is required
generate_n     X   X If the generator returns an rvalue, only MA is required
remove     X      
remove_if     X      
remove_copy         X CA applies only to the output range
remove_copy_if         X CA applies only to the output range
unique     X      
unique_copy         X CA applies only to the output range
reverse X          
reverse_copy         X CA applies only to the output range
rotate X X X      
rotate_copy         X CA applies only to the output range
random_shuffle X          
partition X          
stable_partition X X X      
sort X X X      
stable_sort X X X      
partial_sort X X X      
partial_sort_copy X X     X Applies only to output range
nth_element X X X      

Summary of algorithm requirements (continued)
algorithm S MC MA CC CA Remarks
lower_bound            
upper_bound            
equal_range            
binary_search            
merge         X CA applies only to the output range
inplace_merge X X X      
includes            
set_union         X CA applies only to the output range
set_intersection         X CA applies only to the output range
set_difference         X CA applies only to the output range
set_symmetric_difference         X CA applies only to the output range
push_heap   X X      
pop_heap X X X      
make_heap   X X      
sort_heap X X X      
min            
max            
min_element            
max_element            
lexicographical_compare            
next_permutation X          
prev_permutation X          

[Example:

swap_ranges has only the Swappable requirement. It must call swap unqualified if it is to move any elements around. No other element moving call is allowed.

-- end example]

[Example:

rotate requires Swappable, MoveConstructible and MoveAssignable. It is allowed to call swap unqualified, swap qualified, or to not call swap at all, instead calling the element's move assignment and/or move constructor. rotate may not call the element's copy constructor or copy assignment.

-- end example]

[Example:

push_heap requires MoveConstructible and MoveAssignable (but not Swappable). It is allowed to call swap qualified, and allowed to move elements with a move constructor or move assignment. push_heap must not call swap unqualified, nor the element's copy constructor or copy assignment.

-- end example]

The signature of random_shuffle is changed to allow an rvalue random number generator:

template <class RandomAccessIterator>
  void random_shuffle(RandomAccessIterator first,
                      RandomAccessIterator last,
                      RandomNumberGenerator&&& rand);

Transition note for library vendors:

For exposition purposes, below is shown how an example algorithm might be modified to reduce its requirements from CopyConstructible and CopyAssignable to MoveConstructible and MoveAssignable. The algorithm today might look like:

template <class BidirectionalIterator>
void
insertion_sort(BidirectionalIterator first, BidirectionalIterator last)
{
    typedef typename iterator_traits<BidirectionalIterator>::value_type value_type;
    if (first != last)
    {
        BidirectionalIterator i = first;
        for (++i; i != last; ++i)
        {
            BidirectionalIterator j = i;
            value_type tmp(*j);
            for (BidirectionalIterator k = i; k != first && tmp < *--k; --j)
                *j = *k;
            *j = tmp;
        }
    }
}

Careful analysis of the above function reveals that the value of each value_type copied from is never used again. Therefore the only thing required to greatly accelerate the speed of this algorithm when used with heavy weight but movable value_type's is to replace the copy construction and copy assignment with their move counterparts:

template <class BidirectionalIterator>
void
insertion_sort(BidirectionalIterator first, BidirectionalIterator last)
{
    typedef typename iterator_traits<BidirectionalIterator>::value_type value_type;
    if (first != last)
    {
        BidirectionalIterator i = first;
        for (++i; i != last; ++i)
        {
            BidirectionalIterator j = i;
            value_type tmp(std::move(*j));
            for (BidirectionalIterator k = i; k != first && tmp < *--k; --j)
                *j = std::move(*k);
            *j = std::move(tmp);
        }
    }
}

When working with older compilers not yet implementing the rvalue reference, if the library supplies an interim move function, then the above insertion_sort will continue to work on these older compilers as it did before modification (requiring copy semantics instead of move semantics).

26 - Numerics library

26.3.2 - Class template valarray

Summary: Give valarray a move constructor and move assignment operator.

Add:

valarray(valarray&&);
valarray& operator=(valarray&&);

27 - Input/output library

Summary: Make streams move constructible, move assignable and swappable. Enable clients to work with rvalue streams for operator << and operator >>.

27.4.4 - Class template basic_ios

Add to basic_ios protected members:

void move(basic_ios&& rhs);
void swap(basic_ios&& rhs);
void set_rdbuf(basic_streambuf<charT, traits>* sb);

Derived clients can call move as an aid in move construction, similar to basic_ios::init. Similarly for swap. Neither move nor swap are allowed to change the result which rdbuf() returns. That is, this member remains unchanged through these calls. Derived clients must set this data via set_rdbuf. Like rdbuf, the new, protected set_rdbuf sets the streambuf associated with the stream, but it does not call clear() as the public rdbuf() does.

27.5.2 - Class template basic_streambuf<charT,traits>

Add to basic_streambuf protected members:

basic_streambuf(const basic_streambuf& rhs);
basic_streambuf& operator=(const basic_streambuf& rhs);
void swap(basic_streambuf&& rhs);

This affects LWG issue 421 which concerns whether or not basic_streambuf has copy semantics. It turns out that when writing move constructors and move assignment for clients derived from basic_streambuf that it is sometimes very handy to ask the base to move construct, move assign, or swap. These operations are possible to do in the derived client by calling pubimbue, setg, pbump, eback, etc. However, using this interface is extremely clumsy and inefficient for this purpose.

An alternative is to declare that basic_streambuf has private copy semantics, but protected move semantics. However the move semantics would have the same semantics as the copy, and so the extra complication hardly seems worth the effort.

27.6.1.1 - Class template basic_istream

Add to basic_istream members:

basic_istream(basic_istream&& rhs);
basic_istream& operator=(basic_istream&& rhs);
void swap(basic_istream&& rhs);

The move constructor does not call the move constructor of the base class. Instead it calls the base class's member move function with rhs as an argument. Additionally it sets the gcount of the rhs to zero.

Change/Add:

//  lib.istream::extractors character extraction templates:

template<class charT, class traits>
basic_istream<charT,traits>&
operator>>(basic_istream<charT,traits>&&&, charT&);

template<class traits>
basic_istream<char,traits>&
operator>>(basic_istream<char,traits>&&&, unsigned char&);

template<class traits>
basic_istream<char,traits>&
operator>>(basic_istream<char,traits>&&&, signed char&);

template<class charT, class traits>
basic_istream<charT,traits>&
operator>>(basic_istream<charT,traits>&&&, charT*);

template<class traits>
basic_istream<char,traits>&
operator>>(basic_istream<char,traits>&&&, unsigned char*);

template<class traits>
basic_istream<char,traits>&
operator>>(basic_istream<char,traits>&&&, signed char*);

template <class charT, class traits>
void swap(basic_istream<charT, traits>& x, basic_istream<charT, traits>& y);

template <class charT, class traits>
void swap(basic_istream<charT, traits>&& x, basic_istream<charT, traits>& y);

template <class charT, class traits>
void swap(basic_istream<charT, traits>& x, basic_istream<charT, traits>&& y);

Note: There is no backwards compatibility hit on any of these. They all currently do not compile when given rvalue streams.

27.6.1.5 - Class template basic_iostream

Add to basic_iostream members:

basic_iostream(basic_iostream&& rhs);
basic_iostream& operator=(basic_iostream&& rhs);
void swap(basic_iostream&& rhs);

All three of the above members will have to take care to only move from (or swap with) the rhs only once (in an implementation defined manner).

Add:

template <class charT, class traits>
void swap(basic_iostream<charT, traits>& x, basic_iostream<charT, traits>& y);

template <class charT, class traits>
void swap(basic_iostream<charT, traits>&& x, basic_iostream<charT, traits>& y);

template <class charT, class traits>
void swap(basic_iostream<charT, traits>& x, basic_iostream<charT, traits>&& y);

27.6.2.1 - Class template basic_ostream

Add to basic_ostream members:

basic_ostream(basic_ostream&& rhs);
basic_ostream& operator=(basic_ostream&& rhs);
void swap(basic_iostream&& rhs);

The move constructor does not call the move constructor of the base class. Instead it calls the base class's member move function with rhs as an argument.

Add:

//  lib.ostream.inserters.character character inserters
template<class charT, class traits>
basic_ostream<charT,traits>&
operator<<(basic_ostream<charT,traits>&&, charT);

template<class charT, class traits>
basic_ostream<charT,traits>&
operator<<(basic_ostream<charT,traits>&&, char);

//  specialization
template<class traits>
basic_ostream<char,traits>&
operator<<(basic_ostream<char,traits>&&, char);

//  signed and unsigned
template<class traits>
basic_ostream<char,traits>&
operator<<(basic_ostream<char,traits>&&, signed char);

template<class traits>
basic_ostream<char,traits>&
operator<<(basic_ostream<char,traits>&&, unsigned char);

template<class charT, class traits>
basic_ostream<charT,traits>&
operator<<(basic_ostream<charT,traits>&&, const charT*);

template<class charT, class traits>
basic_ostream<charT,traits>&
operator<<(basic_ostream<charT,traits>&&, const char*);

//  partial specializationss
template<class traits>
basic_ostream<char,traits>&
operator<<(basic_ostream<char,traits>&&, const char*);

//   signed and unsigned
template<class traits>
basic_ostream<char,traits>&
operator<<(basic_ostream<char,traits>&&, const signed char*);

template<class traits>
basic_ostream<char,traits>&
operator<<(basic_ostream<char,traits>&&, const unsigned char*);

template <class charT, class traits>
void swap(basic_ostream<charT, traits>& x, basic_ostream<charT, traits>& y);

template <class charT, class traits>
void swap(basic_ostream<charT, traits>&& x, basic_ostream<charT, traits>& y);

template <class charT, class traits>
void swap(basic_ostream<charT, traits>& x, basic_ostream<charT, traits>&& y);

Note: The above simply call their existing lvalue-stream counterparts. There is a small backwards compatibility hit on all of these. The ones taking a char type currently compile with rvalue streams and resolve to the member inserter taking an int. The signatures taking a const charT* currently compile with an rvalue stream and resolve to the member inserter taking a const void*.
[Example:

std::ofstream("log file") << 'A';

Today's output: 65 (on an ASCII system)

Proposed output: A

----
std::ofstream("log file") << "some text";

Today's output: 0x000ed1bc (implementation defined pointer)

Proposed output: some text

--end example]

In the author's opinion, this is really more of a bug fix, than a backwards compatibility hit.

27.7.1 - Class template basic_stringbuf

Add to basic_stringbuf members:

basic_stringbuf(basic_stringbuf&& rhs);
basic_stringbuf& operator=(basic_stringbuf&& rhs);
void swap(basic_stringbuf&& rhs);

Add:

template <class charT, class traits, class Allocator>
void
swap(basic_stringbuf<charT, traits, Allocator>& x,
     basic_stringbuf<charT, traits, Allocator>& y);

template <class charT, class traits, class Allocator>
void
swap(basic_stringbuf<charT, traits, Allocator>&& x,
     basic_stringbuf<charT, traits, Allocator>& y);

template <class charT, class traits, class Allocator>
void
swap(basic_stringbuf<charT, traits, Allocator>& x,
     basic_stringbuf<charT, traits, Allocator>&& y);

27.7.2 - Class template basic_istringstream

Add to basic_istringstream members:

basic_istringstream(basic_istringstream&& rhs);
basic_istringstream& operator=(basic_istringstream&& rhs);
void swap(basic_istringstream&& rhs);

After the move constructor moves from the base class and basic_stringbuf member it calls the base class's set_rdbuf member with the address of its basic_stringbuf.

Note that the member swap can simply swap the base and basic_stringbuf member. The base class's swap avoids changing the result of rdbuf() which is the correct behavior.

Add:

template <class charT, class traits, class Allocator>
void
swap(basic_istringstream<charT, traits, Allocator>& x,
     basic_istringstream<charT, traits, Allocator>& y);

template <class charT, class traits, class Allocator>
void
swap(basic_istringstream<charT, traits, Allocator>&& x,
     basic_istringstream<charT, traits, Allocator>& y);

template <class charT, class traits, class Allocator>
void
swap(basic_istringstream<charT, traits, Allocator>& x,
     basic_istringstream<charT, traits, Allocator>&& y);

27.7.3 - Class basic_ostringstream

Add to basic_ostringstream members:

basic_ostringstream(basic_ostringstream&& rhs);
basic_ostringstream& operator=(basic_ostringstream&& rhs);
void swap(basic_ostringstream&& rhs);

After the move constructor moves from the base class and basic_stringbuf member it calls the base class's set_rdbuf member with the address of its basic_stringbuf.

Add:

template <class charT, class traits, class Allocator>
void
swap(basic_ostringstream<charT, traits, Allocator>& x,
     basic_ostringstream<charT, traits, Allocator>& y);

template <class charT, class traits, class Allocator>
void
swap(basic_ostringstream<charT, traits, Allocator>&& x,
     basic_ostringstream<charT, traits, Allocator>& y);

template <class charT, class traits, class Allocator>
void
swap(basic_ostringstream<charT, traits, Allocator>& x,
     basic_ostringstream<charT, traits, Allocator>&& y);

27.7.4 - Class template basic_stringstream

Add to basic_stringstream members:

basic_stringstream(basic_stringstream&& rhs);
basic_stringstream& operator=(basic_stringstream&& rhs);
void swap(basic_stringstream&& rhs);

After the move constructor moves from the base class and basic_stringbuf member it calls the base class's set_rdbuf member with the address of its basic_stringbuf.

Add:

template <class charT, class traits, class Allocator>
void
swap(basic_stringstream<charT, traits, Allocator>& x,
     basic_stringstream<charT, traits, Allocator>& y);

template <class charT, class traits, class Allocator>
void
swap(basic_stringstream<charT, traits, Allocator>&& x,
     basic_stringstream<charT, traits, Allocator>& y);

template <class charT, class traits, class Allocator>
void
swap(basic_stringstream<charT, traits, Allocator>& x,
     basic_stringstream<charT, traits, Allocator>&& y);

27.8.1.1 - Class template basic_filebuf

Add to basic_filebuf members:

basic_filebuf(basic_filebuf&& rhs);
basic_filebuf& operator=(basic_filebuf&& rhs);
void swap(basic_filebuf&& rhs);

Add:

template <class charT, class traits>
void swap(basic_filebuf<charT, traits>& x, basic_filebuf<charT, traitsr>& y);

template <class charT, class traits>
void swap(basic_filebuf<charT, traits>&& x, basic_filebuf<charT, traits>& y);

template <class charT, class traits>
void swap(basic_filebuf<charT, traits>& x, basic_filebuf<charT, traits>&& y);

27.8.1.5 - Class template basic_ifstream

Add to basic_ifstream members:

basic_ifstream(basic_ifstream&& rhs);
basic_ifstream& operator=(basic_ifstream&& rhs);
void swap(basic_ifstream&& rhs);

After the move constructor moves from the base class and basic_filebuf member it calls the base class's set_rdbuf member with the address of its basic_filebuf .

Add:

template <class charT, class traits>
void swap(basic_ifstream<charT, traits>& x, basic_ifstream<charT, traitsr>& y);

template <class charT, class traits>
void swap(basic_ifstream<charT, traits>&& x, basic_ifstream<charT, traits>& y);

template <class charT, class traits>
void swap(basic_ifstream<charT, traits>& x, basic_ifstream<charT, traits>&& y);

27.8.1.8 - Class template basic_ofstream

Add to basic_ofstream members:

basic_ofstream(basic_ofstream&& rhs);
basic_ofstream& operator=(basic_ofstream&& rhs);
void swap(basic_ofstream&& rhs);

After the move constructor moves from the base class and basic_filebuf member it calls the base class's set_rdbuf member with the address of its basic_filebuf .

Add:

template <class charT, class traits>
void swap(basic_ofstream<charT, traits>& x, basic_ofstream<charT, traitsr>& y);

template <class charT, class traits>
void swap(basic_ofstream<charT, traits>&& x, basic_ofstream<charT, traits>& y);

template <class charT, class traits>
void swap(basic_ofstream<charT, traits>& x, basic_ofstream<charT, traits>&& y);

27.8.1.11 - Class template basic_fstream

Add to basic_fstream members:

basic_fstream(basic_fstream&& rhs);
basic_fstream& operator=(basic_fstream&& rhs);
void swap(basic_fstream&& rhs);

After the move constructor moves from the base class and basic_filebuf member it calls the base class's set_rdbuf member with the address of its basic_filebuf .

Add:

template <class charT, class traits>
void swap(basic_fstream<charT, traits>& x, basic_fstream<charT, traitsr>& y);

template <class charT, class traits>
void swap(basic_fstream<charT, traits>&& x, basic_fstream<charT, traits>& y);

template <class charT, class traits>
void swap(basic_fstream<charT, traits>& x, basic_fstream<charT, traits>&& y);

Technical Library Report 1 Impact

2.1.2 Class template reference_wrapper

template <class T>
class reference_wrapper
    : public unary_function <T1, R>       // see below
    : public binary_function <T1, T2, R>  // see below
{
public :
    // types
    typedef T type;
    typedef see below result_type; // Not always defined

    // construct/copy/destruct
    explicit reference_wrapper (T&);
    reference_wrapper(const reference_wrapper& x);

    // assignment
    reference_wrapper& operator =(const reference_wrapper& x);

    // access
    operator T & () const;
    T& get () const;

    // invocation
    template <class T1, class T2, ..., class TN>
    typename result_of <T(T1, T2, ..., TN)>::type
    operator() (T1&&&, T2&&&, ..., TN&&&) const;
};

reference_wrapper will use perfect forwarding.

2.2.3 Class template shared_ptr

Change:

template <class Y , class D> shared_ptr (Y* p , D&& d);

This eliminates the requirement that the copy constructor of D be nothrow.

Change 2.2.3.1p10:

Effects: Constructs a shared_ptr object that owns the pointer p and a copy of the the deleter d.

Add:

shared_ptr(shared_ptr&& r);
template <class Y> shared_ptr(shared_ptr<Y>&& r);

Add:

weak_ptr(weak_ptr&& r);

3.3 Requirements

Every call wrapper [3.1] shall be CopyConstructible. A simple call wrapper is a call wrapper that is Assignable and whose copy constructor and assignment operator do not throw exceptions. A forwarding call wrapper is a call wrapper that can be called with an argument list t1, t2, ..., tN where each ti is an lvalue. The effect of calling a forwarding call wrapper with one or more arguments that are rvalues is implementation defined. [Note: in a typical implementation forwarding call wrappers have overloaded function call operators of the form

template <class T1, class T2, ..., class TN>
R
operator ()(T1&&& t1 , T2&&& t2 , ... , TN&&& tN) cv-qual;

3.7.2 Class template function

Add:

function(function&&);
function& operator=(function&&);
template<typename F> function(F&&);
template<typename F> function& operator=(F&&);

4.2 Header <type_traits> synopsis

Remove add_reference. It is now ambiguous, unless renamed to add_lvalue_reference and add_rvalue_reference. Furthermore it is no longer required with CWG 106 implemented.

Add:

template <class T> struct remove_reference<T&&> {typedef T type;};

4.7 Transformations between types

is_convertible should test with an rvalue source instead of lvalue source, and include a U&& signature to test against.

6.1.3 Class template tuple

tuple constructors will need to be looked at in a new light. They will want to be able to move components into the tuple in addition to of copy them in as described for pair. Additionally make_tuple will want to take advantage of rvalues. And of course tuple will want a move constructor and move assignment which does member-wise moving.

6.2.2 Class template array

It would be good if array had a move constructor and move assignment (to do member-wise moving), but not at the expense of disabling the initializer syntax of array. So this will depend upon some other core extension which addresses initializer syntax for non-PODs.

6.3 Unordered associative containers

Needs changes analogous to those set forth for the standard ordered associative containers.

7 Regular expressions

Add move constructors and move assignment as appropriate.

Proposed Libraries

A Multi-threading Library for Standard C++

Pete Becker has proposed a multi-threading library based on the Dinkumware implementation, which is also based on the boost threading library. Metrowerks has also shipped a similar library. In all three cases, a scoped_lock is a non-copyable type which locks and unlocks mutex in a RAII pattern.

It is clear that such a scoped_lock should not be copied. However, movable scoped_locks could have significant utility. If movable, scoped_locks could be returned from functions and placed into containers.

[Example:

mutex cout_mut;
...
mutex::scoped_lock
get_cout_lock()  // return scoped_lock from function,
                 // even though not copyable
{
    return mutex::scoped_lock(cout_mut, defer_lock);
}
...
vector<mutex::scoped_lock> stdio_locks;
stdio_locks.push_back(get_cout_lock());  // store scoped_lock in container,
                                         // even though not copyable
...
void foo()
{   // access lock for cout_mut from container, even though not copyable
    adapt_lock<mutex::scoped_lock> lock(stdio_locks[0]);
    cout << "some stuff" << '\n';
    ...
}

--end example]

Additionally, if read/write style locks are added to this proposal, conversions between lock types can become very useful. For example, here is a study which explores the combination of a scoped_lock (also known as a write lock, same as proposed by Becker), a sharable_lock (also known as a read lock), and an upgradable_lock (a lock capable of sharing locks with a sharable_lock, and also transferring exclusive ownership to a scoped_lock). In this study, move semantics is used to transfer ownership among the three different types of locks.

[Example:

struct A
{
    ...
    mutex mut_;
    ...
};

void foo(A& a1, A& a2)
{
    typedef mutex::scoped_lock     write_lock;
    typedef mutex::upgradable_lock read_lock;
    read_lock a2_rlock(a2.mut_, defer_lock);  // a2.mut_ not yet read-locked
    {
    write_lock a1_wlock(a1.mut_, defer_lock); // a1.mut_ not yet write-locked
    lock_both(a1_wlock, a2_rlock);  // a1.mut_ write-locked, a2.mut_ read-locked
                                    // Use of lock_both negates deadlock possibility
    a1 = a2;                        // Assignment is now thread-safe
    }                               // a1.mut_ now unlocked, a2.mut_ still read-locked
    ...
    if (some condition)
    {
        write_lock a2_wlock(move(a2_rlock));  // a2.mut_ upgraded from read-lock to
        a2.modify();                          // write-lock.  a2.modify() is now safe.
    }                    // a2.mut_ now unlocked if some condition was met
}                        // a2.mut_ now (read)unlocked if some condition was not met

--end example]

Here the function foo needs to write-lock a1's mutex but only read-lock a2's mutex in order to assign from a2 to a1. But based on some condition, foo may need to later write-lock a2 without loosing the existing read-lock. This is where an upgradable lock comes in handy. Using the move syntax, a2's mutex is atomically upgraded from read to write so that non-const operations can now be carried out on a2. And those operations can assume that the state read under a2's read-lock is still valid because the upgrade from read to write lock was atomic.

Should the "some condition" not be met, foo can share lock ownership of a2 with other functions that need only read access to a2, thus improving system throughput.

Move semantics has played a role here by allowing the transfer of mutex ownership among the different locks, with a syntax and semantics that is uniform with the rest of the C++ world. Thus non-copyable locks can even be manipulated by generic move-aware code (such as standard containers and algorithms).