Howard E. Hinnant

2005-08-26

- Introduction
- 25 - Algorithms library

Rvalue Reference Recommendations for Chapter 20

Rvalue Reference Recommendations for Chapter 21

Rvalue Reference Recommendations for Chapter 23

Rvalue Reference Recommendations for Chapter 24

Rvalue Reference Recommendations for Chapter 26

Rvalue Reference Recommendations for Chapter 27

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

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

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

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

The proposed wording in this paper accomplishes three tasks:

- New algorithms
`move`and`move_backward`are introduced. - The
`random_shuffle`signature is altered to accept rvalue generators. - The requirements on the
`value_type`of several algorithms are reduced from`CopyConstructible`and`CopyAssignable`to`MoveConstructible`and`MoveAssignable`.

This third action is the most important as it allows clients to use these algorithms with sequences of movable but non-copyable types. For example:

vector<unique_ptr<T> > v; ... sort(v.begin(), v.end(), indirect_less()); // ok to sort unique_ptr's

**Header <algorithm> synopsis**

The synopsis is updated with two new functions:

moveandmove_backward. These two functions are merely convenience functions as any copying style algorithm can be turned into a moving style algorithm with the use ofmove_iterator. For example:copy(make_move_iterator(first), make_move_iterator(last), result);is equivalent to:

move(first, last, result);However the anticipated frequency of use of

moveandmove_backwardwarrant the special treatment.Additionally the signature (though not the description) of

random_shuffleis modified so as to accept lvalue and rvalue random number generators.

namespace std { ... //lib.alg.modifying.operations, modifying sequence operations://lib.alg.copy, copy:template<class InputIterator, class OutputIterator> OutputIterator copy(InputIteratorfirst, InputIteratorlast, OutputIteratorresult); template<class BidirectionalIterator1, class BidirectionalIterator2> BidirectionalIterator2 copy_backward (BidirectionalIterator1first, BidirectionalIterator1last, BidirectionalIterator2result); template<class InputIterator, class OutputIterator> OutputIterator move(InputIteratorfirst, InputIteratorlast, OutputIteratorresult); template<class BidirectionalIterator1, class BidirectionalIterator2> BidirectionalIterator2 move_backward (BidirectionalIterator1first, BidirectionalIterator1last, BidirectionalIterator2result); ... template<class RandomAccessIterator> void random_shuffle(RandomAccessIteratorfirst, RandomAccessIteratorlast); template<class RandomAccessIterator, class RandomNumberGenerator> void random_shuffle(RandomAccessIteratorfirst, RandomAccessIteratorlast, RandomNumberGenerator&&rand); ... }

Insert new section for

moveandmove_backward.

template<class InputIterator, class OutputIterator> OutputIterator move(InputIteratorfirst, InputIteratorlast, OutputIteratorresult);

-1- **Effects:**
Moves elements in the range `[ first, last)` to the range

-2- **Returns:**
` result + (last - first)`.

-3- **Requires:**
`result` shall not be in the range `[ first, last)`.

-4- **Complexity:**
Exactly ` last - first` move assignments.

template<class BidirectionalIterator1, class BidirectionalIterator2> BidirectionalIterator2 move_backward(BidirectionalIterator1first, BidirectionalIterator1last, BidirectionalIterator2result);

-5- **Effects:**
Moves elements in the range `[ first, last)` to the range

[Footnote:move_backwardshould be used instead ofmovewhenis in the rangelast[.result- (last-first),result)-- end footnote]

For each positive integer `n <= ( last - first)`,
performs

-6- **Requires:**
` result` shall not be in the range

-7- **Returns:**
` result - (last - first)`.

-8- **Complexity:**
Exactly ` last - first` move assignments.

Reduce requirements for

swaptoMoveConstructibleandMoveAssignable.

template<class T> void swap(T&a, T&b);

-1- **Requires:**
Type `T` is `CopyConstructible`
(lib.copyconstructible)`MoveConstructible` and `Assignable`
(lib.container.requirements)`MoveAssignable`.

Reduce requirements for

removeandremove_iftoMoveConstructibleandMoveAssignable.

template<class ForwardIterator, class T> ForwardIterator remove(ForwardIteratorfirst, ForwardIteratorlast, const T&value); template<class ForwardIterator, class Predicate> ForwardIterator remove_if(ForwardIteratorfirst, ForwardIteratorlast, Predicatepred);

-1- **Requires:**
The type of `* first` shall satisfy the

-2- **Effects:** Eliminates all the elements referred to by iterator
`i` in the range `[ first, last)` for which the
following corresponding conditions hold:

-3- **Returns:**
The end of the resulting range.

-4- **Remarks:** Stable.

-5- **Complexity:**
Exactly ` last - first` applications of the corresponding
predicate.

Reduce requirements for

uniquetoMoveConstructibleandMoveAssignable.

template<class ForwardIterator> ForwardIterator unique(ForwardIteratorfirst, ForwardIteratorlast); template<class ForwardIterator, class BinaryPredicate> ForwardIterator unique(ForwardIteratorfirst, ForwardIteratorlast, BinaryPredicatepred);

-1- **Effects:**
Eliminates all but the first element from every consecutive group of equal
elements referred to by the iterator `i` in the range `[ first,
last)` for which the following corresponding conditions hold:

-2- **Requires:** The comparison function shall be an equivalence relation.
The type of `* first` shall satisfy the

-3- **Returns:**
The end of the resulting range.

-4- **Complexity:**
If the range `( last - first)` is not empty, exactly

Reduce requirements for

rotatetoMoveConstructibleandMoveAssignable. Note that we already haveSwappableas well.

template<class ForwardIterator> void rotate(ForwardIteratorfirst, ForwardIteratormiddle, ForwardIteratorlast);

-1- **Effects:**
For each non-negative integer `i < ( last - first)`,
places the element from the position

-2- **Remarks:**
This is a left rotate.

-3- **Requires:**
`[ first, middle)` and

-4- **Complexity:**
At most ` last - first` swaps.

Change the signature of

random_shuffle. No other change is needed for the specification ofrandom_shuffle.

template<class RandomAccessIterator> void random_shuffle(RandomAccessIteratorfirst, RandomAccessIteratorlast); template<class RandomAccessIterator, class RandomNumberGenerator> void random_shuffle(RandomAccessIteratorfirst, RandomAccessIteratorlast, RandomNumberGenerator&&rand);

Reduce requirements for

stable_partitiontoMoveConstructibleandMoveAssignable. Note that we already haveSwappableas well.

template<class BidirectionalIterator, class Predicate> BidirectionalIterator stable_partition(BidirectionalIteratorfirst, BidirectionalIteratorlast, Predicatepred);

-5- **Effects:**
Places all the elements in the range `[ first, last)` that
satisfy

-6- **Returns:**
An iterator `i` such that for any iterator `j` in the range
`[ first, i)`,

-7- **Requires:** The type of `* first` shall satisfy the

-8- **Complexity:**
At most `(last - first) *
log(last - first)` swaps, but only linear
number of swaps if there is enough extra memory. Exactly

Reduce requirements for

sorttoMoveConstructibleandMoveAssignable. Note that we already haveSwappableas well.

template<class RandomAccessIterator> void sort(RandomAccessIteratorfirst, RandomAccessIteratorlast); template<class RandomAccessIterator, class Compare> void sort(RandomAccessIteratorfirst, RandomAccessIteratorlast, Comparecomp);

-1- **Effects:**
Sorts the elements in the range `[ first, last)`.

-2- **Requires:** The type of `* first` shall satisfy the

-3- **Complexity:**
Approximately `N log N` (where

Reduce requirements for

stable_sorttoMoveConstructibleandMoveAssignable. Note that we already haveSwappableas well.

template<class RandomAccessIterator> void stable_sort(RandomAccessIteratorfirst, RandomAccessIteratorlast); template<class RandomAccessIterator, class Compare> void stable_sort(RandomAccessIteratorfirst, RandomAccessIteratorlast, Comparecomp);

-1- **Effects:**
Sorts the elements in the range `[ first, last)`.

-2- **Requires:** The type of `* first` shall satisfy the

-3- **Complexity:**
It does at most
`N( log N)^{2}`
(where

-4- **Remarks:** Stable.

Reduce requirements for

partial_sorttoMoveConstructibleandMoveAssignable. Note that we already haveSwappableas well.

template<class RandomAccessIterator> void partial_sort(RandomAccessIteratorfirst, RandomAccessIteratormiddle, RandomAccessIteratorlast); template<class RandomAccessIterator, class Compare> void partial_sort(RandomAccessIteratorfirst, RandomAccessIteratormiddle, RandomAccessIteratorlast, Comparecomp);

-1- **Effects:**
Places the first ` middle - first` sorted elements from the
range

-2- **Requires:** The type of `* first` shall satisfy the

-3- **Complexity:**
It takes approximately `( last - first) * log(middle -
first)` comparisons.

Reduce requirements for

partial_sorttoMoveConstructibleandCopyAssignable. Note that we already haveSwappableas well. Also note that whileCopyAssignableis required,CopyConstructibleis not.

template<class InputIterator, class RandomAccessIterator> RandomAccessIterator partial_sort_copy(InputIteratorfirst, InputIteratorlast, RandomAccessIteratorresult_first, RandomAccessIteratorresult_last); template<class InputIterator, class RandomAccessIterator, class Compare> RandomAccessIterator partial_sort_copy(InputIteratorfirst, InputIteratorlast, RandomAccessIteratorresult_first, RandomAccessIteratorresult_last, Comparecomp);

-1- **Effects:**
Places the first `min( last - first, result_last -
result_first)` sorted elements into the range

-2- **Returns:**
The smaller of: ` result_last` or

-3- **Requires:** The type of `* result_first` shall satisfy the

-4- **Complexity:**
Approximately `( last - first) * log(min(last -
first, result_last - result_first))` comparisons.

Reduce requirements for

nth_elementtoMoveConstructibleandMoveAssignable. Note that we already haveSwappableas well.

template<class RandomAccessIterator> void nth_element(RandomAccessIteratorfirst, RandomAccessIteratornth, RandomAccessIteratorlast); template<class RandomAccessIterator, class Compare> void nth_element(RandomAccessIteratorfirst, RandomAccessIteratornth, RandomAccessIteratorlast, Comparecomp);

-1- After `nth_element` the element in the position pointed to by
` nth` is the element that would be in that position if the whole
range were sorted. Also for any iterator

**Requires:** The type of `* first` shall satisfy the

-3- **Complexity:**
Linear on average.

Reduce requirements for

inplace_mergetoMoveConstructibleandMoveAssignable. Note that we already haveSwappableas well.

template<class BidirectionalIterator> void inplace_merge(BidirectionalIteratorfirst, BidirectionalIteratormiddle, BidirectionalIteratorlast); template<class BidirectionalIterator, class Compare> void inplace_merge(BidirectionalIteratorfirst, BidirectionalIteratormiddle, BidirectionalIteratorlast, Comparecomp);

-6- **Effects:**
Merges two sorted consecutive ranges `[ first, middle)` and

-7- **Requires:** The type of `* first` shall satisfy the

-8- **Complexity:**
When enough additional memory is available, `( last - first) -
1` comparisons. If no additional memory is available, an algorithm with
complexity

-9- **Remarks:** Stable.

Reduce requirements for the heap operations to

MoveConstructibleandMoveAssignable(no longer requiringCopyConstructibleandCopyAssignable). Note that we already haveSwappableas well forpop_heapandsort_heap.

template<class RandomAccessIterator> void push_heap(RandomAccessIteratorfirst, RandomAccessIteratorlast); template<class RandomAccessIterator, class Compare> void push_heap(RandomAccessIteratorfirst, RandomAccessIteratorlast, Comparecomp);

-1- **Effects:**
Places the value in the location ` last - 1` into the resulting
heap

-2- **Requires:**
The range `[ first, last - 1)` shall be a valid heap. The
type of

-3- **Complexity:**
At most `log( last - first)` comparisons.

template<class RandomAccessIterator> void pop_heap(RandomAccessIteratorfirst, RandomAccessIteratorlast); template<class RandomAccessIterator, class Compare> void pop_heap(RandomAccessIteratorfirst, RandomAccessIteratorlast, Comparecomp);

-1- **Effects:**
Swaps the value in the location ` first` with the value in the
location

-2- **Requires:**
The range `[ first, last)` shall be a valid heap. The type
of

-3- **Complexity:**
At most `2 * log( last - first)` comparisons.

template<class RandomAccessIterator> void make_heap(RandomAccessIteratorfirst, RandomAccessIteratorlast); template<class RandomAccessIterator, class Compare> void make_heap(RandomAccessIteratorfirst, RandomAccessIteratorlast, Comparecomp);

-1- **Effects:**
Constructs a heap out of the range `[ first, last)`.

-2- **Requires:** The type of `* first` shall satisfy the

-3- **Complexity:**
At most `3 * ( last - first)` comparisons.

template<class RandomAccessIterator> void sort_heap(RandomAccessIteratorfirst, RandomAccessIteratorlast); template<class RandomAccessIterator, class Compare> void sort_heap(RandomAccessIteratorfirst, RandomAccessIteratorlast, Comparecomp);

-1- **Effects:**
Sorts elements in the heap `[ first, last)`.

-2- **Requires:**
The range `[ first, last)` shall be a valid heap.
The type of

-3- **Complexity:**
At most `N log N` comparisons (where