C++ 算法 is_sorted()函数

C++ 算法 is_sorted() 函数返回true，如果范围[first, last)的元素按升序排序。

元素的比较使用运算符 < 进行第一种版本，和 comp 进行第二种版本。

语法

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 : 一个指向要检查的范围中最后一个元素之后的随机访问迭代器。

comp : 一个用户定义的二元谓词函数，接受两个参数并返回true（如果两个参数是有序的）或false（如果两个参数不是有序的）。它遵循严格的弱排序来排序元素。

返回值

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

复杂度

复杂度与first和last之间的距离线性相关：比较元素对直到找到不匹配。

数据竞争

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

异常

如果元素比较或迭代器操作引发异常，则此函数会抛出异常。

注意：无效的参数会导致未定义的行为。

示例1

让我们看一个简单的示例来演示 is_sorted() 的使用：

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int main()
{
  vector<int> v = {3, 1, 4, 2, 5};

  cout << std::boolalpha;
  cout << "排序前：是否已排序？" << is_sorted(v.begin(), v.end()) << endl;

  sort(v.begin(), v.end());

  cout << "排序后：是否已排序？" << is_sorted(v.begin(), v.end()) << endl;

  return 0;
}

输出：

排序前：是否已排序？false
排序后：是否已排序？True

示例2

让我们看另一个简单的示例：

#include <iostream>     // std::cout
#include <algorithm>    // std::is_sorted, std::prev_permutation
#include <array>        // std::array

using namespace std;

int main () {
  array<int,5> a {2,4,1,3,5};

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

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

  } while (!is_sorted(a.begin(),a.end()));

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

  return 0;
}

输出:

a: 2 3 5 4 1
a: 2 3 5 1 4
a: 2 3 4 5 1
a: 2 3 4 1 5
a: 2 3 1 5 4
a: 2 3 1 4 5
a: 2 1 5 4 3
a: 2 1 5 3 4
a: 2 1 4 5 3
a: 2 1 4 3 5
a: 2 1 3 5 4
a: 2 1 3 4 5
a: 1 5 4 3 2
a: 1 5 4 2 3
a: 1 5 3 4 2
a: 1 5 3 2 4
a: 1 5 2 4 3
a: 1 5 2 3 4
a: 1 4 5 3 2
a: 1 4 5 2 3
a: 1 4 3 5 2
a: 1 4 3 2 5
a: 1 4 2 5 3
a: 1 4 2 3 5
a: 1 3 5 4 2
a: 1 3 5 2 4
a: 1 3 4 5 2
a: 1 3 4 2 5
a: 1 3 2 5 4
a: 1 3 2 4 5
a: 1 2 5 4 3
a: 1 2 5 3 4
a: 1 2 4 5 3
a: 1 2 4 3 5
a: 1 2 3 5 4
a: 1 2 3 4 5
the range is sorted!

上面的示例显示了排序的顺序，并打印元素直到排序完成。

示例3

看看另一个简单示例，检查元素是否已排序：

#include <iostream>
#include <algorithm>
#include <iterator>
using namespace std;

int main() 
{
    int digits[] = {3, 1, 4, 1, 5};

    for (auto i : digits) cout << i << ' ';
    cout << ": is_sorted: " << boolalpha
              << is_sorted(begin(digits), end(digits)) << '\n';

    sort(begin(digits), end(digits));

    for (auto i : digits) cout << i << ' ';
    cout << ": is_sorted: "
              << is_sorted(begin(digits), end(digits)) << '\n';

    return 0;
}

输出：

3 1 4 1 5 : is_sorted: false
1 1 3 4 5 : is_sorted: true

示例4

再来看一个简单的示例：

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

bool ignore_case(char a, char b) {
   return (tolower(a) == tolower(b));
}

int main(void) {
   vector<char> v = {'D', 'b', 'C', 'p', 'N'};
   bool result;

   result = is_sorted(v.begin(), v.end());

   if (result == false)
      cout << "Vector elements are not sorted in ascending order." << endl;

   result = is_sorted(v.begin(), v.end(), ignore_case);

   if (result == true)
      cout << "Vector elements are sorted in ascending order." << endl;

   return 0;
}

输出：

向量元素未按升序排序。
向量元素按升序排序。