std::ranges::is_sorted() 算法

自 C++20 起

简化

// (1)
constexpr bool
    is_sorted( I first, S last, Comp comp = {}, Proj proj = {} );

// (2)
constexpr bool
    is_sorted( R&& r, Comp comp = {}, Proj proj = {} );

参数类型是泛型的，并具有以下约束

• I - std::forward_iterator
• S - std::sentinel_for<I>
• R - std::ranges::forward_range
• Comp:
  • (1) - std::indirect_strict_weak_order<std::projected<I, Proj>>
  • (2) - std::indirect_strict_weak_order<std::projected<ranges::iterator_t<R>, Proj>>
• Proj - (无)

所有重载的 Proj 和 Comp 模板参数具有以下默认类型：std::identity, ranges::less。

详细

// (1)
template<
  std::forward_iterator I,
  std::sentinel_for<I> S,
  class Proj = std::identity,
  std::indirect_strict_weak_order<std::projected<I, Proj>> Comp = ranges::less
>
constexpr bool
    is_sorted( I first, S last, Comp comp = {}, Proj proj = {} );

// (2)
template<
  ranges::forward_range R,
  class Proj = std::identity,
  std::indirect_strict_weak_order<std::projected<ranges::iterator_t<R>, Proj>> Comp = ranges::less
>
constexpr bool
    is_sorted( R&& r, Comp comp = {}, Proj proj = {} );

检查范围 [first; last) 中的元素是否已排序。

如果对于指向序列的任何迭代器 it 和任何非负整数 n（使得 it + n 是指向序列元素的有效迭代器），std::invoke(comp, std::invoke(proj, *(it + n)), std::invoke(proj, *it)) 评估为 false，则序列相对于比较器 comp 已排序。

• (1) 使用给定的二元比较函数 comp 比较元素。
• (2) 与 (1) 相同，但使用 r 作为源范围，如同使用 ranges::begin(r) 作为 first 和 ranges::end(r) 作为 last。

本页描述的函数类实体是niebloids。

参数

first last	要检查的元素范围。
r	要检查的元素范围。
comp	应用于投影元素的比较函数。
proj	要应用于元素的投影。

返回值

如果范围中的元素按照 comp 已排序（也适用于空范围和长度为一的范围），则为 true。

复杂度

与 first 和 last 之间的距离成线性关系。

异常

(无)

可能的实现

is_sorted(1) 和 is_sorted(2)

struct is_sorted_fn
{
    template<std::forward_iterator I, std::sentinel_for<I> S,
             class Proj = std::identity,
             std::indirect_strict_weak_order<std::projected<I, Proj>>
                 Comp = ranges::less>
    constexpr bool operator()(I first, S last, Comp comp = {}, Proj proj = {}) const
    {
        return ranges::is_sorted_until(first, last, comp, proj) == last;
    }

    template<ranges::forward_range R, class Proj = std::identity,
             std::indirect_strict_weak_order<
                 std::projected<ranges::iterator_t<R>, Proj>>
                     Comp = ranges::less>
    constexpr bool operator()(R&& r, Comp comp = {}, Proj proj = {}) const
    {
        return (*this)(ranges::begin(r), ranges::end(r), std::ref(comp), std::ref(proj));
    }
};

inline constexpr is_sorted_fn is_sorted;

示例

Main.cpp

#include <algorithm>
#include <array>
#include <functional>
#include <iostream>
#include <iterator>

int main()
{
    namespace ranges = std::ranges;

    std::array digits {3, 1, 4, 1, 5};

    ranges::copy(digits, std::ostream_iterator<int>(std::cout, " "));
    ranges::is_sorted(digits)
        ? std::cout << ": sorted\n"
        : std::cout << ": not sorted\n";

    ranges::sort(digits);

    ranges::copy(digits, std::ostream_iterator<int>(std::cout, " "));
    ranges::is_sorted(ranges::begin(digits), ranges::end(digits))
        ? std::cout << ": sorted\n"
        : std::cout << ": not sorted\n";

    ranges::reverse(digits);

    ranges::copy(digits, std::ostream_iterator<int>(std::cout, " "));
    ranges::is_sorted(digits, ranges::greater {})
        ? std::cout << ": sorted (with 'greater')\n"
        : std::cout << ": not sorted\n";
}

可能的输出

3 1 4 1 5 : not sorted
1 1 3 4 5 : sorted
5 4 3 1 1 : sorted (with 'greater')