From Jason Turner

[alg.is.permutation]

C++20 → C++23 3.2 KB 31 lines
Current Draft | LaTeX Source
Archived: C++20 | C++23
Markdown: C++20 | C++23
Explore in Adventure Game

Diff to HTML by rtfpessoa

Files changed (1) hide show
  1. tmp/tmplfif1io8/{from.md → to.md} +14 -13
tmp/tmplfif1io8/{from.md → to.md} RENAMED
@@ -16,34 +16,32 @@ template<class ForwardIterator1, class ForwardIterator2,
16
  constexpr bool is_permutation(ForwardIterator1 first1, ForwardIterator1 last1,
17
  ForwardIterator2 first2, ForwardIterator2 last2,
18
  BinaryPredicate pred);
19
  ```
20
 
 
 
 
 
21
  *Mandates:* `ForwardIterator1` and `ForwardIterator2` have the same
22
  value type.
23
 
24
  *Preconditions:* The comparison function is an equivalence relation.
25
 
26
- *Remarks:* If `last2` was not given in the argument list, it denotes
27
- `first2 + (last1 - first1)` below.
28
-
29
  *Returns:* If `last1 - first1 != last2 - first2`, return `false`.
30
  Otherwise return `true` if there exists a permutation of the elements in
31
- the range \[`first2`, `first2 + (last1 - first1)`), beginning with
32
- `ForwardIterator2 begin`, such that `equal(first1, last1, begin)`
33
- returns `true` or `equal(first1, last1, begin, pred)` returns `true`;
34
- otherwise, returns `false`.
35
 
36
  *Complexity:* No applications of the corresponding predicate if
37
  `ForwardIterator1` and `ForwardIterator2` meet the requirements of
38
  random access iterators and `last1 - first1 != last2 - first2`.
39
  Otherwise, exactly `last1 - first1` applications of the corresponding
40
- predicate if `equal(first1, last1, first2, last2)` would return `true`
41
- if `pred` was not given in the argument list or
42
- `equal(first1, last1, first2, last2, pred)` would return `true` if
43
- `pred` was given in the argument list; otherwise, at worst 𝑂(N^2), where
44
- N has the value `last1 - first1`.
45
 
46
  ``` cpp
47
  template<forward_iterator I1, sentinel_for<I1> S1, forward_iterator I2,
48
  sentinel_for<I2> S2, class Proj1 = identity, class Proj2 = identity,
49
  indirect_equivalence_relation<projected<I1, Proj1>,
@@ -66,13 +64,16 @@ that `ranges::equal(first1, last1, pfirst, plast, pred, proj1, proj2)`
66
  returns `true`; otherwise, returns `false`.
67
 
68
  *Complexity:* No applications of the corresponding predicate and
69
  projections if:
70
 
 
71
  - `S1` and `I1` model `sized_sentinel_for<S1, I1>`,
72
  - `S2` and `I2` model `sized_sentinel_for<S2, I2>`, and
73
- - `last1 - first1 != last2 - first2`.
 
 
74
 
75
  Otherwise, exactly `last1 - first1` applications of the corresponding
76
  predicate and projections if
77
  `ranges::equal(first1, last1, first2, last2, pred, proj1, proj2)` would
78
  return `true`; otherwise, at worst 𝑂(N^2), where N has the value
 
16
  constexpr bool is_permutation(ForwardIterator1 first1, ForwardIterator1 last1,
17
  ForwardIterator2 first2, ForwardIterator2 last2,
18
  BinaryPredicate pred);
19
  ```
20
 
21
+ Let `last2` be `first2 + (last1 - first1)` for the overloads with no
22
+ parameter named `last2`, and let `pred` be `equal_to{}` for the
23
+ overloads with no parameter `pred`.
24
+
25
  *Mandates:* `ForwardIterator1` and `ForwardIterator2` have the same
26
  value type.
27
 
28
  *Preconditions:* The comparison function is an equivalence relation.
29
 
 
 
 
30
  *Returns:* If `last1 - first1 != last2 - first2`, return `false`.
31
  Otherwise return `true` if there exists a permutation of the elements in
32
+ the range \[`first2`, `last2`), beginning with `ForwardIterator2 begin`,
33
+ such that `equal(first1, last1, begin, pred)` returns `true`; otherwise,
34
+ returns `false`.
 
35
 
36
  *Complexity:* No applications of the corresponding predicate if
37
  `ForwardIterator1` and `ForwardIterator2` meet the requirements of
38
  random access iterators and `last1 - first1 != last2 - first2`.
39
  Otherwise, exactly `last1 - first1` applications of the corresponding
40
+ predicate if `equal(first1, last1, first2, last2, pred)` would return
41
+ `true`; otherwise, at worst 𝑂(N^2), where N has the value
42
+ `last1 - first1`.
 
 
43
 
44
  ``` cpp
45
  template<forward_iterator I1, sentinel_for<I1> S1, forward_iterator I2,
46
  sentinel_for<I2> S2, class Proj1 = identity, class Proj2 = identity,
47
  indirect_equivalence_relation<projected<I1, Proj1>,
 
64
  returns `true`; otherwise, returns `false`.
65
 
66
  *Complexity:* No applications of the corresponding predicate and
67
  projections if:
68
 
69
+ - for the first overload,
70
  - `S1` and `I1` model `sized_sentinel_for<S1, I1>`,
71
  - `S2` and `I2` model `sized_sentinel_for<S2, I2>`, and
72
+ - `last1 - first1 != last2 - first2`;
73
+ - for the second overload, `R1` and `R2` each model `sized_range`, and
74
+ `ranges::distance(r1) != ranges::distance(r2)`.
75
 
76
  Otherwise, exactly `last1 - first1` applications of the corresponding
77
  predicate and projections if
78
  `ranges::equal(first1, last1, first2, last2, pred, proj1, proj2)` would
79
  return `true`; otherwise, at worst 𝑂(N^2), where N has the value