tmp/tmpuqozn4oq/{from.md → to.md}
RENAMED
|
@@ -1,36 +1,62 @@
|
|
| 1 |
### Nth element <a id="alg.nth.element">[[alg.nth.element]]</a>
|
| 2 |
|
| 3 |
``` cpp
|
| 4 |
template<class RandomAccessIterator>
|
| 5 |
-
void nth_element(RandomAccessIterator first, RandomAccessIterator nth,
|
| 6 |
RandomAccessIterator last);
|
| 7 |
template<class ExecutionPolicy, class RandomAccessIterator>
|
| 8 |
void nth_element(ExecutionPolicy&& exec,
|
| 9 |
RandomAccessIterator first, RandomAccessIterator nth,
|
| 10 |
RandomAccessIterator last);
|
| 11 |
|
| 12 |
template<class RandomAccessIterator, class Compare>
|
| 13 |
-
void nth_element(RandomAccessIterator first, RandomAccessIterator nth,
|
| 14 |
RandomAccessIterator last, Compare comp);
|
| 15 |
template<class ExecutionPolicy, class RandomAccessIterator, class Compare>
|
| 16 |
void nth_element(ExecutionPolicy&& exec,
|
| 17 |
RandomAccessIterator first, RandomAccessIterator nth,
|
| 18 |
RandomAccessIterator last, Compare comp);
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
| 19 |
```
|
| 20 |
|
| 21 |
-
|
| 22 |
-
|
| 23 |
-
|
| 24 |
-
|
| 25 |
-
|
|
|
|
|
|
|
|
|
|
|
|
|
| 26 |
|
| 27 |
*Effects:* After `nth_element` the element in the position pointed to by
|
| 28 |
`nth` is the element that would be in that position if the whole range
|
| 29 |
-
were sorted, unless `nth == last`.
|
| 30 |
-
|
| 31 |
-
|
|
|
|
|
|
|
|
|
|
| 32 |
|
| 33 |
*Complexity:* For the overloads with no `ExecutionPolicy`, linear on
|
| 34 |
average. For the overloads with an `ExecutionPolicy`, 𝑂(N) applications
|
| 35 |
of the predicate, and 𝑂(N log N) swaps, where N = `last - first`.
|
| 36 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
| 1 |
### Nth element <a id="alg.nth.element">[[alg.nth.element]]</a>
|
| 2 |
|
| 3 |
``` cpp
|
| 4 |
template<class RandomAccessIterator>
|
| 5 |
+
constexpr void nth_element(RandomAccessIterator first, RandomAccessIterator nth,
|
| 6 |
RandomAccessIterator last);
|
| 7 |
template<class ExecutionPolicy, class RandomAccessIterator>
|
| 8 |
void nth_element(ExecutionPolicy&& exec,
|
| 9 |
RandomAccessIterator first, RandomAccessIterator nth,
|
| 10 |
RandomAccessIterator last);
|
| 11 |
|
| 12 |
template<class RandomAccessIterator, class Compare>
|
| 13 |
+
constexpr void nth_element(RandomAccessIterator first, RandomAccessIterator nth,
|
| 14 |
RandomAccessIterator last, Compare comp);
|
| 15 |
template<class ExecutionPolicy, class RandomAccessIterator, class Compare>
|
| 16 |
void nth_element(ExecutionPolicy&& exec,
|
| 17 |
RandomAccessIterator first, RandomAccessIterator nth,
|
| 18 |
RandomAccessIterator last, Compare comp);
|
| 19 |
+
|
| 20 |
+
template<random_access_iterator I, sentinel_for<I> S, class Comp = ranges::less,
|
| 21 |
+
class Proj = identity>
|
| 22 |
+
requires sortable<I, Comp, Proj>
|
| 23 |
+
constexpr I
|
| 24 |
+
ranges::nth_element(I first, I nth, S last, Comp comp = {}, Proj proj = {});
|
| 25 |
```
|
| 26 |
|
| 27 |
+
Let `comp` be `less{}` and `proj` be `identity{}` for the overloads with
|
| 28 |
+
no parameters by those names.
|
| 29 |
+
|
| 30 |
+
*Preconditions:* \[`first`, `nth`) and \[`nth`, `last`) are valid
|
| 31 |
+
ranges. For the overloads in namespace `std`, `RandomAccessIterator`
|
| 32 |
+
meets the *Cpp17ValueSwappable* requirements [[swappable.requirements]],
|
| 33 |
+
and the type of `*first` meets the *Cpp17MoveConstructible*
|
| 34 |
+
([[cpp17.moveconstructible]]) and *Cpp17MoveAssignable*
|
| 35 |
+
([[cpp17.moveassignable]]) requirements.
|
| 36 |
|
| 37 |
*Effects:* After `nth_element` the element in the position pointed to by
|
| 38 |
`nth` is the element that would be in that position if the whole range
|
| 39 |
+
were sorted with respect to `comp` and `proj`, unless `nth == last`.
|
| 40 |
+
Also for every iterator `i` in the range \[`first`, `nth`) and every
|
| 41 |
+
iterator `j` in the range \[`nth`, `last`) it holds that:
|
| 42 |
+
`bool(invoke(comp, invoke(proj, *j), invoke(proj, *i)))` is `false`.
|
| 43 |
+
|
| 44 |
+
*Returns:* `last` for the overload in namespace `ranges`.
|
| 45 |
|
| 46 |
*Complexity:* For the overloads with no `ExecutionPolicy`, linear on
|
| 47 |
average. For the overloads with an `ExecutionPolicy`, 𝑂(N) applications
|
| 48 |
of the predicate, and 𝑂(N log N) swaps, where N = `last - first`.
|
| 49 |
|
| 50 |
+
``` cpp
|
| 51 |
+
template<random_access_range R, class Comp = ranges::less, class Proj = identity>
|
| 52 |
+
requires sortable<iterator_t<R>, Comp, Proj>
|
| 53 |
+
constexpr borrowed_iterator_t<R>
|
| 54 |
+
ranges::nth_element(R&& r, iterator_t<R> nth, Comp comp = {}, Proj proj = {});
|
| 55 |
+
```
|
| 56 |
+
|
| 57 |
+
*Effects:* Equivalent to:
|
| 58 |
+
|
| 59 |
+
``` cpp
|
| 60 |
+
return ranges::nth_element(ranges::begin(r), nth, ranges::end(r), comp, proj);
|
| 61 |
+
```
|
| 62 |
+
|