hpx/parallel/container_algorithms/is_sorted.hpp#

See Public API for a list of names and headers that are part of the public HPX API.

namespace hpx
namespace ranges

Functions

template<typename FwdIter, typename Sent, typename Pred = hpx::parallel::detail::less, typename Proj = hpx::identity>
bool is_sorted(FwdIter first, Sent last, Pred &&pred = Pred(), Proj &&proj = Proj())#

Determines if the range [first, last) is sorted. Uses pred to compare elements.

The comparison operations in the parallel is_sorted algorithm executes in sequential order in the calling thread.

Note

Complexity: at most (N+S-1) comparisons where N = distance(first, last). S = number of partitions

Template Parameters
  • FwdIter – The type of the source iterators used for the This iterator type must meet the requirements of a forward iterator.

  • Sent – The type of the source sentinel (deduced). This sentinel type must be a sentinel for FwdIter.

  • Pred – The type of an optional function/function object to use.

  • Proj – The type of an optional projection function. This defaults to hpx::identity

Parameters
  • first – Refers to the beginning of the sequence of elements of that the algorithm will be applied to.

  • last – Refers to the end of the sequence of elements of that the algorithm will be applied to.

  • pred – Refers to the binary predicate which returns true if the first argument should be treated as less than the second argument. The signature of the function should be equivalent to

    bool pred(const Type &a, const Type &b);
    
    The signature does not need to have const &, but the function must not modify the objects passed to it. The type Type must be such that objects of types FwdIter can be dereferenced and then implicitly converted to Type.

  • proj – Specifies the function (or function object) which will be invoked for each of the elements as a projection operation before the actual predicate is invoked.

Returns

The is_sorted algorithm returns a bool. The is_sorted algorithm returns true if each element in the sequence [first, last) satisfies the predicate passed. If the range [first, last) contains less than two elements, the function always returns true.

template<typename ExPolicy, typename FwdIter, typename Sent, typename Pred = hpx::parallel::detail::less, typename Proj = hpx::identity>
hpx::parallel::util::detail::algorithm_result_t<ExPolicy, bool> is_sorted(ExPolicy &&policy, FwdIter first, Sent last, Pred &&pred = Pred(), Proj &&proj = Proj())#

Determines if the range [first, last) is sorted. Uses pred to compare elements.

The comparison operations in the parallel is_sorted algorithm invoked with an execution policy object of type sequenced_policy executes in sequential order in the calling thread.

The comparison operations in the parallel is_sorted algorithm invoked with an execution policy object of type parallel_policy or parallel_task_policy are permitted to execute in an unordered fashion in unspecified threads, and indeterminately sequenced within each thread.

Note

Complexity: at most (N+S-1) comparisons where N = distance(first, last). S = number of partitions

Template Parameters
  • ExPolicy – The type of the execution policy to use (deduced). It describes the manner in which the execution of the algorithm may be parallelized and the manner in which it executes the assignments.

  • FwdIter – The type of the source iterators used for the This iterator type must meet the requirements of a forward iterator.

  • Sent – The type of the source sentinel (deduced). This sentinel type must be a sentinel for FwdIter.

  • Pred – The type of an optional function/function object to use. Unlike its sequential form, the parallel overload of is_sorted requires Pred to meet the requirements of CopyConstructible. This defaults to std::less<>

  • Proj – The type of an optional projection function. This defaults to hpx::identity

Parameters
  • policy – The execution policy to use for the scheduling of the iterations.

  • first – Refers to the beginning of the sequence of elements of that the algorithm will be applied to.

  • last – Refers to the end of the sequence of elements of that the algorithm will be applied to.

  • pred – Refers to the binary predicate which returns true if the first argument should be treated as less than the second argument. The signature of the function should be equivalent to

    bool pred(const Type &a, const Type &b);
    
    The signature does not need to have const &, but the function must not modify the objects passed to it. The type Type must be such that objects of types FwdIter can be dereferenced and then implicitly converted to Type.

  • proj – Specifies the function (or function object) which will be invoked for each of the elements as a projection operation before the actual predicate is invoked.

Returns

The is_sorted algorithm returns a hpx::future<bool> if the execution policy is of type task_execution_policy and returns bool otherwise. The is_sorted algorithm returns a bool if each element in the sequence [first, last) satisfies the predicate passed. If the range [first, last) contains less than two elements, the function always returns true.

template<typename Rng, typename Pred = hpx::parallel::detail::less, typename Proj = hpx::identity>
bool is_sorted(Rng &&rng, Pred &&pred = Pred(), Proj &&proj = Proj())#

Determines if the range rng is sorted. Uses pred to compare elements.

The comparison operations in the parallel is_sorted algorithm executes in sequential order in the calling thread.

Note

Complexity: at most (N+S-1) comparisons where N = size(rng). S = number of partitions

Template Parameters
  • Rng – The type of the source range used (deduced). The iterators extracted from this range type must meet the requirements of an forward iterator.

  • Pred – The type of an optional function/function object to use.

  • Proj – The type of an optional projection function. This defaults to hpx::identity

Parameters
  • rng – Refers to the sequence of elements the algorithm will be applied to.

  • pred – Refers to the binary predicate which returns true if the first argument should be treated as less than the second argument. The signature of the function should be equivalent to

    bool pred(const Type &a, const Type &b);
    
    The signature does not need to have const &, but the function must not modify the objects passed to it. The type Type must be such that objects of types FwdIter can be dereferenced and then implicitly converted to Type.

  • proj – Specifies the function (or function object) which will be invoked for each of the elements as a projection operation before the actual predicate is invoked.

Returns

The is_sorted algorithm returns a bool. The is_sorted algorithm returns true if each element in the rng satisfies the predicate passed. If the range rng contains less than two elements, the function always returns true.

template<typename ExPolicy, typename Rng, typename Pred = hpx::parallel::detail::less, typename Proj = hpx::identity>
hpx::parallel::util::detail::algorithm_result_t<ExPolicy, bool> is_sorted(ExPolicy &&policy, Rng &&rng, Pred &&pred = Pred(), Proj &&proj = Proj())#

Determines if the range rng is sorted. Uses pred to compare elements.

The comparison operations in the parallel is_sorted algorithm invoked with an execution policy object of type sequenced_policy executes in sequential order in the calling thread.

The comparison operations in the parallel is_sorted algorithm invoked with an execution policy object of type parallel_policy or parallel_task_policy are permitted to execute in an unordered fashion in unspecified threads, and indeterminately sequenced within each thread.

Note

Complexity: at most (N+S-1) comparisons where N = size(rng). S = number of partitions

Template Parameters
  • ExPolicy – The type of the execution policy to use (deduced). It describes the manner in which the execution of the algorithm may be parallelized and the manner in which it executes the assignments.

  • Rng – The type of the source range used (deduced). The iterators extracted from this range type must meet the requirements of an forward iterator.

  • Pred – The type of an optional function/function object to use. Unlike its sequential form, the parallel overload of is_sorted requires Pred to meet the requirements of CopyConstructible. This defaults to std::less<>

  • Proj – The type of an optional projection function. This defaults to hpx::identity

Parameters
  • policy – The execution policy to use for the scheduling of the iterations.

  • rng – Refers to the sequence of elements the algorithm will be applied to.

  • pred – Refers to the binary predicate which returns true if the first argument should be treated as less than the second argument. The signature of the function should be equivalent to

    bool pred(const Type &a, const Type &b);
    
    The signature does not need to have const &, but the function must not modify the objects passed to it. The type Type must be such that objects of types FwdIter can be dereferenced and then implicitly converted to Type.

  • proj – Specifies the function (or function object) which will be invoked for each of the elements as a projection operation before the actual predicate is invoked.

Returns

The is_sorted algorithm returns a hpx::future<bool> if the execution policy is of type task_execution_policy and returns bool otherwise. The is_sorted algorithm returns a bool if each element in the range rng satisfies the predicate passed. If the range rng contains less than two elements, the function always returns true.

template<typename FwdIter, typename Sent, typename Pred = hpx::parallel::detail::less, typename Proj = hpx::identity>
FwdIter is_sorted_until(FwdIter first, Sent last, Pred &&pred = Pred(), Proj &&proj = Proj())#

Returns the first element in the range [first, last) that is not sorted. Uses a predicate to compare elements or the less than operator.

The comparison operations in the parallel is_sorted_until algorithm execute in sequential order in the calling thread.

Note

Complexity: at most (N+S-1) comparisons where N = distance(first, last). S = number of partitions

Template Parameters
  • FwdIter – The type of the source iterators used for the This iterator type must meet the requirements of a forward iterator.

  • Sent – The type of the source sentinel (deduced). This sentinel type must be a sentinel for FwdIter.

  • Pred – The type of an optional function/function object to use.

  • Proj – The type of an optional projection function. This defaults to hpx::identity

Parameters
  • first – Refers to the beginning of the sequence of elements of that the algorithm will be applied to.

  • last – Refers to the end of the sequence of elements of that the algorithm will be applied to.

  • pred – Refers to the binary predicate which returns true if the first argument should be treated as less than the second argument. The signature of the function should be equivalent to

    bool pred(const Type &a, const Type &b);
    
    The signature does not need to have const &, but the function must not modify the objects passed to it. The type Type must be such that objects of types FwdIter can be dereferenced and then implicitly converted to Type.

  • proj – Specifies the function (or function object) which will be invoked for each of the elements as a projection operation before the actual predicate is invoked.

Returns

The is_sorted_until algorithm returns a FwdIter. The is_sorted_until algorithm returns the first unsorted element. If the sequence has less than two elements or the sequence is sorted, last is returned.

template<typename ExPolicy, typename FwdIter, typename Sent, typename Pred = hpx::parallel::detail::less, typename Proj = hpx::identity>
hpx::parallel::util::detail::algorithm_result<ExPolicy, FwdIter>::type is_sorted_until(ExPolicy &&policy, FwdIter first, Sent last, Pred &&pred = Pred(), Proj &&proj = Proj())#

Returns the first element in the range [first, last) that is not sorted. Uses a predicate to compare elements or the less than operator.

The comparison operations in the parallel is_sorted_until algorithm invoked with an execution policy object of type sequenced_policy executes in sequential order in the calling thread.

The comparison operations in the parallel is_sorted_until algorithm invoked with an execution policy object of type parallel_policy or parallel_task_policy are permitted to execute in an unordered fashion in unspecified threads, and indeterminately sequenced within each thread.

Note

Complexity: at most (N+S-1) comparisons where N = distance(first, last). S = number of partitions

Template Parameters
  • ExPolicy – The type of the execution policy to use (deduced). It describes the manner in which the execution of the algorithm may be parallelized and the manner in which it executes the assignments.

  • FwdIter – The type of the source iterators used for the This iterator type must meet the requirements of a forward iterator.

  • Sent – The type of the source sentinel (deduced). This sentinel type must be a sentinel for FwdIter.

  • Pred – The type of an optional function/function object to use. Unlike its sequential form, the parallel overload of is_sorted_until requires Pred to meet the requirements of CopyConstructible. This defaults to std::less<>

  • Proj – The type of an optional projection function. This defaults to hpx::identity

Parameters
  • policy – The execution policy to use for the scheduling of the iterations.

  • first – Refers to the beginning of the sequence of elements of that the algorithm will be applied to.

  • last – Refers to the end of the sequence of elements of that the algorithm will be applied to.

  • pred – Refers to the binary predicate which returns true if the first argument should be treated as less than the second argument. The signature of the function should be equivalent to

    bool pred(const Type &a, const Type &b);
    
    The signature does not need to have const &, but the function must not modify the objects passed to it. The type Type must be such that objects of types FwdIter can be dereferenced and then implicitly converted to Type.

  • proj – Specifies the function (or function object) which will be invoked for each of the elements as a projection operation before the actual predicate is invoked.

Returns

The is_sorted_until algorithm returns a hpx::future<FwdIter> if the execution policy is of type task_execution_policy and returns FwdIter otherwise. The is_sorted_until algorithm returns the first unsorted element. If the sequence has less than two elements or the sequence is sorted, last is returned.

template<typename Rng, typename Pred = hpx::parallel::detail::less, typename Proj = hpx::identity>
hpx::traits::range_iterator_t<Rng> is_sorted_until(Rng &&rng, Pred &&pred = Pred(), Proj &&proj = Proj())#

Returns the first element in the range rng that is not sorted. Uses a predicate to compare elements or the less than operator.

Note

Complexity: at most (N+S-1) comparisons where N = size(rng). S = number of partitions

Template Parameters
  • Rng – The type of the source range used (deduced). The iterators extracted from this range type must meet the requirements of an forward iterator.

  • Pred – The type of an optional function/function object to use. Unlike its sequential form, the parallel overload of is_sorted_until requires Pred to meet the requirements of CopyConstructible. This defaults to std::less<>

  • Proj – The type of an optional projection function. This defaults to hpx::identity

Parameters
  • rng – Refers to the sequence of elements the algorithm will be applied to.

  • pred – Refers to the binary predicate which returns true if the first argument should be treated as less than the second argument. The signature of the function should be equivalent to

    bool pred(const Type &a, const Type &b);
    
    The signature does not need to have const &, but the function must not modify the objects passed to it. The type Type must be such that objects of types FwdIter can be dereferenced and then implicitly converted to Type.

  • proj – Specifies the function (or function object) which will be invoked for each of the elements as a projection operation before the actual predicate is invoked.

Returns

The is_sorted_until returns FwdIter. The is_sorted_until algorithm returns the first unsorted element. If the sequence has less than two elements or the sequence is sorted, last is returned.

template<typename ExPolicy, typename Rng, typename Pred = hpx::parallel::detail::less, typename Proj = hpx::identity>
hpx::parallel::util::detail::algorithm_result<ExPolicy, hpx::traits::range_iterator_t<Rng>> is_sorted_until(ExPolicy &&policy, Rng &&rng, Pred &&pred = Pred(), Proj &&proj = Proj())#

Returns the first element in the range rng that is not sorted. Uses a predicate to compare elements or the less than operator.

The comparison operations in the parallel is_sorted_until algorithm invoked with an execution policy object of type sequenced_policy executes in sequential order in the calling thread.

The comparison operations in the parallel is_sorted_until algorithm invoked with an execution policy object of type parallel_policy or parallel_task_policy are permitted to execute in an unordered fashion in unspecified threads, and indeterminately sequenced within each thread.

Note

Complexity: at most (N+S-1) comparisons where N = size(rng). S = number of partitions

Template Parameters
  • ExPolicy – The type of the execution policy to use (deduced). It describes the manner in which the execution of the algorithm may be parallelized and the manner in which it executes the assignments.

  • Rng – The type of the source range used (deduced). The iterators extracted from this range type must meet the requirements of an forward iterator.

  • Pred – The type of an optional function/function object to use. Unlike its sequential form, the parallel overload of is_sorted_until requires Pred to meet the requirements of CopyConstructible. This defaults to std::less<>

  • Proj – The type of an optional projection function. This defaults to hpx::identity

Parameters
  • policy – The execution policy to use for the scheduling of the iterations.

  • rng – Refers to the sequence of elements the algorithm will be applied to.

  • pred – Refers to the binary predicate which returns true if the first argument should be treated as less than the second argument. The signature of the function should be equivalent to

    bool pred(const Type &a, const Type &b);
    
    The signature does not need to have const &, but the function must not modify the objects passed to it. The type Type must be such that objects of types FwdIter can be dereferenced and then implicitly converted to Type.

  • proj – Specifies the function (or function object) which will be invoked for each of the elements as a projection operation before the actual predicate is invoked.

Returns

The is_sorted_until algorithm returns a hpx::future<FwdIter> if the execution policy is of type task_execution_policy and returns FwdIter otherwise. The is_sorted_until algorithm returns the first unsorted element. If the sequence has less than two elements or the sequence is sorted, last is returned.