std::is_sorted
ja.cppreference.net より
| ヘッダ <algorithm>
|
||
template< class ForwardIt >
bool is_sorted( ForwardIt first, ForwardIt last );
|
で定義 (1) | (C++11以上) (C++20以上 constexpr) |
template< class ExecutionPolicy, class ForwardIt >
bool is_sorted( ExecutionPolicy&& policy,
ForwardIt first, ForwardIt last );
|
(2) | (C++17以上) |
template< class ForwardIt, class Compare >
bool is_sorted( ForwardIt first, ForwardIt last, Compare comp );
|
(3) | (C++11以上) (C++20以上 constexpr) |
template< class ExecutionPolicy, class ForwardIt, class Compare >
bool is_sorted( ExecutionPolicy&& policy,
ForwardIt first, ForwardIt last, Compare comp );
|
(4) | (C++17以上) |
範囲 [first, last) 内の要素が非減少順にソートされているかどうかを調べます。
3) 要素が
comp に関してソートされているかどうかを調べます。2,4) (1,3) と同じですが、
policy に従って実行されます。 これらのオーバーロードは、次の式の値が
true である場合にのみオーバーロード解決に参加します:
|
|
(C++20未満) |
|
|
(C++20以上) |
引数
| first, last | - | 調べる要素の 範囲 を定義するイテレータのペア |
| policy | - | 使用する 実行ポリシー |
| comp | - | 比較関数オブジェクト (Compare の要件を満たすオブジェクト) で、最初の引数が2番目の引数より true小さい (つまり、前に順序付けられる) 場合に を返します。 比較関数のシグネチャは以下と同等であるべきです:
シグネチャに |
| 型要件 | ||
-ForwardIt は LegacyForwardIterator の要件を満たさなければなりません。
| ||
-Compare は Compare の要件を満たさなければなりません。
| ||
戻り値
true 範囲内の要素が非減少順にソートされている場合は false、そうでなければ 。
計算量
N を std::distance(first, last) とすると:
1,2) O(N) 回の
operator<(C++20未満)std::less{}(C++20以上) を使用した比較。3,4) O(N) 回の比較子
comp の適用。例外
ExecutionPolicy という名前のテンプレートパラメータを持つオーバーロードは、以下のようにエラーを報告します:
- アルゴリズムの一部として呼び出された関数の実行が例外を送出し、かつ
ExecutionPolicyが 標準ポリシー の1つである場合、std::terminate が呼び出されます。それ以外のExecutionPolicyの場合、動作は処理系定義です。 - アルゴリズムがメモリの確保に失敗した場合、std::bad_alloc が送出されます。
実装例
| is_sorted (1) |
|---|
template<class ForwardIt>
bool is_sorted(ForwardIt first, ForwardIt last)
{
return std::is_sorted_until(first, last) == last;
}
|
| is_sorted (3) |
template<class ForwardIt, class Compare>
bool is_sorted(ForwardIt first, ForwardIt last, Compare comp)
{
return std::is_sorted_until(first, last, comp) == last;
}
|
注記
std::is_sorted 空の範囲および長さ1の範囲に対しては true を返します。
例
このコードを実行する
#include <algorithm>
#include <cassert>
#include <functional>
#include <iterator>
#include <vector>
int main()
{
std::vector<int> v;
assert(std::is_sorted(v.cbegin(), v.cend()) && "an empty range is always sorted");
v.push_back(42);
assert(std::is_sorted(v.cbegin(), v.cend()) && "a range of size 1 is always sorted");
int data[] = {3, 1, 4, 1, 5};
assert(not std::is_sorted(std::begin(data), std::end(data)));
std::sort(std::begin(data), std::end(data));
assert(std::is_sorted(std::begin(data), std::end(data)));
assert(not std::is_sorted(std::begin(data), std::end(data), std::greater<>{}));
}
関連項目
(C++11) |
最大のソート済み部分範囲を検出する (関数テンプレート & アルゴリズム関数オブジェクト) |
(C++20) |
|
(C++20) |
範囲がソートされているかどうかを調べる (アルゴリズム関数オブジェクト) |