std::lexicographical_compare
ja.cppreference.net より
| ヘッダ <algorithm>
|
||
template< class InputIt1, class InputIt2 >
bool lexicographical_compare( InputIt1 first1, InputIt1 last1,
InputIt2 first2, InputIt2 last2 );
|
で定義 (1) | (C++20 から constexpr) |
template< class ExecutionPolicy,
class ForwardIt1, class ForwardIt2 >
bool lexicographical_compare( ExecutionPolicy&& policy,
ForwardIt1 first1, ForwardIt1 last1,
ForwardIt2 first2, ForwardIt2 last2 );
|
(2) | (C++17 から) |
template< class InputIt1, class InputIt2, class Compare >
bool lexicographical_compare( InputIt1 first1, InputIt1 last1,
InputIt2 first2, InputIt2 last2,
Compare comp );
|
(3) | (C++20 から constexpr) |
template< class ExecutionPolicy,
class ForwardIt1, class ForwardIt2, class Compare >
bool lexicographical_compare( ExecutionPolicy&& policy,
ForwardIt1 first1, ForwardIt1 last1,
ForwardIt2 first2, ForwardIt2 last2,
Compare comp );
|
(4) | (C++17 から) |
第1範囲 [first1, last1) が第2範囲 より辞書的に 小さい[first2, last2) かどうかをチェックする。
1) 要素は
operator< を用いて比較される。3) 要素は与えられた二項比較関数
comp を用いて比較される。2,4) (1,3) と同じだが、
policy に従って実行される。これらのオーバーロードは、以下の式の値が true である場合にのみオーバーロード解決に参加する:
|
|
(C++20 まで) |
|
|
(C++20 から) |
辞書比較は以下の特性を持つ操作である:
- 2つの範囲が要素ごとに比較される。
- 最初に不一致となる要素が、どちらの範囲が辞書的に 小さい か 大きい かを定義する。
- 一方の範囲が他方のプレフィックスである場合、短い方が辞書的に 小さい とされる。
- 2つの範囲が等価な要素を持ち、同じ長さである場合、それらの範囲は辞書的に 等しい。
- 空の範囲は、空でない任意の範囲より辞書的に 小さい。
- 2つの空の範囲は辞書的に 等しい。
引数
| first1, last1 | - | 調査する最初の要素の 範囲 を定義するイテレータのペア |
| first2, last2 | - | 調査する2番目の要素の 範囲 を定義するイテレータのペア |
| policy | - | 使用する 実行ポリシー |
| comp | - | 比較関数オブジェクト (すなわち Compare の要件を満たすオブジェクト)。第1引数が第2引数より true 小さい場合に を返す。比較関数のシグネチャは以下と等価であるべき:
シグネチャに |
| 型要件 | ||
-InputIt1, InputIt2 は LegacyInputIterator の要件を満たさなければならない。
| ||
-ForwardIt1, ForwardIt2 は LegacyForwardIterator の要件を満たさなければならない。
| ||
-Compare は Compare の要件を満たさなければならない。
| ||
戻り値
true最初の範囲が 2 番目の範囲より辞書的に 小さい 場合は false、そうでない場合は
。
計算量N1 を std::distance(first1, last1) とし、N2 を std::distance(first2, last2) とする:
1,2) 最大で 2min(1,N2) 回の
operator< による比較。3,4) 最大で 2min(N1,N2) 回の比較関数
comp の適用。例外
テンプレートパラメータ ExecutionPolicy を持つオーバーロードは以下のようにエラーを報告する:
- アルゴリズムの一部として呼び出された関数が例外をスローし、
ExecutionPolicyが 標準ポリシー のいずれかである場合、std::terminate が呼び出される。他のExecutionPolicyについては、動作は実装定義である。 - アルゴリズムがメモリの確保に失敗した場合、std::bad_alloc がスローされる。
実装例
| lexicographical_compare (1) |
|---|
template<class InputIt1, class InputIt2>
bool lexicographical_compare(InputIt1 first1, InputIt1 last1,
InputIt2 first2, InputIt2 last2)
{
for (; (first1 != last1) && (first2 != last2); ++first1, (void) ++first2)
{
if (*first1 < *first2)
return true;
if (*first2 < *first1)
return false;
}
return (first1 == last1) && (first2 != last2);
}
|
| lexicographical_compare (3) |
template<class InputIt1, class InputIt2, class Compare>
bool lexicographical_compare(InputIt1 first1, InputIt1 last1,
InputIt2 first2, InputIt2 last2, Compare comp)
{
for (; (first1 != last1) && (first2 != last2); ++first1, (void) ++first2)
{
if (comp(*first1, *first2))
return true;
if (comp(*first2, *first1))
return false;
}
return (first1 == last1) && (first2 != last2);
}
|
例
このコードを実行
#include <algorithm>
#include <iostream>
#include <random>
#include <vector>
void print(const std::vector<char>& v, auto suffix)
{
for (char c : v)
std::cout << c << ' ';
std::cout << suffix;
}
int main()
{
std::vector<char> v1{'a', 'b', 'c', 'd'};
std::vector<char> v2{'a', 'b', 'c', 'd'};
for (std::mt19937 g{std::random_device{}()};
!std::lexicographical_compare(v1.begin(), v1.end(),
v2.begin(), v2.end());)
{
print(v1, ">= ");
print(v2, '\n');
std::shuffle(v1.begin(), v1.end(), g);
std::shuffle(v2.begin(), v2.end(), g);
}
print(v1, "< ");
print(v2, '\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++ 標準に遡って適用された。
| DR | 適用先 | 公開時の動作 | 正しい動作 |
|---|---|---|---|
| LWG 142 | C++98 | 最大 min(N1,N2) 回の比較が許可されていたが、それは 不可能である (等価性は2回の比較で判定される) |
制限を2倍に変更 |
| LWG 1205 | C++98 | 空の範囲を含む辞書比較の結果が不明確であった | 明確化 |
関連項目
| 2つの要素の集合が同じかどうかを判定する (関数テンプレート & アルゴリズム関数オブジェクト) | |
(C++20) |
|
| 三方比較を使用して2つの範囲を比較する (関数テンプレート) | |
| 2つの範囲を辞書的に比較する (アルゴリズム関数オブジェクト) |