C++ 算法 is_sorted_until()函数

C++算法 is_sorted_until() 函数用于查找范围中第一个未排序的元素。这意味着它返回一个迭代器，指向范围[first, last)中第一个不按升序排列的元素。

元素的比较使用操作符 < 进行，第一个版本，使用 comp 。

语法

default (1) template <class ForwardIterator>
                      ForwardIterator is_sorted_until (ForwardIterator first, ForwardIterator last);

custom (2)  template <class ForwardIterator, class Compare>
                       ForwardIterator is_sorted_until (ForwardIterator first, ForwardIterator last,
                                   Compare comp);

参数

first ：指向要检查的范围中第一个元素的前向迭代器。

last ：指向要检查的范围中最后一个元素之后的随机访问迭代器。

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

返回值

如果范围是无序的，则返回指向第一个元素的迭代器；如果整个范围都是有序的，则返回last。

复杂度

在first和last之间的复杂度是线性的：对每个元素调用comp直到找到一个不匹配。

数据竞争

范围[first，last）中的对象被访问。

异常

如果comp或迭代器上的操作引发异常，此函数会抛出异常。

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

示例1

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

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

using namespace std;

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

  cout << boolalpha;
  cout << "Before: is it sorted? "
            << (is_sorted_until(v.begin(), v.end()) == v.end()) << endl;

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

  cout << "After: is it sorted? "
            << (is_sorted_until(v.begin(), v.end()) == v.end()) << endl;

  return 0;
}

输出结果：

Before: is it sorted? false
After: is it sorted? true

示例2

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

#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 = {'A', 'b', 'C', 'd', 'E'};

   auto it = is_sorted_until(v.begin(), v.end());

   cout << "First unsorted element = " << *it << endl;

   it = is_sorted_until(v.begin(), v.end(), ignore_case);

   if (it == end(v))
      cout << "Entire vector is sorted." << endl;

   return 0;
}

输出：

First unsorted element = C
Entire vector is sorted.

示例3

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

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

using namespace std;

int main(void) {
   vector<int> v = {1, 2, 5, 3, 4};
   auto it = is_sorted_until(v.begin(), v.end());

   cout << "First unsorted element = " << *it << endl;

   v[3] = 4;

   it = is_sorted_until(v.begin(), v.end());

   if (it == end(v))
      cout << "Entire vector is sorted." << endl;

   return 0;
}

输出：

First unsorted element = 3

示例4

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

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

using namespace std;

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

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

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

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

  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!