From Jason Turner

[alg.partitions]

C++14 → C++17 7.8 KB 115 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/tmpmrz2m56b/{from.md → to.md} +75 -36
tmp/tmpmrz2m56b/{from.md → to.md} RENAMED
@@ -1,81 +1,120 @@
1
  ### Partitions <a id="alg.partitions">[[alg.partitions]]</a>
2
 
3
  ``` cpp
4
  template <class InputIterator, class Predicate>
5
  bool is_partitioned(InputIterator first, InputIterator last, Predicate pred);
 
 
 
6
  ```
7
 
8
- *Requires:* `InputIterator`’s value type shall be convertible to
9
- `Predicate`’s argument type.
 
 
 
10
 
11
  *Returns:* `true` if \[`first`, `last`) is empty or if \[`first`,
12
  `last`) is partitioned by `pred`, i.e. if all elements that satisfy
13
  `pred` appear before those that do not.
14
 
15
  *Complexity:* Linear. At most `last - first` applications of `pred`.
16
 
17
  ``` cpp
18
  template<class ForwardIterator, class Predicate>
19
  ForwardIterator
20
- partition(ForwardIterator first,
21
- ForwardIterator last, Predicate pred);
 
 
 
22
  ```
23
 
24
- *Effects:* Places all the elements in the range \[`first`, `last`) that
25
- satisfy `pred` before all the elements that do not satisfy it.
26
-
27
- *Returns:* An iterator `i` such that for every iterator `j` in the range
28
- \[`first`, `i`) `pred(*j) != false`, and for every iterator `k` in the
29
- range \[`i`, `last`), `pred(*k) == false`.
30
-
31
  *Requires:* `ForwardIterator` shall satisfy the requirements of
32
  `ValueSwappable` ([[swappable.requirements]]).
33
 
34
- *Complexity:* If ForwardIterator meets the requirements for a
35
- BidirectionalIterator, at most `(last - first) / 2` swaps are done;
36
- otherwise at most `last - first` swaps are done. Exactly `last - first`
37
- applications of the predicate are done.
 
 
 
 
 
 
 
 
 
 
38
 
39
  ``` cpp
40
  template<class BidirectionalIterator, class Predicate>
41
  BidirectionalIterator
42
- stable_partition(BidirectionalIterator first,
43
- BidirectionalIterator last, Predicate pred);
 
 
 
 
 
44
  ```
45
 
46
- *Effects:* Places all the elements in the range \[`first`, `last`) that
47
- satisfy `pred` before all the elements that do not satisfy it.
48
-
49
- *Returns:* An iterator `i` such that for every iterator `j` in the range
50
- \[`first`, `i`), `pred(*j) != false`, and for every iterator `k` in the
51
- range \[`i`, `last`), `pred(*k) == false`. The relative order of the
52
- elements in both groups is preserved.
53
-
54
  *Requires:* `BidirectionalIterator` shall satisfy the requirements of
55
  `ValueSwappable` ([[swappable.requirements]]). The type of `*first`
56
  shall satisfy the requirements of `MoveConstructible`
57
- (Table  [[moveconstructible]]) and of `MoveAssignable`
58
- (Table  [[moveassignable]]).
59
 
60
- *Complexity:* At most `(last - first) * log(last - first)` swaps, but
61
- only linear number of swaps if there is enough extra memory. Exactly
62
- `last - first` applications of the predicate.
 
 
 
 
 
 
 
 
 
 
 
 
63
 
64
  ``` cpp
65
  template <class InputIterator, class OutputIterator1,
66
  class OutputIterator2, class Predicate>
67
  pair<OutputIterator1, OutputIterator2>
68
  partition_copy(InputIterator first, InputIterator last,
69
  OutputIterator1 out_true, OutputIterator2 out_false,
70
  Predicate pred);
 
 
 
 
 
 
 
71
  ```
72
 
73
- *Requires:* `InputIterator`’s value type shall be `CopyAssignable`, and
74
- shall be writable to the `out_true` and `out_false` `OutputIterator`s,
75
- and shall be convertible to `Predicate`’s argument type. The input range
76
- shall not overlap with either of the output ranges.
 
 
 
 
 
 
 
 
 
 
 
77
 
78
  *Effects:* For each iterator `i` in \[`first`, `last`), copies `*i` to
79
  the output range beginning with `out_true` if `pred(*i)` is `true`, or
80
  to the output range beginning with `out_false` otherwise.
81
 
@@ -96,9 +135,9 @@ template<class ForwardIterator, class Predicate>
96
  `Predicate`’s argument type. \[`first`, `last`) shall be partitioned by
97
  `pred`, i.e. all elements that satisfy `pred` shall appear before those
98
  that do not.
99
 
100
  *Returns:* An iterator `mid` such that `all_of(first, mid, pred)` and
101
- `none_of(mid, last, pred)` are both true.
102
 
103
- *Complexity:* 𝑂(log(last - first)) applications of `pred`.
104
 
 
1
  ### Partitions <a id="alg.partitions">[[alg.partitions]]</a>
2
 
3
  ``` cpp
4
  template <class InputIterator, class Predicate>
5
  bool is_partitioned(InputIterator first, InputIterator last, Predicate pred);
6
+ template <class ExecutionPolicy, class ForwardIterator, class Predicate>
7
+ bool is_partitioned(ExecutionPolicy&& exec,
8
+ ForwardIterator first, ForwardIterator last, Predicate pred);
9
  ```
10
 
11
+ *Requires:* For the overload with no `ExecutionPolicy`,
12
+ `InputIterator`’s value type shall be convertible to `Predicate`’s
13
+ argument type. For the overload with an `ExecutionPolicy`,
14
+ `ForwardIterator`’s value type shall be convertible to `Predicate`’s
15
+ argument type.
16
 
17
  *Returns:* `true` if \[`first`, `last`) is empty or if \[`first`,
18
  `last`) is partitioned by `pred`, i.e. if all elements that satisfy
19
  `pred` appear before those that do not.
20
 
21
  *Complexity:* Linear. At most `last - first` applications of `pred`.
22
 
23
  ``` cpp
24
  template<class ForwardIterator, class Predicate>
25
  ForwardIterator
26
+ partition(ForwardIterator first, ForwardIterator last, Predicate pred);
27
+ template<class ExecutionPolicy, class ForwardIterator, class Predicate>
28
+ ForwardIterator
29
+ partition(ExecutionPolicy&& exec,
30
+ ForwardIterator first, ForwardIterator last, Predicate pred);
31
  ```
32
 
 
 
 
 
 
 
 
33
  *Requires:* `ForwardIterator` shall satisfy the requirements of
34
  `ValueSwappable` ([[swappable.requirements]]).
35
 
36
+ *Effects:* Places all the elements in the range \[`first`, `last`) that
37
+ satisfy `pred` before all the elements that do not satisfy it.
38
+
39
+ *Returns:* An iterator `i` such that for every iterator `j` in the range
40
+ \[`first`, `i`) `pred(*j) != false`, and for every iterator `k` in the
41
+ range \[`i`, `last`), `pred(*k) == false`.
42
+
43
+ *Complexity:* Let N = `last - first`:
44
+
45
+ - For the overload with no `ExecutionPolicy`, exactly N applications of
46
+ the predicate. At most N / 2 swaps if `ForwardIterator` meets the
47
+ `BidirectionalIterator` requirements and at most N swaps otherwise.
48
+ - For the overload with an `ExecutionPolicy`, 𝑂(N log N) swaps and 𝑂(N)
49
+ applications of the predicate.
50
 
51
  ``` cpp
52
  template<class BidirectionalIterator, class Predicate>
53
  BidirectionalIterator
54
+ stable_partition(BidirectionalIterator first, BidirectionalIterator last,
55
+ Predicate pred);
56
+ template<class ExecutionPolicy, class BidirectionalIterator, class Predicate>
57
+ BidirectionalIterator
58
+ stable_partition(ExecutionPolicy&& exec,
59
+ BidirectionalIterator first, BidirectionalIterator last,
60
+ Predicate pred);
61
  ```
62
 
 
 
 
 
 
 
 
 
63
  *Requires:* `BidirectionalIterator` shall satisfy the requirements of
64
  `ValueSwappable` ([[swappable.requirements]]). The type of `*first`
65
  shall satisfy the requirements of `MoveConstructible`
66
+ (Table  [[tab:moveconstructible]]) and of `MoveAssignable`
67
+ (Table  [[tab:moveassignable]]).
68
 
69
+ *Effects:* Places all the elements in the range \[`first`, `last`) that
70
+ satisfy `pred` before all the elements that do not satisfy it.
71
+
72
+ *Returns:* An iterator `i` such that for every iterator `j` in the range
73
+ \[`first`, `i`), `pred(*j) != false`, and for every iterator `k` in the
74
+ range \[`i`, `last`), `pred(*k) == false`. The relative order of the
75
+ elements in both groups is preserved.
76
+
77
+ *Complexity:* Let N = `last - first`:
78
+
79
+ - For the overload with no `ExecutionPolicy`, at most N log N swaps, but
80
+ only 𝑂(N) swaps if there is enough extra memory. Exactly N
81
+ applications of the predicate.
82
+ - For the overload with an `ExecutionPolicy`, 𝑂(N log N) swaps and 𝑂(N)
83
+ applications of the predicate.
84
 
85
  ``` cpp
86
  template <class InputIterator, class OutputIterator1,
87
  class OutputIterator2, class Predicate>
88
  pair<OutputIterator1, OutputIterator2>
89
  partition_copy(InputIterator first, InputIterator last,
90
  OutputIterator1 out_true, OutputIterator2 out_false,
91
  Predicate pred);
92
+ template <class ExecutionPolicy, class ForwardIterator, class ForwardIterator1,
93
+ class ForwardIterator2, class Predicate>
94
+ pair<ForwardIterator1, ForwardIterator2>
95
+ partition_copy(ExecutionPolicy&& exec,
96
+ ForwardIterator first, ForwardIterator last,
97
+ ForwardIterator1 out_true, ForwardIterator2 out_false,
98
+ Predicate pred);
99
  ```
100
 
101
+ *Requires:*
102
+
103
+ - For the overload with no `ExecutionPolicy`, `InputIterator`’s value
104
+ type shall be `CopyAssignable` (Table  [[tab:copyassignable]]), and
105
+ shall be writable ([[iterator.requirements.general]]) to the
106
+ `out_true` and `out_false` `OutputIterator`s, and shall be convertible
107
+ to `Predicate`’s argument type.
108
+ - For the overload with an `ExecutionPolicy`, `ForwardIterator`’s value
109
+ type shall be `CopyAssignable`, and shall be writable to the
110
+ `out_true` and `out_false` `ForwardIterator`s, and shall be
111
+ convertible to `Predicate`’s argument type. \[*Note 1*: There may be a
112
+ performance cost if `ForwardIterator`’s value type is not
113
+ `CopyConstructible`. — *end note*]
114
+ - For both overloads, the input range shall not overlap with either of
115
+ the output ranges.
116
 
117
  *Effects:* For each iterator `i` in \[`first`, `last`), copies `*i` to
118
  the output range beginning with `out_true` if `pred(*i)` is `true`, or
119
  to the output range beginning with `out_false` otherwise.
120
 
 
135
  `Predicate`’s argument type. \[`first`, `last`) shall be partitioned by
136
  `pred`, i.e. all elements that satisfy `pred` shall appear before those
137
  that do not.
138
 
139
  *Returns:* An iterator `mid` such that `all_of(first, mid, pred)` and
140
+ `none_of(mid, last, pred)` are both `true`.
141
 
142
+ *Complexity:* 𝑂(log(`last - first`)) applications of `pred`.
143