From Jason Turner

[partial.sort.copy]

C++17 → C++20 5.2 KB 79 lines
Current Draft | LaTeX Source
Archived: C++17 | C++20
Markdown: C++17 | C++20
Explore in Adventure Game

Diff to HTML by rtfpessoa

Files changed (1) hide show
  1. tmp/tmpaarsvel_/{from.md → to.md} +58 -16
tmp/tmpaarsvel_/{from.md → to.md} RENAMED
@@ -1,10 +1,10 @@
1
  #### `partial_sort_copy` <a id="partial.sort.copy">[[partial.sort.copy]]</a>
2
 
3
  ``` cpp
4
  template<class InputIterator, class RandomAccessIterator>
5
- RandomAccessIterator
6
  partial_sort_copy(InputIterator first, InputIterator last,
7
  RandomAccessIterator result_first,
8
  RandomAccessIterator result_last);
9
  template<class ExecutionPolicy, class ForwardIterator, class RandomAccessIterator>
10
  RandomAccessIterator
@@ -13,11 +13,11 @@ template<class ExecutionPolicy, class ForwardIterator, class RandomAccessIterato
13
  RandomAccessIterator result_first,
14
  RandomAccessIterator result_last);
15
 
16
  template<class InputIterator, class RandomAccessIterator,
17
  class Compare>
18
- RandomAccessIterator
19
  partial_sort_copy(InputIterator first, InputIterator last,
20
  RandomAccessIterator result_first,
21
  RandomAccessIterator result_last,
22
  Compare comp);
23
  template<class ExecutionPolicy, class ForwardIterator, class RandomAccessIterator,
@@ -26,25 +26,67 @@ template<class ExecutionPolicy, class ForwardIterator, class RandomAccessIterato
26
  partial_sort_copy(ExecutionPolicy&& exec,
27
  ForwardIterator first, ForwardIterator last,
28
  RandomAccessIterator result_first,
29
  RandomAccessIterator result_last,
30
  Compare comp);
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
31
  ```
32
 
33
- *Requires:* `RandomAccessIterator` shall satisfy the requirements of
34
- `ValueSwappable` ([[swappable.requirements]]). The type of
35
- `*result_first` shall satisfy the requirements of `MoveConstructible`
36
- (Table  [[tab:moveconstructible]]) and of `MoveAssignable`
37
- (Table  [[tab:moveassignable]]).
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
38
 
39
- *Effects:* Places the first
40
- `min(last - first, result_last - result_first)` sorted elements into the
41
- range \[`result_first`,
42
- `result_first + min(last - first, result_last - result_first)`).
43
 
44
- *Returns:* The smaller of: `result_last` or
45
- `result_first + (last - first)`.
46
 
47
- *Complexity:* Approximately
48
- `(last - first) * log(min(last - first, result_last - result_first))`
49
- comparisons.
50
 
 
1
  #### `partial_sort_copy` <a id="partial.sort.copy">[[partial.sort.copy]]</a>
2
 
3
  ``` cpp
4
  template<class InputIterator, class RandomAccessIterator>
5
+ constexpr RandomAccessIterator
6
  partial_sort_copy(InputIterator first, InputIterator last,
7
  RandomAccessIterator result_first,
8
  RandomAccessIterator result_last);
9
  template<class ExecutionPolicy, class ForwardIterator, class RandomAccessIterator>
10
  RandomAccessIterator
 
13
  RandomAccessIterator result_first,
14
  RandomAccessIterator result_last);
15
 
16
  template<class InputIterator, class RandomAccessIterator,
17
  class Compare>
18
+ constexpr RandomAccessIterator
19
  partial_sort_copy(InputIterator first, InputIterator last,
20
  RandomAccessIterator result_first,
21
  RandomAccessIterator result_last,
22
  Compare comp);
23
  template<class ExecutionPolicy, class ForwardIterator, class RandomAccessIterator,
 
26
  partial_sort_copy(ExecutionPolicy&& exec,
27
  ForwardIterator first, ForwardIterator last,
28
  RandomAccessIterator result_first,
29
  RandomAccessIterator result_last,
30
  Compare comp);
31
+
32
+ template<input_iterator I1, sentinel_for<I1> S1, random_access_iterator I2, sentinel_for<I2> S2,
33
+ class Comp = ranges::less, class Proj1 = identity, class Proj2 = identity>
34
+ requires indirectly_copyable<I1, I2> && sortable<I2, Comp, Proj2> &&
35
+ indirect_strict_weak_order<Comp, projected<I1, Proj1>, projected<I2, Proj2>>
36
+ constexpr ranges::partial_sort_copy_result<I1, I2>
37
+ ranges::partial_sort_copy(I1 first, S1 last, I2 result_first, S2 result_last,
38
+ Comp comp = {}, Proj1 proj1 = {}, Proj2 proj2 = {});
39
+ template<input_range R1, random_access_range R2, class Comp = ranges::less,
40
+ class Proj1 = identity, class Proj2 = identity>
41
+ requires indirectly_copyable<iterator_t<R1>, iterator_t<R2>> &&
42
+ sortable<iterator_t<R2>, Comp, Proj2> &&
43
+ indirect_strict_weak_order<Comp, projected<iterator_t<R1>, Proj1>,
44
+ projected<iterator_t<R2>, Proj2>>
45
+ constexpr ranges::partial_sort_copy_result<borrowed_iterator_t<R1>, borrowed_iterator_t<R2>>
46
+ ranges::partial_sort_copy(R1&& r, R2&& result_r, Comp comp = {},
47
+ Proj1 proj1 = {}, Proj2 proj2 = {});
48
  ```
49
 
50
+ Let N be min(`last - first`, `result_last - result_first`). Let `comp`
51
+ be `less{}`, and `proj1` and `proj2` be `identity{}` for the overloads
52
+ with no parameters by those names.
53
+
54
+ *Mandates:* For the overloads in namespace `std`, the expression
55
+ `*first` is writable [[iterator.requirements.general]] to
56
+ `result_first`.
57
+
58
+ *Preconditions:* For the overloads in namespace `std`,
59
+ `RandomAccessIterator` meets the *Cpp17ValueSwappable*
60
+ requirements [[swappable.requirements]], the type of `*result_first`
61
+ meets the *Cpp17MoveConstructible* ([[cpp17.moveconstructible]]) and
62
+ *Cpp17MoveAssignable* ([[cpp17.moveassignable]]) requirements.
63
+
64
+ *Preconditions:* For iterators `a1` and `b1` in \[`first`, `last`), and
65
+ iterators `x2` and `y2` in \[`result_first`, `result_last`), after
66
+ evaluating the assignment `*y2 = *b1`, let E be the value of
67
+
68
+ ``` cpp
69
+ bool(invoke(comp, invoke(proj1, *a1), invoke(proj2, *y2))).
70
+ ```
71
+
72
+ Then, after evaluating the assignment `*x2 = *a1`, E is equal to
73
+
74
+ ``` cpp
75
+ bool(invoke(comp, invoke(proj2, *x2), invoke(proj2, *y2))).
76
+ ```
77
+
78
+ [*Note 1*: Writing a value from the input range into the output range
79
+ does not affect how it is ordered by `comp` and `proj1` or
80
+ `proj2`. — *end note*]
81
+
82
+ *Effects:* Places the first N elements as sorted with respect to `comp`
83
+ and `proj2` into the range \[`result_first`, `result_first + `N).
84
 
85
+ *Returns:*
 
 
 
86
 
87
+ - `result_first + `N for the overloads in namespace `std`.
88
+ - `{last, result_first + `N`}` for the overloads in namespace `ranges`.
89
 
90
+ *Complexity:* Approximately `(last - first) * log `N comparisons, and
91
+ twice as many projections.
 
92