C++ is_sorted_until()
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。它遵循严格的弱排序来对元素进行排序。
返回值
如果范围未排序,则返回第一个元素的迭代器,如果整个范围已排序,则返回最后的元素。
复杂度
第一个和最后一个之间的复杂度是线性的: 为每个元素调用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!