From Jason Turner

[alg.sort]

C++14 → C++17 9.6 KB 127 lines
Current Draft | LaTeX Source
Archived: C++14 | C++17
Markdown: C++14 | C++17
Explore in Adventure Game

Diff to HTML by rtfpessoa

Files changed (1) hide show
  1. tmp/tmph3zpk4xz/{from.md → to.md} +96 -27
tmp/tmph3zpk4xz/{from.md → to.md} RENAMED
@@ -3,111 +3,150 @@
3
  #### `sort` <a id="sort">[[sort]]</a>
4
 
5
  ``` cpp
6
  template<class RandomAccessIterator>
7
  void sort(RandomAccessIterator first, RandomAccessIterator last);
 
 
 
8
 
9
  template<class RandomAccessIterator, class Compare>
10
  void sort(RandomAccessIterator first, RandomAccessIterator last,
11
  Compare comp);
 
 
 
 
12
  ```
13
 
14
- *Effects:* Sorts the elements in the range \[`first`, `last`).
15
-
16
  *Requires:* `RandomAccessIterator` shall satisfy the requirements of
17
  `ValueSwappable` ([[swappable.requirements]]). The type of `*first`
18
  shall satisfy the requirements of `MoveConstructible`
19
- (Table  [[moveconstructible]]) and of `MoveAssignable`
20
- (Table  [[moveassignable]]).
21
 
22
- *Complexity:* 𝑂(Nlog(N)) (where N` == last - first`) comparisons.
 
 
23
 
24
  #### `stable_sort` <a id="stable.sort">[[stable.sort]]</a>
25
 
26
  ``` cpp
27
  template<class RandomAccessIterator>
28
  void stable_sort(RandomAccessIterator first, RandomAccessIterator last);
 
 
 
29
 
30
  template<class RandomAccessIterator, class Compare>
31
  void stable_sort(RandomAccessIterator first, RandomAccessIterator last,
32
  Compare comp);
 
 
 
 
33
  ```
34
 
35
- *Effects:* Sorts the elements in the range \[`first`, `last`).
36
-
37
  *Requires:* `RandomAccessIterator` shall satisfy the requirements of
38
  `ValueSwappable` ([[swappable.requirements]]). The type of `*first`
39
  shall satisfy the requirements of `MoveConstructible`
40
- (Table  [[moveconstructible]]) and of `MoveAssignable`
41
- (Table  [[moveassignable]]).
42
 
43
- *Complexity:* It does at most N log²(N) (where N` == last - first`)
44
- comparisons; if enough extra memory is available, it is N log(N).
 
 
45
 
46
  *Remarks:* Stable ([[algorithm.stable]]).
47
 
48
  #### `partial_sort` <a id="partial.sort">[[partial.sort]]</a>
49
 
50
  ``` cpp
51
  template<class RandomAccessIterator>
52
  void partial_sort(RandomAccessIterator first,
53
  RandomAccessIterator middle,
54
  RandomAccessIterator last);
 
 
 
 
 
55
 
56
  template<class RandomAccessIterator, class Compare>
57
  void partial_sort(RandomAccessIterator first,
58
  RandomAccessIterator middle,
59
  RandomAccessIterator last,
60
  Compare comp);
 
 
 
 
 
 
61
  ```
62
 
 
 
 
 
 
 
63
  *Effects:* Places the first `middle - first` sorted elements from the
64
  range \[`first`, `last`) into the range \[`first`, `middle`). The rest
65
  of the elements in the range \[`middle`, `last`) are placed in an
66
  unspecified order.
67
 
68
- *Requires:* `RandomAccessIterator` shall satisfy the requirements of
69
- `ValueSwappable` ([[swappable.requirements]]). The type of `*first`
70
- shall satisfy the requirements of `MoveConstructible`
71
- (Table  [[moveconstructible]]) and of `MoveAssignable`
72
- (Table  [[moveassignable]]).
73
-
74
- *Complexity:* It takes approximately
75
- `(last - first) * log(middle - first)` comparisons.
76
 
77
  #### `partial_sort_copy` <a id="partial.sort.copy">[[partial.sort.copy]]</a>
78
 
79
  ``` cpp
80
  template<class InputIterator, class RandomAccessIterator>
81
  RandomAccessIterator
82
  partial_sort_copy(InputIterator first, InputIterator last,
83
  RandomAccessIterator result_first,
84
  RandomAccessIterator result_last);
 
 
 
 
 
 
85
 
86
  template<class InputIterator, class RandomAccessIterator,
87
  class Compare>
88
  RandomAccessIterator
89
  partial_sort_copy(InputIterator first, InputIterator last,
90
  RandomAccessIterator result_first,
91
  RandomAccessIterator result_last,
92
  Compare comp);
 
 
 
 
 
 
 
 
93
  ```
94
 
 
 
 
 
 
 
95
  *Effects:* Places the first
96
  `min(last - first, result_last - result_first)` sorted elements into the
97
  range \[`result_first`,
98
  `result_first + min(last - first, result_last - result_first)`).
99
 
100
  *Returns:* The smaller of: `result_last` or
101
  `result_first + (last - first)`.
102
 
103
- *Requires:* `RandomAccessIterator` shall satisfy the requirements of
104
- `ValueSwappable` ([[swappable.requirements]]). The type of
105
- `*result_first` shall satisfy the requirements of `MoveConstructible`
106
- (Table  [[moveconstructible]]) and of `MoveAssignable`
107
- (Table  [[moveassignable]]).
108
-
109
  *Complexity:* Approximately
110
  `(last - first) * log(min(last - first, result_last - result_first))`
111
  comparisons.
112
 
113
  #### `is_sorted` <a id="is.sorted">[[is.sorted]]</a>
@@ -117,27 +156,57 @@ template<class ForwardIterator>
117
  bool is_sorted(ForwardIterator first, ForwardIterator last);
118
  ```
119
 
120
  *Returns:* `is_sorted_until(first, last) == last`
121
 
 
 
 
 
 
 
 
 
 
122
  ``` cpp
123
  template<class ForwardIterator, class Compare>
124
  bool is_sorted(ForwardIterator first, ForwardIterator last,
125
  Compare comp);
126
  ```
127
 
128
  *Returns:* `is_sorted_until(first, last, comp) == last`
129
 
 
 
 
 
 
 
 
 
 
 
 
 
 
130
  ``` cpp
131
  template<class ForwardIterator>
132
  ForwardIterator is_sorted_until(ForwardIterator first, ForwardIterator last);
 
 
 
 
133
  template<class ForwardIterator, class Compare>
134
  ForwardIterator is_sorted_until(ForwardIterator first, ForwardIterator last,
135
  Compare comp);
 
 
 
 
136
  ```
137
 
138
- *Returns:* If `distance(first, last) < 2`, returns `last`. Otherwise,
139
- returns the last iterator `i` in \[`first`, `last`\] for which the range
140
  \[`first`, `i`) is sorted.
141
 
142
  *Complexity:* Linear.
143
 
 
3
  #### `sort` <a id="sort">[[sort]]</a>
4
 
5
  ``` cpp
6
  template<class RandomAccessIterator>
7
  void sort(RandomAccessIterator first, RandomAccessIterator last);
8
+ template<class ExecutionPolicy, class RandomAccessIterator>
9
+ void sort(ExecutionPolicy&& exec,
10
+ RandomAccessIterator first, RandomAccessIterator last);
11
 
12
  template<class RandomAccessIterator, class Compare>
13
  void sort(RandomAccessIterator first, RandomAccessIterator last,
14
  Compare comp);
15
+ template<class ExecutionPolicy, class RandomAccessIterator, class Compare>
16
+ void sort(ExecutionPolicy&& exec,
17
+ RandomAccessIterator first, RandomAccessIterator last,
18
+ Compare comp);
19
  ```
20
 
 
 
21
  *Requires:* `RandomAccessIterator` shall satisfy the requirements of
22
  `ValueSwappable` ([[swappable.requirements]]). The type of `*first`
23
  shall satisfy the requirements of `MoveConstructible`
24
+ (Table  [[tab:moveconstructible]]) and of `MoveAssignable`
25
+ (Table  [[tab:moveassignable]]).
26
 
27
+ *Effects:* Sorts the elements in the range \[`first`, `last`).
28
+
29
+ *Complexity:* 𝑂(N log N) comparisons, where N = `last - first`.
30
 
31
  #### `stable_sort` <a id="stable.sort">[[stable.sort]]</a>
32
 
33
  ``` cpp
34
  template<class RandomAccessIterator>
35
  void stable_sort(RandomAccessIterator first, RandomAccessIterator last);
36
+ template<class ExecutionPolicy, class RandomAccessIterator>
37
+ void stable_sort(ExecutionPolicy&& exec,
38
+ RandomAccessIterator first, RandomAccessIterator last);
39
 
40
  template<class RandomAccessIterator, class Compare>
41
  void stable_sort(RandomAccessIterator first, RandomAccessIterator last,
42
  Compare comp);
43
+ template<class ExecutionPolicy, class RandomAccessIterator, class Compare>
44
+ void stable_sort(ExecutionPolicy&& exec,
45
+ RandomAccessIterator first, RandomAccessIterator last,
46
+ Compare comp);
47
  ```
48
 
 
 
49
  *Requires:* `RandomAccessIterator` shall satisfy the requirements of
50
  `ValueSwappable` ([[swappable.requirements]]). The type of `*first`
51
  shall satisfy the requirements of `MoveConstructible`
52
+ (Table  [[tab:moveconstructible]]) and of `MoveAssignable`
53
+ (Table  [[tab:moveassignable]]).
54
 
55
+ *Effects:* Sorts the elements in the range \[`first`, `last`).
56
+
57
+ *Complexity:* At most N log²(N) comparisons, where N = `last - first`,
58
+ but only N log N comparisons if there is enough extra memory.
59
 
60
  *Remarks:* Stable ([[algorithm.stable]]).
61
 
62
  #### `partial_sort` <a id="partial.sort">[[partial.sort]]</a>
63
 
64
  ``` cpp
65
  template<class RandomAccessIterator>
66
  void partial_sort(RandomAccessIterator first,
67
  RandomAccessIterator middle,
68
  RandomAccessIterator last);
69
+ template<class ExecutionPolicy, class RandomAccessIterator>
70
+ void partial_sort(ExecutionPolicy&& exec,
71
+ RandomAccessIterator first,
72
+ RandomAccessIterator middle,
73
+ RandomAccessIterator last);
74
 
75
  template<class RandomAccessIterator, class Compare>
76
  void partial_sort(RandomAccessIterator first,
77
  RandomAccessIterator middle,
78
  RandomAccessIterator last,
79
  Compare comp);
80
+ template<class ExecutionPolicy, class RandomAccessIterator, class Compare>
81
+ void partial_sort(ExecutionPolicy&& exec,
82
+ RandomAccessIterator first,
83
+ RandomAccessIterator middle,
84
+ RandomAccessIterator last,
85
+ Compare comp);
86
  ```
87
 
88
+ *Requires:* `RandomAccessIterator` shall satisfy the requirements of
89
+ `ValueSwappable` ([[swappable.requirements]]). The type of `*first`
90
+ shall satisfy the requirements of `MoveConstructible`
91
+ (Table  [[tab:moveconstructible]]) and of `MoveAssignable`
92
+ (Table  [[tab:moveassignable]]).
93
+
94
  *Effects:* Places the first `middle - first` sorted elements from the
95
  range \[`first`, `last`) into the range \[`first`, `middle`). The rest
96
  of the elements in the range \[`middle`, `last`) are placed in an
97
  unspecified order.
98
 
99
+ *Complexity:* Approximately `(last - first) * log(middle - first)`
100
+ comparisons.
 
 
 
 
 
 
101
 
102
  #### `partial_sort_copy` <a id="partial.sort.copy">[[partial.sort.copy]]</a>
103
 
104
  ``` cpp
105
  template<class InputIterator, class RandomAccessIterator>
106
  RandomAccessIterator
107
  partial_sort_copy(InputIterator first, InputIterator last,
108
  RandomAccessIterator result_first,
109
  RandomAccessIterator result_last);
110
+ template<class ExecutionPolicy, class ForwardIterator, class RandomAccessIterator>
111
+ RandomAccessIterator
112
+ partial_sort_copy(ExecutionPolicy&& exec,
113
+ ForwardIterator first, ForwardIterator last,
114
+ RandomAccessIterator result_first,
115
+ RandomAccessIterator result_last);
116
 
117
  template<class InputIterator, class RandomAccessIterator,
118
  class Compare>
119
  RandomAccessIterator
120
  partial_sort_copy(InputIterator first, InputIterator last,
121
  RandomAccessIterator result_first,
122
  RandomAccessIterator result_last,
123
  Compare comp);
124
+ template<class ExecutionPolicy, class ForwardIterator, class RandomAccessIterator,
125
+ class Compare>
126
+ RandomAccessIterator
127
+ partial_sort_copy(ExecutionPolicy&& exec,
128
+ ForwardIterator first, ForwardIterator last,
129
+ RandomAccessIterator result_first,
130
+ RandomAccessIterator result_last,
131
+ Compare comp);
132
  ```
133
 
134
+ *Requires:* `RandomAccessIterator` shall satisfy the requirements of
135
+ `ValueSwappable` ([[swappable.requirements]]). The type of
136
+ `*result_first` shall satisfy the requirements of `MoveConstructible`
137
+ (Table  [[tab:moveconstructible]]) and of `MoveAssignable`
138
+ (Table  [[tab:moveassignable]]).
139
+
140
  *Effects:* Places the first
141
  `min(last - first, result_last - result_first)` sorted elements into the
142
  range \[`result_first`,
143
  `result_first + min(last - first, result_last - result_first)`).
144
 
145
  *Returns:* The smaller of: `result_last` or
146
  `result_first + (last - first)`.
147
 
 
 
 
 
 
 
148
  *Complexity:* Approximately
149
  `(last - first) * log(min(last - first, result_last - result_first))`
150
  comparisons.
151
 
152
  #### `is_sorted` <a id="is.sorted">[[is.sorted]]</a>
 
156
  bool is_sorted(ForwardIterator first, ForwardIterator last);
157
  ```
158
 
159
  *Returns:* `is_sorted_until(first, last) == last`
160
 
161
+ ``` cpp
162
+ template<class ExecutionPolicy, class ForwardIterator>
163
+ bool is_sorted(ExecutionPolicy&& exec,
164
+ ForwardIterator first, ForwardIterator last);
165
+ ```
166
+
167
+ *Returns:*
168
+ `is_sorted_until(std::forward<ExecutionPolicy>(exec), first, last) == last`
169
+
170
  ``` cpp
171
  template<class ForwardIterator, class Compare>
172
  bool is_sorted(ForwardIterator first, ForwardIterator last,
173
  Compare comp);
174
  ```
175
 
176
  *Returns:* `is_sorted_until(first, last, comp) == last`
177
 
178
+ ``` cpp
179
+ template<class ExecutionPolicy, class ForwardIterator, class Compare>
180
+ bool is_sorted(ExecutionPolicy&& exec,
181
+ ForwardIterator first, ForwardIterator last,
182
+ Compare comp);
183
+ ```
184
+
185
+ *Returns:*
186
+
187
+ ``` cpp
188
+ is_sorted_until(std::forward<ExecutionPolicy>(exec), first, last, comp) == last
189
+ ```
190
+
191
  ``` cpp
192
  template<class ForwardIterator>
193
  ForwardIterator is_sorted_until(ForwardIterator first, ForwardIterator last);
194
+ template<class ExecutionPolicy, class ForwardIterator>
195
+ ForwardIterator is_sorted_until(ExecutionPolicy&& exec,
196
+ ForwardIterator first, ForwardIterator last);
197
+
198
  template<class ForwardIterator, class Compare>
199
  ForwardIterator is_sorted_until(ForwardIterator first, ForwardIterator last,
200
  Compare comp);
201
+ template<class ExecutionPolicy, class ForwardIterator, class Compare>
202
+ ForwardIterator is_sorted_until(ExecutionPolicy&& exec,
203
+ ForwardIterator first, ForwardIterator last,
204
+ Compare comp);
205
  ```
206
 
207
+ *Returns:* If `(last - first) < 2`, returns `last`. Otherwise, returns
208
+ the last iterator `i` in \[`first`, `last`\] for which the range
209
  \[`first`, `i`) is sorted.
210
 
211
  *Complexity:* Linear.
212