hpx::stable_partition

hpx::stable_partition#

Defined in header hpx/algorithm.hpp.

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

See also:

template<typename BidirIter, typename F, typename Proj = hpx::identity>
BidirIter hpx::stable_partition(BidirIter first, BidirIter last, F &&f, Proj &&proj = Proj())#

Permutes the elements in the range [first, last) such that there exists an iterator i such that for every iterator j in the range [first, i) INVOKE(f, INVOKE (proj, *j)) != false, and for every iterator k in the range [i, last), INVOKE(f, INVOKE (proj, *k)) == false

The invocations of f in the parallel stable_partition algorithm invoked without an execution policy object executes in sequential order in the calling thread.

Note

Complexity: At most (last - first) * log(last - first) swaps, but only linear number of swaps if there is enough extra memory. Exactly last - first applications of the predicate and projection.

Template Parameters:

  • BidirIter – The type of the source iterators used (deduced). This iterator type must meet the requirements of a bidirectional iterator.

  • F – The type of the function/function object to use (deduced). Unlike its sequential form, the parallel overload of transform requires F to meet the requirements of CopyConstructible.

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

Parameters:

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

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

  • f – Unary predicate which returns true if the element should be ordered before other elements. Specifies the function (or function object) which will be invoked for each of the elements in the sequence specified by [first, last). The signature of this predicate should be equivalent to: 

    bool fun(const Type &a);
    The signature does not need to have const&. The type Type must be such that an object of type BidirIter 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 f is invoked.

Returns:

The stable_partition algorithm returns an iterator i such that for every iterator j in the range [first, i), f(*j) != false INVOKE(f, INVOKE(proj, *j)) != false, and for every iterator k in the range [i, last), f(*k) == false INVOKE(f, INVOKE (proj, *k)) == false. The relative order of the elements in both groups is preserved.

template<typename ExPolicy, typename BidirIter, typename F, typename Proj = hpx::identity>
parallel::util::detail::algorithm_result_t<ExPolicy, BidirIter> hpx::stable_partition(ExPolicy &&policy, BidirIter first, BidirIter last, F &&f, Proj &&proj = Proj())#

Permutes the elements in the range [first, last) such that there exists an iterator i such that for every iterator j in the range [first, i) INVOKE(f, INVOKE (proj, *j)) != false, and for every iterator k in the range [i, last), INVOKE(f, INVOKE (proj, *k)) == false

The invocations of f in the parallel stable_partition algorithm invoked with an execution policy object of type sequenced_policy executes in sequential order in the calling thread.

The invocations of f in the parallel stable_partition 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 (last - first) * log(last - first) swaps, but only linear number of swaps if there is enough extra memory. Exactly last - first applications of the predicate and projection.

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 invocations of f.

  • BidirIter – The type of the source iterators used (deduced). This iterator type must meet the requirements of a bidirectional iterator.

  • F – The type of the function/function object to use (deduced). Unlike its sequential form, the parallel overload of transform requires F to meet the requirements of CopyConstructible.

  • 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 the algorithm will be applied to.

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

  • f – Unary predicate which returns true if the element should be ordered before other elements. Specifies the function (or function object) which will be invoked for each of the elements in the sequence specified by [first, last). The signature of this predicate should be equivalent to: 

    bool fun(const Type &a);
    The signature does not need to have const&. The type Type must be such that an object of type BidirIter 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 f is invoked.

Returns:

The stable_partition algorithm returns an iterator i such that for every iterator j in the range [first, i), f(*j) != false INVOKE(f, INVOKE(proj, *j)) != false, and for every iterator k in the range [i, last), f(*k) == false INVOKE(f, INVOKE (proj, *k)) == false. The relative order of the elements in both groups is preserved. If the execution policy is of type parallel_task_policy the algorithm returns a future<> referring to this iterator.

Contents