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.
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.
| expression | post-condition |
|---|---|
| T(rv) | T(rv) is equivalent to the value of rv before the construction |
| 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.]
| expression | return type | return value | post-condition |
|---|---|---|---|
| t = rv | T& | t | t is equivalent to the value of rv before the assignment |
| 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.]
| 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.]
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.
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.
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.
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).
template <class U> void construct(pointer p, U&& val);
Effects: ::new((void*)p) T(std::forward<U>(val))
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:
#include <memory>
#include <vector>
struct Base {virtual ~Base() {}};
struct Derived : Base {};
int main()
{
typedef std::unique_ptr<Base> BasePtr;
typedef std::unique_ptr<Derived> DerivedPtr;
std::vector<BasePtr> v(3); // 3 default constructed BasePtr's
v.resize(2); // No copy constructor required
v.push_back(DerivedPtr(new Derived)); // No copy constructor required
v.front() = DerivedPtr(new Derived); // No copy constructor required
v.insert(v.begin(), DerivedPtr(new Derived));// No copy constructor required
v.erase(v.begin() + v.size()/2); // No copy constructor required
// BasePtr p = v[0]; // will not compile, copy constructor required
BasePtr p = std::move(v[0]); // ok, ownership transferred to p
}
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);
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).
-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.
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);
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);
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);
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);
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);
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);
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();
};
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);
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);
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);
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);
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).
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);
};
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);
};
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);
};
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.
| 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 |
| 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 |
| 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);
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).
Summary: Give valarray a move constructor and move assignment operator.
Add:
valarray(valarray&&); valarray& operator=(valarray&&);
Summary: Make streams move constructible, move assignable and swappable. Enable clients to work with rvalue streams for operator << and operator >>.
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.
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.
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.
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);
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.
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);
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);
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);
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);
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);
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);
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);
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);
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.
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);
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;
Add:
function(function&&); function& operator=(function&&); template<typename F> function(F&&); template<typename F> function& operator=(F&&);
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;};
is_convertible should test with an rvalue source instead of lvalue source, and include a U&& signature to test against.
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.
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.
Needs changes analogous to those set forth for the standard ordered associative containers.
Add move constructors and move assignment as appropriate.
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).