tmp/tmph42tt6bm/{from.md → to.md}
RENAMED
|
@@ -0,0 +1,80 @@
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
| 1 |
+
### Is permutation <a id="alg.is.permutation">[[alg.is.permutation]]</a>
|
| 2 |
+
|
| 3 |
+
``` cpp
|
| 4 |
+
template<class ForwardIterator1, class ForwardIterator2>
|
| 5 |
+
constexpr bool is_permutation(ForwardIterator1 first1, ForwardIterator1 last1,
|
| 6 |
+
ForwardIterator2 first2);
|
| 7 |
+
template<class ForwardIterator1, class ForwardIterator2,
|
| 8 |
+
class BinaryPredicate>
|
| 9 |
+
constexpr bool is_permutation(ForwardIterator1 first1, ForwardIterator1 last1,
|
| 10 |
+
ForwardIterator2 first2, BinaryPredicate pred);
|
| 11 |
+
template<class ForwardIterator1, class ForwardIterator2>
|
| 12 |
+
constexpr bool is_permutation(ForwardIterator1 first1, ForwardIterator1 last1,
|
| 13 |
+
ForwardIterator2 first2, ForwardIterator2 last2);
|
| 14 |
+
template<class ForwardIterator1, class ForwardIterator2,
|
| 15 |
+
class BinaryPredicate>
|
| 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>,
|
| 50 |
+
projected<I2, Proj2>> Pred = ranges::equal_to>
|
| 51 |
+
constexpr bool ranges::is_permutation(I1 first1, S1 last1, I2 first2, S2 last2,
|
| 52 |
+
Pred pred = {},
|
| 53 |
+
Proj1 proj1 = {}, Proj2 proj2 = {});
|
| 54 |
+
template<forward_range R1, forward_range R2,
|
| 55 |
+
class Proj1 = identity, class Proj2 = identity,
|
| 56 |
+
indirect_equivalence_relation<projected<iterator_t<R1>, Proj1>,
|
| 57 |
+
projected<iterator_t<R2>, Proj2>> Pred = ranges::equal_to>
|
| 58 |
+
constexpr bool ranges::is_permutation(R1&& r1, R2&& r2, Pred pred = {},
|
| 59 |
+
Proj1 proj1 = {}, Proj2 proj2 = {});
|
| 60 |
+
```
|
| 61 |
+
|
| 62 |
+
*Returns:* If `last1 - first1 != last2 - first2`, return `false`.
|
| 63 |
+
Otherwise return `true` if there exists a permutation of the elements in
|
| 64 |
+
the range \[`first2`, `last2`), bounded by \[`pfirst`, `plast`), such
|
| 65 |
+
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
|
| 79 |
+
`last1 - first1`.
|
| 80 |
+
|