From Jason Turner

[alg.unique]

C++17 → C++20 8.0 KB 116 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/tmp9pze7s94/{from.md → to.md} +82 -31
tmp/tmp9pze7s94/{from.md → to.md} RENAMED
@@ -1,84 +1,135 @@
1
  ### Unique <a id="alg.unique">[[alg.unique]]</a>
2
 
3
  ``` cpp
4
  template<class ForwardIterator>
5
- ForwardIterator unique(ForwardIterator first, ForwardIterator last);
6
  template<class ExecutionPolicy, class ForwardIterator>
7
  ForwardIterator unique(ExecutionPolicy&& exec,
8
  ForwardIterator first, ForwardIterator last);
9
 
10
  template<class ForwardIterator, class BinaryPredicate>
11
- ForwardIterator unique(ForwardIterator first, ForwardIterator last,
12
  BinaryPredicate pred);
13
  template<class ExecutionPolicy, class ForwardIterator, class BinaryPredicate>
14
  ForwardIterator unique(ExecutionPolicy&& exec,
15
  ForwardIterator first, ForwardIterator last,
16
  BinaryPredicate pred);
 
 
 
 
 
 
 
 
 
17
  ```
18
 
19
- *Requires:* The comparison function shall be an equivalence relation.
20
- The type of `*first` shall satisfy the `MoveAssignable` requirements
21
- (Table  [[tab:moveassignable]]).
 
 
 
 
 
 
 
22
 
23
  *Effects:* For a nonempty range, eliminates all but the first element
24
  from every consecutive group of equivalent elements referred to by the
25
- iterator `i` in the range \[`first + 1`, `last`) for which the following
26
- conditions hold: `*(i - 1) == *i` or `pred(*(i - 1), *i) != false`.
27
 
28
- *Returns:* The end of the resulting range.
 
 
 
29
 
30
  *Complexity:* For nonempty ranges, exactly `(last - first) - 1`
31
- applications of the corresponding predicate.
 
32
 
33
  ``` cpp
34
  template<class InputIterator, class OutputIterator>
35
- OutputIterator
36
  unique_copy(InputIterator first, InputIterator last,
37
  OutputIterator result);
38
  template<class ExecutionPolicy, class ForwardIterator1, class ForwardIterator2>
39
  ForwardIterator2
40
  unique_copy(ExecutionPolicy&& exec,
41
  ForwardIterator1 first, ForwardIterator1 last,
42
  ForwardIterator2 result);
43
 
44
  template<class InputIterator, class OutputIterator,
45
  class BinaryPredicate>
46
- OutputIterator
47
  unique_copy(InputIterator first, InputIterator last,
48
  OutputIterator result, BinaryPredicate pred);
49
  template<class ExecutionPolicy, class ForwardIterator1, class ForwardIterator2,
50
  class BinaryPredicate>
51
  ForwardIterator2
52
  unique_copy(ExecutionPolicy&& exec,
53
  ForwardIterator1 first, ForwardIterator1 last,
54
  ForwardIterator2 result, BinaryPredicate pred);
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
55
  ```
56
 
57
- *Requires:*
 
 
 
 
 
 
 
 
 
 
58
 
59
- - The comparison function shall be an equivalence relation.
60
  - The ranges \[`first`, `last`) and \[`result`, `result+(last-first)`)
61
- shall not overlap.
62
- - The expression `*result = *first` shall be valid.
63
- - For the overloads with no `ExecutionPolicy`, let `T` be the value type
64
- of `InputIterator`. If `InputIterator` meets the forward iterator
65
- requirements, then there are no additional requirements for `T`.
66
- Otherwise, if `OutputIterator` meets the forward iterator requirements
67
- and its value type is the same as `T`, then `T` shall be
68
- `CopyAssignable` (Table  [[tab:copyassignable]]). Otherwise, `T` shall
69
- be both `CopyConstructible` (Table  [[tab:copyconstructible]]) and
70
- `CopyAssignable`. \[*Note 1*: For the overloads with an
71
- `ExecutionPolicy`, there may be a performance cost if the value type
72
- of `ForwardIterator1` is not both `CopyConstructible` and
73
- `CopyAssignable`. — *end note*]
 
 
 
74
 
75
  *Effects:* Copies only the first element from every consecutive group of
76
  equal elements referred to by the iterator `i` in the range \[`first`,
77
- `last`) for which the following corresponding conditions hold:
78
- `*i == *(i - 1)` or `pred(*i, *(i - 1)) != false`.
79
 
80
- *Returns:* The end of the resulting range.
81
 
82
- *Complexity:* For nonempty ranges, exactly `last - first - 1`
83
- applications of the corresponding predicate.
 
 
 
 
84
 
 
1
  ### Unique <a id="alg.unique">[[alg.unique]]</a>
2
 
3
  ``` cpp
4
  template<class ForwardIterator>
5
+ constexpr ForwardIterator unique(ForwardIterator first, ForwardIterator last);
6
  template<class ExecutionPolicy, class ForwardIterator>
7
  ForwardIterator unique(ExecutionPolicy&& exec,
8
  ForwardIterator first, ForwardIterator last);
9
 
10
  template<class ForwardIterator, class BinaryPredicate>
11
+ constexpr ForwardIterator unique(ForwardIterator first, ForwardIterator last,
12
  BinaryPredicate pred);
13
  template<class ExecutionPolicy, class ForwardIterator, class BinaryPredicate>
14
  ForwardIterator unique(ExecutionPolicy&& exec,
15
  ForwardIterator first, ForwardIterator last,
16
  BinaryPredicate pred);
17
+
18
+ template<permutable I, sentinel_for<I> S, class Proj = identity,
19
+ indirect_equivalence_relation<projected<I, Proj>> C = ranges::equal_to>
20
+ constexpr subrange<I> ranges::unique(I first, S last, C comp = {}, Proj proj = {});
21
+ template<forward_range R, class Proj = identity,
22
+ indirect_equivalence_relation<projected<iterator_t<R>, Proj>> C = ranges::equal_to>
23
+ requires permutable<iterator_t<R>>
24
+ constexpr borrowed_subrange_t<R>
25
+ ranges::unique(R&& r, C comp = {}, Proj proj = {});
26
  ```
27
 
28
+ Let `pred` be `equal_to{}` for the overloads with no parameter `pred`,
29
+ and let E be
30
+
31
+ - `bool(pred(*(i - 1), *i))` for the overloads in namespace `std`;
32
+ - `bool(invoke(comp, invoke(proj, *(i - 1)), invoke(proj, *i)))` for the
33
+ overloads in namespace `ranges`.
34
+
35
+ *Preconditions:* For the overloads in namepace `std`, `pred` is an
36
+ equivalence relation and the type of `*first` meets the
37
+ *Cpp17MoveAssignable* requirements ([[cpp17.moveassignable]]).
38
 
39
  *Effects:* For a nonempty range, eliminates all but the first element
40
  from every consecutive group of equivalent elements referred to by the
41
+ iterator `i` in the range \[`first + 1`, `last`) for which E is `true`.
 
42
 
43
+ *Returns:* Let j be the end of the resulting range. Returns:
44
+
45
+ - j for the overloads in namespace `std`.
46
+ - `{`j`, last}` for the overloads in namespace `ranges`.
47
 
48
  *Complexity:* For nonempty ranges, exactly `(last - first) - 1`
49
+ applications of the corresponding predicate and no more than twice as
50
+ many applications of any projection.
51
 
52
  ``` cpp
53
  template<class InputIterator, class OutputIterator>
54
+ constexpr OutputIterator
55
  unique_copy(InputIterator first, InputIterator last,
56
  OutputIterator result);
57
  template<class ExecutionPolicy, class ForwardIterator1, class ForwardIterator2>
58
  ForwardIterator2
59
  unique_copy(ExecutionPolicy&& exec,
60
  ForwardIterator1 first, ForwardIterator1 last,
61
  ForwardIterator2 result);
62
 
63
  template<class InputIterator, class OutputIterator,
64
  class BinaryPredicate>
65
+ constexpr OutputIterator
66
  unique_copy(InputIterator first, InputIterator last,
67
  OutputIterator result, BinaryPredicate pred);
68
  template<class ExecutionPolicy, class ForwardIterator1, class ForwardIterator2,
69
  class BinaryPredicate>
70
  ForwardIterator2
71
  unique_copy(ExecutionPolicy&& exec,
72
  ForwardIterator1 first, ForwardIterator1 last,
73
  ForwardIterator2 result, BinaryPredicate pred);
74
+
75
+ template<input_iterator I, sentinel_for<I> S, weakly_incrementable O, class Proj = identity,
76
+ indirect_equivalence_relation<projected<I, Proj>> C = ranges::equal_to>
77
+ requires indirectly_copyable<I, O> &&
78
+ (forward_iterator<I> ||
79
+ (input_iterator<O> && same_as<iter_value_t<I>, iter_value_t<O>>) ||
80
+ indirectly_copyable_storable<I, O>)
81
+ constexpr ranges::unique_copy_result<I, O>
82
+ ranges::unique_copy(I first, S last, O result, C comp = {}, Proj proj = {});
83
+ template<input_range R, weakly_incrementable O, class Proj = identity,
84
+ indirect_equivalence_relation<projected<iterator_t<R>, Proj>> C = ranges::equal_to>
85
+ requires indirectly_copyable<iterator_t<R>, O> &&
86
+ (forward_iterator<iterator_t<R>> ||
87
+ (input_iterator<O> && same_as<range_value_t<R>, iter_value_t<O>>) ||
88
+ indirectly_copyable_storable<iterator_t<R>, O>)
89
+ constexpr ranges::unique_copy_result<borrowed_iterator_t<R>, O>
90
+ ranges::unique_copy(R&& r, O result, C comp = {}, Proj proj = {});
91
  ```
92
 
93
+ Let `pred` be `equal_to{}` for the overloads in namespace `std` with no
94
+ parameter `pred`, and let E be
95
+
96
+ - `bool(pred(*i, *(i - 1)))` for the overloads in namespace `std`;
97
+ - `bool(invoke(comp, invoke(proj, *i), invoke(proj, *(i - 1))))` for the
98
+ overloads in namespace `ranges`.
99
+
100
+ *Mandates:* `*first` is writable [[iterator.requirements.general]] to
101
+ `result`.
102
+
103
+ *Preconditions:*
104
 
 
105
  - The ranges \[`first`, `last`) and \[`result`, `result+(last-first)`)
106
+ do not overlap.
107
+ - For the overloads in namespace `std`:
108
+ - The comparison function is an equivalence relation.
109
+ - For the overloads with no `ExecutionPolicy`, let `T` be the value
110
+ type of `InputIterator`. If `InputIterator` meets the
111
+ *Cpp17ForwardIterator* requirements, then there are no additional
112
+ requirements for `T`. Otherwise, if `OutputIterator` meets the
113
+ *Cpp17ForwardIterator* requirements and its value type is the same
114
+ as `T`, then `T` meets the *Cpp17CopyAssignable*
115
+ ([[cpp17.copyassignable]]) requirements. Otherwise, `T` meets both
116
+ the *Cpp17CopyConstructible* ([[cpp17.copyconstructible]]) and
117
+ *Cpp17CopyAssignable* requirements. \[*Note 1*: For the overloads
118
+ with an `ExecutionPolicy`, there may be a performance cost if the
119
+ value type of `ForwardIterator1` does not meet both the
120
+ *Cpp17CopyConstructible* and *Cpp17CopyAssignable*
121
+ requirements. — *end note*]
122
 
123
  *Effects:* Copies only the first element from every consecutive group of
124
  equal elements referred to by the iterator `i` in the range \[`first`,
125
+ `last`) for which E holds.
 
126
 
127
+ *Returns:*
128
 
129
+ - `result + `N for the overloads in namespace `std`.
130
+ - `{last, result + `N`}` for the overloads in namespace `ranges`.
131
+
132
+ *Complexity:* Exactly `last - first - 1` applications of the
133
+ corresponding predicate and no more than twice as many applications of
134
+ any projection.
135