namespace std::ranges {
template<forward_iterator I1, sentinel_for<I1> S1, forward_iterator I2, sentinel_for<I2> S2, class Proj1 = identity, class Proj2 = identity,
indirect_equivalence_relation<projected<I1, Proj1>, projected<I2, Proj2>> Pred = ranges::equal_to>
constexpr bool is_permutation(I1 first1, S1 last1, I2 first2, S2 last2, Pred pred = {}, Proj1 proj1 = {}, Proj2 proj2 = {}); // (1)
template<forward_range R1, forward_range R2, class Proj1 = identity, class Proj2 = identity,
indirect_equivalence_relation<projected<iterator_t<R1>, Proj1>, projected<iterator_t<R2>, Proj2>> Pred = ranges::equal_to>
constexpr bool is_permutation(R1&& r1, R2&& r2, Pred pred = {}, Proj1 proj1 = {}, Proj2 proj2 = {}); // (2)
}
概要
範囲 [first2, last2)
を並べ替えたものが、[first1, last1)
の範囲と一致するか判定する。
- (1): イテレータペアで範囲を指定する
- (2): 範囲を直接指定する
戻り値
last2
が与えられている形式の場合、last1 - first1 != last2 - first2
であれば false
を返す。
そうでなければ、[first1, last1)
の範囲と [first2, first2 + (last1 - first1))
の範囲を並び変えたもので、equal(first1, last1, first2)
、あるいは equal(first1, last1, first2, pred)
が true
を返すようなものがあれば true
を、そうでなければ false
を返す。
なお、実際に並べ替えが行われるわけではない。
計算量
last2
が与えられている形式の場合、I1
と I2
がどちらもrandom_access_iterator
のモデルであり、かつ last1 - first1 != last2 - first2
であれば 1 度も述語の適用を行わない。
そうでなければ、equal(first1, last1, first2, last2) == true
もしくは equal(first1, last1, first2, last2, pred) == true
の場合(last2
が無い形式の場合、equal
も last2
の無い形式で置き換える)、distance(first1, last1)
回の述語適用で完了する。
そうでなければ、distance(first1, last1)
をNとした場合に最悪O(N^2)回の述語適用で完了する。
例
#include <iostream>
#include <vector>
#include <algorithm>
int main ()
{
std::vector<int> v = {1, 2, 3};
std::vector<int> good = {2, 3, 1};
std::vector<int> bad = {2, 3, 4};
std::cout << std::boolalpha;
std::cout << std::ranges::is_permutation(v, good) << std::endl;
std::cout << std::ranges::is_permutation(v, bad) << std::endl;
}
出力
true
false
バージョン
言語
- C++20
処理系
- Clang: ??
- GCC: 10.1.0
- ICC: ??
- Visual C++: 2019 Update 10