C++

參考

<algorithm>

函式模板
<algorithm>

std::is_sorted_until

預設 (1)
template <class ForwardIterator>  ForwardIterator is_sorted_until (ForwardIterator first, ForwardIterator last);
自定義 (2)
template <class ForwardIterator, class Compare>  ForwardIterator is_sorted_until (ForwardIterator first, ForwardIterator last,                                   Compare comp);
查詢範圍內的第一個未排序元素
返回指向範圍 [first,last) 中第一個不遵循升序的元素的迭代器。

first 指向的元素和返回的迭代器之間的範圍 是已排序的。

如果整個範圍都是排序的，則函式返回 last。

元素使用第一個版本的 operator< 進行比較，第二個版本使用 comp 進行比較。

此函式模板的行為等同於
1
2
3
4
5
6
7
8
9
10
11
 
template <class ForwardIterator>
  ForwardIterator is_sorted_until (ForwardIterator first, ForwardIterator last)
{
  if (first==last) return first;
  ForwardIterator next = first;
  while (++next!=last) {
    if (*next<*first) return next;
    ++first;
  }
  return last;
}

引數

first, last
前向迭代器，指向序列的初始位置和最終位置。檢查的範圍是 [first,last)，它包含 first 和 last 之間的所有元素，包括 first 指向的元素，但不包括 last 指向的元素。
comp
二元函式，它接受範圍內的兩個元素作為引數，並返回一個可轉換為 bool 的值。返回的值指示傳遞的第一個引數是否被認為在它定義的特定嚴格弱序中排在第二個引數之前。
該函式不得修改其任何引數。
這可以是指向函式的指標，也可以是函式物件。

返回值

指向範圍中第一個不遵循升序的元素的迭代器，或者如果所有元素都已排序或範圍包含的元素少於兩個，則返回 last。

示例

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
 
// is_sorted_until example
#include <iostream>     // std::cout
#include <algorithm>    // std::is_sorted_until, std::prev_permutation
#include <array>        // std::array

int main () {
  std::array<int,4> foo {2,4,1,3};
  std::array<int,4>::iterator it;

  do {
    // try a new permutation:
    std::prev_permutation(foo.begin(),foo.end());

    // print range:
    std::cout << "foo:";
    for (int& x:foo) std::cout << ' ' << x;
    it=std::is_sorted_until(foo.begin(),foo.end());
    std::cout << " (" << (it-foo.begin()) << " elements sorted)\n";

  } while (it!=foo.end());

  std::cout << "the range is sorted!\n";

  return 0;
}

輸出
foo: 2 3 4 1 (3 elements sorted)
foo: 2 3 1 4 (2 elements sorted)
foo: 2 1 4 3 (1 elements sorted)
foo: 2 1 3 4 (1 elements sorted)
foo: 1 4 3 2 (2 elements sorted)
foo: 1 4 2 3 (2 elements sorted)
foo: 1 3 4 2 (3 elements sorted)
foo: 1 3 2 4 (2 elements sorted)
foo: 1 2 4 3 (3 elements sorted)
foo: 1 2 3 4 (4 elements sorted)
the range is sorted!


複雜度

最多線性於 first 和 last 之間的距離：為每個元素呼叫 comp 直到找到不匹配項。

資料競爭

範圍 [first,last) 中的一些（或全部）物件被訪問（最多一次）。

異常

如果 comp 或迭代器上的操作丟擲異常，則此函式將丟擲異常。
請注意，無效的引數會導致 *未定義行為*。

另見

is_sorted
檢查範圍是否已排序 (函式模板)
sort
對範圍中的元素進行排序 （函式模板）
find_if
在範圍中查詢元素 （函式模板）