C++

参考

<algorithm>

function template
<algorithm>

std::is_sorted

默认 (1)
template <class ForwardIterator>  bool is_sorted (ForwardIterator first, ForwardIterator last);
自定义 (2)
template <class ForwardIterator, class Compare>  bool is_sorted (ForwardIterator first, ForwardIterator last, Compare comp);
检查范围是否已排序
如果范围 [first,last) 是升序排列的，则返回 true。

元素使用第一个版本的 operator< 进行比较，第二个版本使用 comp 进行比较。

此函数模板的行为等同于
1
2
3
4
5
6
7
8
9
10
11
12
 
template <class ForwardIterator>
  bool is_sorted (ForwardIterator first, ForwardIterator last)
{
  if (first==last) return true;
  ForwardIterator next = first;
  while (++next!=last) {
    if (*next<*first)     // or, if (comp(*next,*first)) for version (2)
      return false;
    ++first;
  }
  return true;
}

参数

first, last
Forward iterators 指向序列的初始位置和结束位置。要检查的范围是 [first,last)，它包含 first 和 last 之间的所有元素，包括 first 指向的元素，但不包括 last 指向的元素。
comp
二元函数，接受范围中的两个元素作为参数，并返回一个可转换为 bool 的值。返回的值指示传递为第一个参数的元素是否在它定义的特定严格弱序中排在第二个元素之前。
该函数不得修改其任何参数。
这可以是指针函数，也可以是函数对象。

返回值

如果范围 [first,last) 是升序排列的，则为 true，否则为 false。

如果范围 [first,last) 包含的元素少于两个，则函数始终返回 true。

示例

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

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

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

    // print range:
    std::cout << "foo:";
    for (int& x:foo) std::cout << ' ' << x;
    std::cout << '\n';

  } while (!std::is_sorted(foo.begin(),foo.end()));

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

  return 0;
}

输出
foo: 2 3 4 1
foo: 2 3 1 4
foo: 2 1 4 3
foo: 2 1 3 4
foo: 1 4 3 2
foo: 1 4 2 3
foo: 1 3 4 2
foo: 1 3 2 4
foo: 1 2 4 3
foo: 1 2 3 4
the range is sorted!


复杂度

最多线性于 first 和 last 之间距离少 1 的值：比较元素对直到找到不匹配项。

数据竞争

访问范围 [first,last) 中的对象。

异常

如果元素比较或迭代器操作引发异常，则抛出。
请注意，无效参数会导致未定义行为。

另见

is_sorted_until
在范围中查找第一个未排序的元素 （函数模板）
sort
对范围中的元素进行排序 （函数模板）
partial_sort
对范围中的元素进行部分排序 （函数模板）