hpx/parallel/algorithms/is_sorted.hpp#

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

namespace hpx

Functions

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

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.

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

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.

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 Pred = hpx::parallel::v1::detail::less>
hpx::parallel::util::detail::algorithm_result<ExPolicy, bool>::type is_sorted(ExPolicy &&policy, FwdIter first, FwdIter last, Pred &&pred = Pred())#

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.

• 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<>

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.

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 FwdIter, typename Pred = hpx::parallel::v1::detail::less>
FwdIter is_sorted_until(FwdIter first, FwdIter last, Pred &&pred = Pred())#

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.

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

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.

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 Pred = hpx::parallel::v1::detail::less>
hpx::parallel::util::detail::algorithm_result<ExPolicy, FwdIter>::type is_sorted_until(ExPolicy &&policy, FwdIter first, FwdIter last, Pred &&pred = Pred())#

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.

• 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<>

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.

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.