Przejdź do głównej zawartości

std::ranges::is_sorted() algorithm

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

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

The type of arguments are generic and have the following constraints:

  • 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 - (none)

The Proj and Comp template arguments have the following default types: std::identity, ranges::less for all overloads.

Checks if the elements in range [first; last) are sorted.

A sequence is sorted with respect to a comparator comp if for any iterator it pointing to the sequence and any non-negative integer n such that it + n is a valid iterator pointing to an element of the sequence, std::invoke(comp, std::invoke(proj, *(it + n)), std::invoke(proj, *it)) evaluates to false.

  • (1) Elements are compared using the given binary comparison function comp.
  • (2) Same as (1), but uses r as the source range, as if using ranges::begin(r) as first and ranges::end(r) as last.

The function-like entities described on this page are niebloids.

Parameters

first
last

The range of elements to examine.

r

The range of elements to examine.

comp

Comparison function to apply to the projected elemenets.

proj

The projection to apply to the elements.

Return value

true if the elements in the range are sorted according to comp (also for empty ranges and ranges of length one).

Complexity

Linear in the distance between first and last.

Exceptions

(none)

Possible implementation

is_sorted(1) and 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;

Examples

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";
}
Possible Output
3 1 4 1 5 : not sorted
1 1 3 4 5 : sorted
5 4 3 1 1 : sorted (with 'greater')
This article originates from this CppReference page. It was likely altered for improvements or editors' preference. Click "Edit this page" to see all changes made to this document.
Hover to see the original license.

std::ranges::is_sorted() algorithm

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

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

The type of arguments are generic and have the following constraints:

  • 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 - (none)

The Proj and Comp template arguments have the following default types: std::identity, ranges::less for all overloads.

Checks if the elements in range [first; last) are sorted.

A sequence is sorted with respect to a comparator comp if for any iterator it pointing to the sequence and any non-negative integer n such that it + n is a valid iterator pointing to an element of the sequence, std::invoke(comp, std::invoke(proj, *(it + n)), std::invoke(proj, *it)) evaluates to false.

  • (1) Elements are compared using the given binary comparison function comp.
  • (2) Same as (1), but uses r as the source range, as if using ranges::begin(r) as first and ranges::end(r) as last.

The function-like entities described on this page are niebloids.

Parameters

first
last

The range of elements to examine.

r

The range of elements to examine.

comp

Comparison function to apply to the projected elemenets.

proj

The projection to apply to the elements.

Return value

true if the elements in the range are sorted according to comp (also for empty ranges and ranges of length one).

Complexity

Linear in the distance between first and last.

Exceptions

(none)

Possible implementation

is_sorted(1) and 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;

Examples

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";
}
Possible Output
3 1 4 1 5 : not sorted
1 1 3 4 5 : sorted
5 4 3 1 1 : sorted (with 'greater')
This article originates from this CppReference page. It was likely altered for improvements or editors' preference. Click "Edit this page" to see all changes made to this document.
Hover to see the original license.