std::ranges::lexicographical_compare
| ヘッダー <algorithm> で定義 |
||
| 呼び出しシグネチャ |
||
| template< std::input_iterator I1, std::sentinel_for<I1> S1, std::input_iterator I2, std::sentinel_for<I2> S2, |
(1) | (C++20以降) |
| template< ranges::input_range R1, ranges::input_range R2, class Proj1 = std::identity, class Proj2 = std::identity, |
(2) | (C++20以降) |
最初の範囲 [first1, last1) が、2番目の範囲 [first2, last2) よりも辞書順で 小さい かどうかをチェックします。
辞書順比較は、以下の特性を持つ操作です。
- 2つの範囲は要素ごとに比較されます。
- 最初に一致しない要素が、どちらの範囲が他方よりも辞書順で 小さい または 大きい かを定義します。
- 一方の範囲がもう一方の範囲のプレフィックスである場合、短い方の範囲が辞書順で 小さい とみなされます。
- 2つの範囲の要素が等しく、長さも同じ場合、その範囲は辞書順で 等しい とみなされます。
- 空の範囲は、任意の非空の範囲よりも辞書順で 小さい とみなされます。
- 2つの空の範囲は、辞書順で 等しい とみなされます。
このページで説明されている関数のようなエンティティは、アルゴリズム関数オブジェクト（非公式にはニーブロイドとして知られている）です。つまり、
- これらのいずれかを呼び出す際に、明示的なテンプレート引数リストを指定することはできません。
- これらのいずれも実引数依存の名前探索には見えません。
- これらのいずれかが関数呼び出し演算子の左側の名前として通常の非修飾名探索によって見つかった場合、実引数依存の名前探索は抑制されます。
目次 |
[編集] パラメーター
| first1, last1 | - | 調査対象の最初の 範囲 を定義するイテレーター-センチネルペア |
| r1 | - | 調査対象の最初の範囲 |
| first2, last2 | - | 調査対象の2番目の 範囲 を定義するイテレーター-センチネルペア |
| r2 | - | 調査対象の2番目の範囲 |
| comp | - | 射影された要素に適用する比較関数 |
| proj1 | - | 最初の範囲の要素に適用するプロジェクション |
| proj2 | - | 2番目の範囲の要素に適用するプロジェクション |
[編集] 戻り値
最初の範囲が2番目の範囲よりも辞書順で 小さい 場合、true
[編集] 計算量
比較および対応するプロジェクションの適用回数は、最大で 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つの要素の集合が同じかどうかを判断する (アルゴリズム関数オブジェクト) |
| ある範囲が別の範囲より辞書順で小さい場合に true を返す (関数テンプレート) |
