C++中的std::is_sorted_until及示例

在C++标准库中，std::is_sorted_until函数是用来找到一个序列中的第一个未排序的元素的。下面我们来详细了解一下这个函数的使用以及实现。

函数原型

在C++标准库中，std::is_sorted_until函数的函数原型为：

template< class ForwardIt >
ForwardIt is_sorted_until( ForwardIt first, ForwardIt last );

template< class ForwardIt, class Compare >
ForwardIt is_sorted_until( ForwardIt first, ForwardIt last, Compare comp );

其中，ForwardIt是一个元素类型为可向前迭代器的迭代器类型。first和last分别表示容器中第一个元素和最后一个元素的迭代器，comp是一个用于定义比较关系的二元谓词，如果没有给出比较函数，则默认使用operator<进行比较。

函数介绍

std::is_sorted_until可以用于判断一个序列是否已经按照升序排列（默认情况下），如果是，则返回指向最后一个元素的迭代器。如果不是，则返回指向第一个未排序元素的迭代器。以下是一个示例：

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

bool myFunction(int i, int j) { return (i < j); }

int main() {
  std::vector<int> arr{ 1, 2, 4, 3, 5, 6 };

  auto check_point = std::is_sorted_until(arr.begin(), arr.end());
  bool is_sorted = (check_point == arr.end());

  if (is_sorted) {
    std::cout << "The array is sorted" << std::endl;
  } else {
    std::cout << "The array is not sorted, first unsorted element: " << *check_point << std::endl;
  }

  auto check_point2 = std::is_sorted_until(arr.begin(), arr.end(), myFunction);
  bool is_sorted2 = (check_point2 == arr.end());

  if (is_sorted2) {
    std::cout << "The array is sorted" << std::endl;
  } else {
    std::cout << "The array is not sorted, first unsorted element: " << *check_point2 << std::endl;
  }

  return 0;
}

在这个例子中，我们首先定义了一个整型数组arr，并将它的元素打乱。随后，我们调用了std::is_sorted_until函数来检查数组是否已经按升序排序。最后，我们输出检查结果。

需要注意的是，在上面的代码中，我们演示了如何用用户提供的比较函数来使用std::is_sorted_until。在这种情况下，我们需要将自定义的比较函数作为第二个参数传递给std::is_sorted_until函数。

函数实现

下面是一个简单的实现std::is_sorted_until函数的示例代码：

template<class ForwardIt>
ForwardIt is_sorted_until(ForwardIt first, ForwardIt last) {
  if (first == last) {
    return last;
  }

  ForwardIt next = std::next(first);
  while (next != last && !(*next < *first)) { // 或者用 !comp(*first, *next)
    first = next;
    ++next;
  }

  return next;
}

在这个示例代码中，我们首先判断了序列的起始和末尾迭代器是否相同，如果相同，则说明序列为空，直接返回last。否则，就定义了两个迭代器，一个是指向当前比较的元素，另一个则指向下一个元素。然后，我们循环比较这两个元素，如果序列是升序排列，则next会一直遍历到序列的末尾。否则，is_sorted_until函数会返回指向第一个未排序元素的迭代器。