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:
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: move and move_backward. These two functions are merely convenience functions as any copying style algorithm can be turned into a moving style algorithm with the use of move_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 move and move_backward warrant the special treatment.
Additionally the signature (though not the description) of random_shuffle is 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(InputIterator first, InputIterator last,
OutputIterator result);
template<class BidirectionalIterator1, class BidirectionalIterator2>
BidirectionalIterator2
copy_backward
(BidirectionalIterator1 first, BidirectionalIterator1 last,
BidirectionalIterator2 result);
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);
...
template<class RandomAccessIterator>
void random_shuffle(RandomAccessIterator first,
RandomAccessIterator last);
template<class RandomAccessIterator, class RandomNumberGenerator>
void random_shuffle(RandomAccessIterator first,
RandomAccessIterator last,
RandomNumberGenerator&& rand);
...
}
Insert new section for move and move_backward.
template<class InputIterator, class OutputIterator>
OutputIterator move(InputIterator first, InputIterator last,
OutputIterator result);
-1- Effects: Moves elements in the range [first, last) to the range [result, result + (last - first)) starting from first and proceeding to last. For each non-negative integer n < (last-first), performs *(result + n) = std::move(*(first + n)).
-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(BidirectionalIterator1 first,
BidirectionalIterator1 last,
BidirectionalIterator2 result);
-5- Effects: Moves elements in the range [first, last) to the range [result - (last - first), result) starting from last - 1 and proceeding to first . *
[Footnote: move_backward should be used instead of move when last is in the range [result - (last - first), result). -- end footnote]
For each positive integer n <= (last - first), performs *(result - n) = std::move(*(last - n)).
-6- Requires: result shall not be in the range [first, last).
-7- Returns: result - (last - first).
-8- Complexity: Exactly last - first move assignments.
Reduce requirements for swap to MoveConstructible and MoveAssignable.
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 remove and remove_if to MoveConstructible and MoveAssignable.
template<class ForwardIterator, class T>
ForwardIterator remove(ForwardIterator first, ForwardIterator last,
const T& value);
template<class ForwardIterator, class Predicate>
ForwardIterator remove_if(ForwardIterator first, ForwardIterator last,
Predicate pred);
-1- Requires:
The type of *first shall satisfy the
Assignable MoveAssignable requirements.
-2- Effects: Eliminates all the elements referred to by iterator i in the range [first, last) for which the following corresponding conditions hold: *i == value, pred(*i) != false.
-3- Returns: The end of the resulting range.
-4- Remarks: Stable.
-5- Complexity: Exactly last - first applications of the corresponding predicate.
Reduce requirements for unique to MoveConstructible and MoveAssignable.
template<class ForwardIterator>
ForwardIterator unique(ForwardIterator first, ForwardIterator last);
template<class ForwardIterator, class BinaryPredicate>
ForwardIterator unique(ForwardIterator first, ForwardIterator last,
BinaryPredicate pred);
-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: *i == *(i - 1) or pred(*i, *(i - 1)) != false
-2- Requires: The comparison function shall be an equivalence relation. The type of *first shall satisfy the MoveAssignable requirements.
-3- Returns: The end of the resulting range.
-4- Complexity: If the range (last - first) is not empty, exactly (last - first) - 1 applications of the corresponding predicate, otherwise no applications of the predicate.
Reduce requirements for rotate to MoveConstructible and MoveAssignable. Note that we already have Swappable as well.
template<class ForwardIterator>
void rotate(ForwardIterator first, ForwardIterator middle,
ForwardIterator last);
-1- Effects: For each non-negative integer i < (last - first), places the element from the position first + i into position first + (i + (last - middle)) % (last - first).
-2- Remarks: This is a left rotate.
-3- Requires: [first, middle) and [middle, last) are valid ranges. The type of *first shall satisfy the Swappable requirements (20.1.4), the MoveConstructible requirements, and the MoveAssignable requirements.
-4- Complexity: At most last - first swaps.
Change the signature of random_shuffle. No other change is needed for the specification of random_shuffle.
template<class RandomAccessIterator>
void random_shuffle(RandomAccessIterator first,
RandomAccessIterator last);
template<class RandomAccessIterator, class RandomNumberGenerator>
void random_shuffle(RandomAccessIterator first,
RandomAccessIterator last,
RandomNumberGenerator&& rand);
Reduce requirements for stable_partition to MoveConstructible and MoveAssignable. Note that we already have Swappable as well.
template<class BidirectionalIterator, class Predicate>
BidirectionalIterator
stable_partition(BidirectionalIterator first,
BidirectionalIterator last, Predicate pred);
-5- Effects: Places all the elements in the range [first, last) that satisfy pred before all the elements that do not satisfy it.
-6- Returns: An iterator i such that for any iterator j in the range [first, i), pred(*j) != false, and for any iterator k in the range [i, last), pred(*j) == false. The relative order of the elements in both groups is preserved.
-7- Requires: The type of *first shall satisfy the Swappable requirements (20.1.4), the MoveConstructible requirements, and the MoveAssignable requirements.
-8- Complexity: At most (last - first) * log(last - first) swaps, but only linear number of swaps if there is enough extra memory. Exactly last - first applications of the predicate.
Reduce requirements for sort to MoveConstructible and MoveAssignable. Note that we already have Swappable as well.
template<class RandomAccessIterator>
void sort(RandomAccessIterator first, RandomAccessIterator last);
template<class RandomAccessIterator, class Compare>
void sort(RandomAccessIterator first, RandomAccessIterator last,
Compare comp);
-1- Effects: Sorts the elements in the range [first, last).
-2- Requires: The type of *first shall satisfy the Swappable requirements (20.1.4), the MoveConstructible requirements, and the MoveAssignable requirements.
-3- Complexity: Approximately N log N (where N == last - first) comparisons on the average.*
Reduce requirements for stable_sort to MoveConstructible and MoveAssignable. Note that we already have Swappable as well.
template<class RandomAccessIterator>
void stable_sort(RandomAccessIterator first, RandomAccessIterator last);
template<class RandomAccessIterator, class Compare>
void stable_sort(RandomAccessIterator first, RandomAccessIterator last,
Compare comp);
-1- Effects: Sorts the elements in the range [first, last).
-2- Requires: The type of *first shall satisfy the Swappable requirements (20.1.4), the MoveConstructible requirements, and the MoveAssignable requirements.
-3- Complexity: It does at most N(log N)2 (where N == last - first) comparisons; if enough extra memory is available, it is N log N.
-4- Remarks: Stable.
Reduce requirements for partial_sort to MoveConstructible and MoveAssignable. Note that we already have Swappable as well.
template<class RandomAccessIterator>
void partial_sort(RandomAccessIterator first,
RandomAccessIterator middle,
RandomAccessIterator last);
template<class RandomAccessIterator, class Compare>
void partial_sort(RandomAccessIterator first,
RandomAccessIterator middle,
RandomAccessIterator last,
Compare comp);
-1- Effects: Places the first middle - first sorted elements from the range [first, last) into the range [first, middle). The rest of the elements in the range [middle, last) are placed in an unspecified order.
-2- Requires: The type of *first shall satisfy the Swappable requirements (20.1.4), the MoveConstructible requirements, and the MoveAssignable requirements.
-3- Complexity: It takes approximately (last - first) * log(middle - first) comparisons.
Reduce requirements for partial_sort to MoveConstructible and CopyAssignable. Note that we already have Swappable as well. Also note that while CopyAssignable is required, CopyConstructible is not.
template<class InputIterator, class RandomAccessIterator>
RandomAccessIterator
partial_sort_copy(InputIterator first, InputIterator last,
RandomAccessIterator result_first,
RandomAccessIterator result_last);
template<class InputIterator, class RandomAccessIterator,
class Compare>
RandomAccessIterator
partial_sort_copy(InputIterator first, InputIterator last,
RandomAccessIterator result_first,
RandomAccessIterator result_last,
Compare comp);
-1- Effects: Places the first min(last - first, result_last - result_first) sorted elements into the range [result_first, result_first + min(last - first, result_last - result_first)).
-2- Returns: The smaller of: result_last or result_first + (last - first)
-3- Requires: The type of *result_first shall satisfy the Swappable requirements (20.1.4), the MoveConstructible requirements, and the CopyAssignable requirements.
-4- Complexity: Approximately (last - first) * log(min(last - first, result_last - result_first)) comparisons.
Reduce requirements for nth_element to MoveConstructible and MoveAssignable. Note that we already have Swappable as well.
template<class RandomAccessIterator>
void nth_element(RandomAccessIterator first, RandomAccessIterator nth,
RandomAccessIterator last);
template<class RandomAccessIterator, class Compare>
void nth_element(RandomAccessIterator first, RandomAccessIterator nth,
RandomAccessIterator last, Compare comp);
-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 i in the range [first, nth) and any iterator j in the range [nth, last) it holds that: !(*i > *j) or comp(*j, *i) == false.
-2- Requires: The type of *first shall satisfy the Swappable requirements (20.1.4), the MoveConstructible requirements, and the MoveAssignable requirements.
-3- Complexity: Linear on average.
Reduce requirements for inplace_merge to MoveConstructible and MoveAssignable. Note that we already have Swappable as well.
template<class BidirectionalIterator>
void inplace_merge(BidirectionalIterator first,
BidirectionalIterator middle,
BidirectionalIterator last);
template<class BidirectionalIterator, class Compare>
void inplace_merge(BidirectionalIterator first,
BidirectionalIterator middle,
BidirectionalIterator last, Compare comp);
-6- Effects: Merges two sorted consecutive ranges [first, middle) and [middle, last), putting the result of the merge into the range [first, last). The resulting range will be in non-decreasing order; that is, for every iterator i in [first, last) other than first, the condition *i < *(i - 1) or, respectively, comp(*i, *(i - 1)) will be false.
-7- Requires: The type of *first shall satisfy the Swappable requirements (20.1.4), the MoveConstructible requirements, and the MoveAssignable requirements.
-8- Complexity: When enough additional memory is available, (last - first) - 1 comparisons. If no additional memory is available, an algorithm with complexity N log N (where N is equal to last - first) may be used.
-9- Remarks: Stable.
Reduce requirements for the heap operations to MoveConstructible and MoveAssignable (no longer requiring CopyConstructible and CopyAssignable). Note that we already have Swappable as well for pop_heap and sort_heap.
template<class RandomAccessIterator>
void push_heap(RandomAccessIterator first, RandomAccessIterator last);
template<class RandomAccessIterator, class Compare>
void push_heap(RandomAccessIterator first, RandomAccessIterator last,
Compare comp);
-1- Effects: Places the value in the location last - 1 into the resulting heap [first, last).
-2- Requires: The range [first, last - 1) shall be a valid heap. The type of *first shall satisfy the MoveConstructible requirements, and the MoveAssignable requirements.
-3- Complexity: At most log(last - first) comparisons.
template<class RandomAccessIterator>
void pop_heap(RandomAccessIterator first, RandomAccessIterator last);
template<class RandomAccessIterator, class Compare>
void pop_heap(RandomAccessIterator first, RandomAccessIterator last,
Compare comp);
-1- Effects: Swaps the value in the location first with the value in the location last - 1 and makes [first, last - 1) into a heap.
-2- Requires: The range [first, last) shall be a valid heap. The type of *first shall satisfy the Swappable requirements (20.1.4), the MoveConstructible requirements, and the MoveAssignable requirements.
-3- Complexity: At most 2 * log(last - first) comparisons.
template<class RandomAccessIterator>
void make_heap(RandomAccessIterator first, RandomAccessIterator last);
template<class RandomAccessIterator, class Compare>
void make_heap(RandomAccessIterator first, RandomAccessIterator last,
Compare comp);
-1- Effects: Constructs a heap out of the range [first, last).
-2- Requires: The type of *first shall satisfy the MoveConstructible requirements, and the MoveAssignable requirements.
-3- Complexity: At most 3 * (last - first) comparisons.
template<class RandomAccessIterator>
void sort_heap(RandomAccessIterator first, RandomAccessIterator last);
template<class RandomAccessIterator, class Compare>
void sort_heap(RandomAccessIterator first, RandomAccessIterator last,
Compare comp);
-1- Effects: Sorts elements in the heap [first, last).
-2- Requires: The range [first, last) shall be a valid heap. The type of *first shall satisfy the Swappable requirements (20.1.4), the MoveConstructible requirements, and the MoveAssignable requirements.
-3- Complexity: At most N log N comparisons (where N == last - first).