std::
is_sorted_until
函数模板 <algorithm>| 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)中第一个不遵循升序元素的迭代器。
first迭代器和返回的迭代器之间的范围是排序的。
如果整个范围都已排序，则函数返回last。
第一个版本使用operator<比较元素，第二个版本使用comp操作符比较元素。
这个函数模板(2)的行为相当于:
template <class ForwardIterator>
ForwardIterator is_sorted_until (ForwardIterator first, ForwardIterator last)
{
if (first==last) return first;
ForwardIterator next = first;
while (++next!=last) {
if (*next<*first) return next;
++first;
}
return last;
} |
☲ 参数
- first, last
- 指向一个序列初始和最终位置的前向迭代器。使用的范围是[first,last)， 它包含first和last之间的所有元素，包括first指向的元素，但不包括last指向的元素。
- comp
-
二元函数，它接受范围中的两个元素作为参数，并返回可转换为bool的值。
返回的值表明作为第一个参数传递的元素是否按照其定义的严格弱顺序先于第二个参数。
函数不能修改它的任何参数。
它可以是函数指针，也可以是函数对象。
☉ 返回值
一个迭代器，指向范围内第一个不按升序排列的元素，如果所有元素都已排序， 或者范围内包含的元素少于两个，则该迭代器位于last.
☣ 示例
// is_sorted_until example
#include <iostream> // std::cout
#include <algorithm> // std::is_sorted_until, std::prev_permutation
#include <array> // std::array
int main () {
std::array<int,4> foo {2,4,1,3};
std::array<int,4>::iterator it;
do {
// try a new permutation:
std::prev_permutation(foo.begin(),foo.end());
// print range:
std::cout << "foo:";
for (int& x:foo) std::cout << ' ' << x;
it=std::is_sorted_until(foo.begin(),foo.end());
std::cout << " (" << (it-foo.begin()) << " elements sorted)\n";
} while (it!=foo.end());
std::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!
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!
✥ 复杂度
在 first and last之间的距离线性:对每个元素调用comp，直到发现不匹配。
⇄ 数据竞争
范围[first,last)中的部分(或全部)对象将被访问。
☂ 异常安全性
如果comp或迭代器上的操作抛出，则抛出。
注意，无效的参数会导致未定义的行为。
🍄 另请参阅
| sort | 对范围内的元素进行排序(函数模板) |
| is_sorted | 检查范围是否排序(函数模板) |
| find_if | 在范围内查找元素(函数模板) |