is_sorted-c和c++中文资料站

C&C++标准库

std::

is_sorted

函数模板 <algorithm>

default (1)

template <class ForwardIterator>
  bool is_sorted (ForwardIterator first, ForwardIterator last);

custom (2)

template <class ForwardIterator, class Compare>
  bool is_sorted (ForwardIterator first, ForwardIterator last, Compare comp);

检查范围是否排序

如果范围[first,last)按升序排序，则返回true。

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

这个函数模板(2)的行为相当于:

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: 指向一个序列初始和最终位置的前向迭代器。使用的范围是[first,last)，它包含first和last之间的所有元素，包括first指向的元素，但不包括last指向的元素。
comp: 二元函数，它接受范围中的两个元素作为参数，并返回可转换为bool的值。返回的值表明作为第一个参数传递的元素是否按照其定义的严格弱顺序先于第二个参数。
函数不能修改它的任何参数。
它可以是函数指针，也可以是函数对象。

☉ 返回值

如果范围 [first,last)按升序排序为True，否则为false。如果范围[first,last)包含少于两个元素，函数总是返回true。

☣ 示例

// 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 and last之间的距离小于1的线性:比较元素对，直到发现不匹配。

⇄ 数据竞争

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

☂ 异常安全性

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

🍄 另请参阅

sort	对范围内的元素进行排序(函数模板)
is_sorted_until	找到范围内第一个未排序的元素(函数模板)
partial_sort	对范围内的元素进行部分排序(函数模板)