hpx/parallel/container_algorithms/sort.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
RandomIt
, typenameSent
, typenameComp
, typenameProj
>
RandomItsort
(RandomIt first, Sent last, Comp &&comp, Proj &&proj)¶ Sorts the elements in the range [first, last) in ascending order. The order of equal elements is not guaranteed to be preserved. The function uses the given comparison function object comp (defaults to using operator<()).
A sequence is sorted with respect to a comparator
comp and a projection proj if for every iterator i pointing to the sequence and every non-negative integer n such that i + n is a valid iterator pointing to an element of the sequence, and INVOKE(comp, INVOKE(proj, *(i + n)), INVOKE(proj, *i)) == false.- Note
Complexity: O(Nlog(N)), where N = detail::distance(first, last) comparisons.
comp has to induce a strict weak ordering on the values.
- Template Parameters
RandomIt
: The type of the source iterators used (deduced). This iterator type must meet the requirements of an random iterator.Sent
: The type of the source sentinel (deduced). This sentinel type must be a sentinel for RandomIt.Comp
: The type of the function/function object to use (deduced).Proj
: The type of an optional projection function. This defaults to util::projection_identity
- Parameters
first
: Refers to the beginning of the sequence of elements the algorithm will be applied to.last
: Refers to sentinel value denoting the end of the sequence of elements the algorithm will be applied.comp
: comp is a callable object. The return value of the INVOKE operation applied to an object of type Comp, when contextually converted to bool, yields true if the first argument of the call is less than the second, and false otherwise. It is assumed that comp will not apply any non-constant function through the dereferenced iterator.proj
: Specifies the function (or function object) which will be invoked for each pair of elements as a projection operation before the actual predicate comp is invoked.
The assignments in the parallel sort algorithm invoked without an execution policy object execute in sequential order in the calling thread.
- Return
The sort algorithm returns RandomIt. The algorithm returns an iterator pointing to the first element after the last element in the input sequence.
-
template<typename
ExPolicy
, typenameRandomIt
, typenameSent
, typenameComp
, typenameProj
>
parallel::util::detail::algorithm_result<ExPolicy, RandomIt>::typesort
(ExPolicy &&policy, RandomIt first, Sent last, Comp &&comp, Proj &&proj)¶ Sorts the elements in the range [first, last) in ascending order. The order of equal elements is not guaranteed to be preserved. The function uses the given comparison function object comp (defaults to using operator<()).
A sequence is sorted with respect to a comparator
comp and a projection proj if for every iterator i pointing to the sequence and every non-negative integer n such that i + n is a valid iterator pointing to an element of the sequence, and INVOKE(comp, INVOKE(proj, *(i + n)), INVOKE(proj, *i)) == false.- Note
Complexity: O(Nlog(N)), where N = detail::distance(first, last) comparisons.
comp has to induce a strict weak ordering on the values.
- 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.RandomIt
: The type of the source iterators used (deduced). This iterator type must meet the requirements of an random iterator.Sent
: The type of the source sentinel (deduced). This sentinel type must be a sentinel for RandomIt.Comp
: The type of the function/function object to use (deduced).Proj
: The type of an optional projection function. This defaults to util::projection_identity
- Parameters
policy
: The execution policy to use for the scheduling of the iterations.first
: Refers to the beginning of the sequence of elements the algorithm will be applied to.last
: Refers to sentinel value denoting the end of the sequence of elements the algorithm will be applied.comp
: comp is a callable object. The return value of the INVOKE operation applied to an object of type Comp, when contextually converted to bool, yields true if the first argument of the call is less than the second, and false otherwise. It is assumed that comp will not apply any non-constant function through the dereferenced iterator.proj
: Specifies the function (or function object) which will be invoked for each pair of elements as a projection operation before the actual predicate comp is invoked.
The application of function objects in parallel algorithm invoked with an execution policy object of type sequenced_policy execute in sequential order in the calling thread.
The application of function objects in parallel 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.
- Return
The sort algorithm returns a hpx::future<RandomIt> if the execution policy is of type sequenced_task_policy or parallel_task_policy and returns RandomIt otherwise. The algorithm returns an iterator pointing to the first element after the last element in the input sequence.
-
template<typename
Rng
, typenameComp
, typenameProj
>
hpx::traits::range_iterator<Rng>::typesort
(Rng &&rng, Compare &&comp, Proj &&proj)¶ Sorts the elements in the range rng in ascending order. The order of equal elements is not guaranteed to be preserved. The function uses the given comparison function object comp (defaults to using operator<()).
A sequence is sorted with respect to a comparator
comp and a projection proj if for every iterator i pointing to the sequence and every non-negative integer n such that i + n is a valid iterator pointing to an element of the sequence, and INVOKE(comp, INVOKE(proj, *(i + n)), INVOKE(proj, *i)) == false.- Note
Complexity: O(Nlog(N)), where N = std::distance(begin(rng), end(rng)) comparisons.
comp has to induce a strict weak ordering on the values.
- Template Parameters
Rng
: The type of the source range used (deduced). The iterators extracted from this range type must meet the requirements of an input iterator.Comp
: The type of the function/function object to use (deduced).Proj
: The type of an optional projection function. This defaults to util::projection_identity
- Parameters
rng
: Refers to the sequence of elements the algorithm will be applied to.comp
: comp is a callable object. The return value of the INVOKE operation applied to an object of type Comp, when contextually converted to bool, yields true if the first argument of the call is less than the second, and false otherwise. It is assumed that comp will not apply any non-constant function through the dereferenced iterator.proj
: Specifies the function (or function object) which will be invoked for each pair of elements as a projection operation before the actual predicate comp is invoked.
The assignments in the parallel sort algorithm invoked without an execution policy object execute in sequential order in the calling thread.
- Return
The sort algorithm returns typename hpx::traits::range_iterator<Rng>::type. It returns last.
-
template<typename
ExPolicy
, typenameRng
, typenamePred
, typenameProj
>
util::detail::algorithm_result<ExPolicy, typename hpx::traits::range_iterator<Rng>::type>::typesort
(ExPolicy &&policy, Rng &&rng, Comp &&comp, Proj&&)¶ Sorts the elements in the range rng in ascending order. The order of equal elements is not guaranteed to be preserved. The function uses the given comparison function object comp (defaults to using operator<()).
A sequence is sorted with respect to a comparator
comp and a projection proj if for every iterator i pointing to the sequence and every non-negative integer n such that i + n is a valid iterator pointing to an element of the sequence, and INVOKE(comp, INVOKE(proj, *(i + n)), INVOKE(proj, *i)) == false.- Note
Complexity: O(Nlog(N)), where N = std::distance(begin(rng), end(rng)) comparisons.
comp has to induce a strict weak ordering on the values.
- 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 applies user-provided function objects.Rng
: The type of the source range used (deduced). The iterators extracted from this range type must meet the requirements of an input iterator.Comp
: The type of the function/function object to use (deduced).Proj
: The type of an optional projection function. This defaults to util::projection_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.comp
: comp is a callable object. The return value of the INVOKE operation applied to an object of type Comp, when contextually converted to bool, yields true if the first argument of the call is less than the second, and false otherwise. It is assumed that comp will not apply any non-constant function through the dereferenced iterator.proj
: Specifies the function (or function object) which will be invoked for each pair of elements as a projection operation before the actual predicate comp is invoked.
The application of function objects in parallel algorithm invoked with an execution policy object of type sequenced_policy execute in sequential order in the calling thread.
The application of function objects in parallel 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.
- Return
The sort algorithm returns a hpx::future<typename hpx::traits::range_iterator<Rng> ::type> if the execution policy is of type sequenced_task_policy or parallel_task_policy and returns typename hpx::traits::range_iterator<Rng>::type otherwise. It returns last.
-
template<typename
-
namespace