std::ranges::lexicographical_compare
ja.cppreference.net より
| (C++23) <algorithm>
|
||
| ヘッダ |
||
template< std::input_iterator I1, std::sentinel_for<I1> S1,
std::input_iterator I2, std::sentinel_for<I2> S2,
class Proj1 = std::identity, class Proj2 = std::identity,
std::indirect_strict_weak_order<
std::projected<I1, Proj1>,
std::projected<I2, Proj2>> Comp = ranges::less >
constexpr bool
lexicographical_compare( I1 first1, S1 last1, I2 first2, S2 last2,
Comp comp = {}, Proj1 proj1 = {}, Proj2 proj2 = {} );
|
で定義されています | 呼び出しシグネチャ |
template< ranges::input_range R1, ranges::input_range R2,
class Proj1 = std::identity, class Proj2 = std::identity,
std::indirect_strict_weak_order<
std::projected<ranges::iterator_t<R1>, Proj1>,
std::projected<ranges::iterator_t<R2>, Proj2>> Comp = ranges::less >
constexpr bool
lexicographical_compare( R1&& r1, R2&& r2, Comp comp = {},
Proj1 proj1 = {}, Proj2 proj2 = {} );
|
(1) | (C++20 以降) |
(2) [first1, last1)(C++20 以降)最初の範囲 が 2 番目の範囲 [first2, last2) よりも
辞書順で小さい
compかどうかを調べます。
1) 要素は指定された二項比較関数 を用いて比較されます。2)
r (1) と同じですが、ranges::begin(r) をソース範囲として使用します。これは first を ranges::end(r) として、last を として使用するのと同じです。
- 辞書順比較は、以下の特性を持つ操作です：
- 2 つの範囲が要素ごとに比較されます。最初に不一致となった要素によって、どちらの範囲が他方より辞書順で小さいか大きい
- かが決まります。一方の範囲が他方の接頭辞である場合、短い範囲が他方より辞書順で小さい
- とみなされます。2 つの範囲が同等の要素を持ち、かつ長さが等しい場合、それらの範囲は辞書順で等しい
- とみなされます。空の範囲は、空でない範囲より辞書順で小さい
- とみなされます。2 つの空の範囲は辞書順で等しい
とみなされます。このページで説明されている関数に類似したエンティティはアルゴリズム関数オブジェクト (非公式にはniebloids
- として知られています) であり、つまり次のような特徴があります：
- これらを呼び出す際に明示的なテンプレート引数リストを指定することはできません。これらは引数依存の名前探索
- には表示されません。通常の非修飾名前探索によって関数呼び出し演算子の左側の名前として見つかった場合、引数依存の名前探索は抑制されます。
パラメータ
| first1, last1 | - | 検査対象の最初の要素範囲を定義する 範囲 を表すイテレータ-番兵ペア |
| r1 | - | 検査対象の最初の要素範囲 |
| first2, last2 | - | 検査対象の2番目の要素範囲を定義する 範囲 を表すイテレータ-番兵ペア |
| r2 | - | 検査対象の2番目の要素範囲 |
| comp | - | 投影された要素に適用する比較関数 |
| proj1 | - | 最初の要素範囲に適用する投影 |
| proj2 | - | 2番目の要素範囲に適用する投影 |
戻り値
true 最初の範囲が2番目の範囲より辞書順で 小さい 場合。
計算量
最大で 2·min(N1, N2) 回の比較および対応する射影の適用。ここで N1 = ranges:: distance ( first1, last1 ) および N2 = ranges:: distance ( first2, last2 ) である。
実装例
struct lexicographical_compare_fn { template<std::input_iterator I1, std::sentinel_for<I1> S1, std::input_iterator I2, std::sentinel_for<I2> S2, class Proj1 = std::identity, class Proj2 = std::identity, std::indirect_strict_weak_order< std::projected<I1, Proj1>, std::projected<I2, Proj2>> Comp = ranges::less> constexpr bool operator()(I1 first1, S1 last1, I2 first2, S2 last2, Comp comp = {}, Proj1 proj1 = {}, Proj2 proj2 = {}) const { for (; (first1 != last1) && (first2 != last2); ++first1, (void) ++first2) { if (std::invoke(comp, std::invoke(proj1, *first1), std::invoke(proj2, *first2))) return true; if (std::invoke(comp, std::invoke(proj2, *first2), std::invoke(proj1, *first1))) return false; } return (first1 == last1) && (first2 != last2); } template<ranges::input_range R1, ranges::input_range R2, class Proj1 = std::identity, class Proj2 = std::identity, std::indirect_strict_weak_order< std::projected<ranges::iterator_t<R1>, Proj1>, std::projected<ranges::iterator_t<R2>, Proj2>> Comp = ranges::less> constexpr bool operator()(R1&& r1, R2&& r2, Comp comp = {}, Proj1 proj1 = {}, Proj2 proj2 = {}) const { return (*this)(ranges::begin(r1), ranges::end(r1), ranges::begin(r2), ranges::end(r2), std::ref(comp), std::ref(proj1), std::ref(proj2)); } }; inline constexpr lexicographical_compare_fn lexicographical_compare; |
例
このコードを実行
#include <algorithm> #include <iostream> #include <iterator> #include <random> #include <vector> int main() { std::vector<char> v1 {'a', 'b', 'c', 'd'}; std::vector<char> v2 {'a', 'b', 'c', 'd'}; namespace ranges = std::ranges; auto os = std::ostream_iterator<char>(std::cout, " "); std::mt19937 g {std::random_device {}()}; while (not ranges::lexicographical_compare(v1, v2)) { ranges::copy(v1, os); std::cout << ">= "; ranges::copy(v2, os); std::cout << '\n'; ranges::shuffle(v1, g); ranges::shuffle(v2, g); } ranges::copy(v1, os); std::cout << "< "; ranges::copy(v2, os); std::cout << '\n'; }
出力例:
a b c d >= a b c d d a b c >= c b d a b d a c >= a d c b a c d b < c d a b
関連項目
(C++20) |
2つの要素の集合が同一かどうかを判定する (アルゴリズム関数オブジェクト) |
| 2つの範囲を辞書順で比較する (関数テンプレート) |