hpx/parallel/algorithms/sort_by_key.hpp#

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

namespace hpx
namespace parallel

Typedefs

template<typename KeyIter, typename ValueIter>
using sort_by_key_result = std::pair<KeyIter, ValueIter>#

Functions

template<typename ExPolicy, typename KeyIter, typename ValueIter, typename Compare = detail::less>
util::detail::algorithm_result_t<ExPolicy, sort_by_key_result<KeyIter, ValueIter>> sort_by_key(ExPolicy &&policy, KeyIter key_first, KeyIter key_last, ValueIter value_first, Compare &&comp = Compare())#

Sorts one range of data using keys supplied in another range. The key elements in the range [key_first, key_last) are sorted in ascending order with the corresponding elements in the value range moved to follow the sorted order. The algorithm is not stable, the order of equal elements is not guaranteed to be preserved. The function uses the given comparison function object comp (defaults to using operator<()). Executed according to the policy.

A sequence is sorted with respect to a comparator comp 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, *(i + n), *i) == false.

comp has to induce a strict weak ordering on the values.

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.

Note

Complexity: O(Nlog(N)), where N = std::distance(first, last) comparisons.

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.

  • KeyIter – The type of the key iterators used (deduced). This iterator type must meet the requirements of a random access iterator.

  • ValueIter – The type of the value iterators used (deduced). This iterator type must meet the requirements of a random access iterator.

  • Compare – The type of the function/function object to use (deduced).

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

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

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

  • value_first – Refers to the beginning of the sequence of value elements the algorithm will be applied to, the range of elements must match [key_first, key_last)

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

Returns

The sort_by_key algorithm returns a hpx::future<sort_by_key_result<KeyIter,ValueIter>> if the execution policy is of type sequenced_task_policy or parallel_task_policy and returns otherwise. The algorithm returns a pair holding an iterator pointing to the first element after the last element in the input key sequence and an iterator pointing to the first element after the last element in the input value sequence.

namespace v1