hpx::merge, hpx::inplace_merge#

Defined in header hpx/algorithm.hpp.

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

namespace hpx

Functions

template<typename ExPolicy, typename RandIter1, typename RandIter2, typename RandIter3, typename Comp = hpx::parallel::detail::less>
hpx::parallel::util::detail::algorithm_result_t<ExPolicy, RandIter3> merge(ExPolicy &&policy, RandIter1 first1, RandIter1 last1, RandIter2 first2, RandIter2 last2, RandIter3 dest, Comp &&comp = Comp())#

Merges two sorted ranges [first1, last1) and [first2, last2) into one sorted range beginning at dest. The order of equivalent elements in the each of original two ranges is preserved. For equivalent elements in the original two ranges, the elements from the first range precede the elements from the second range. The destination range cannot overlap with either of the input ranges. Executed according to the policy.

The assignments in the parallel merge algorithm invoked with an execution policy object of type sequenced_policy execute in sequential order in the calling thread.

The assignments in the parallel merge 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: Performs O(std::distance(first1, last1) + std::distance(first2, last2)) applications of the comparison comp and the each 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 assignments.

  • RandIter1 – The type of the source iterators used (deduced) representing the first sorted range. This iterator type must meet the requirements of an random access iterator.

  • RandIter2 – The type of the source iterators used (deduced) representing the second sorted range. This iterator type must meet the requirements of an random access iterator.

  • RandIter3 – The type of the iterator representing the destination range (deduced). This iterator type must meet the requirements of an random access iterator.

  • Comp – The type of the function/function object to use (deduced). Unlike its sequential form, the parallel overload of merge requires Comp to meet the requirements of CopyConstructible. This defaults to std::less<>

Parameters

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

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

  • last1 – Refers to the end of the first range of elements the algorithm will be applied to.

  • first2 – Refers to the beginning of the second range of elements the algorithm will be applied to.

  • last2 – Refers to the end of the second range of elements the algorithm will be applied to.

  • dest – Refers to the beginning of the destination range.

  • comp – comp is a callable object which returns true if the first argument is less than the second, and false otherwise. The signature of this comparison should be equivalent to: 

    bool comp(const Type1 &a, const Type2 &b);
    The signature does not need to have const&, but the function must not modify the objects passed to it. The types Type1 and Type2 must be such that objects of types RandIter1 and RandIter2 can be dereferenced and then implicitly converted to both Type1 and Type2

Returns

The merge algorithm returns a hpx::future<RandIter3> > if the execution policy is of type sequenced_task_policy or parallel_task_policy and returns RandIter3 otherwise. The merge algorithm returns the destination iterator to the end of the dest range.

template<typename RandIter1, typename RandIter2, typename RandIter3, typename Comp = hpx::parallel::detail::less>
RandIter3 merge(RandIter1 first1, RandIter1 last1, RandIter2 first2, RandIter2 last2, RandIter3 dest, Comp &&comp = Comp())#

Merges two sorted ranges [first1, last1) and [first2, last2) into one sorted range beginning at dest. The order of equivalent elements in the each of original two ranges is preserved. For equivalent elements in the original two ranges, the elements from the first range precede the elements from the second range. The destination range cannot overlap with either of the input ranges.

Note

Complexity: Performs O(std::distance(first1, last1) + std::distance(first2, last2)) applications of the comparison comp and the each projection.

Template Parameters

  • RandIter1 – The type of the source iterators used (deduced) representing the first sorted range. This iterator type must meet the requirements of an random access iterator.

  • RandIter2 – The type of the source iterators used (deduced) representing the second sorted range. This iterator type must meet the requirements of an random access iterator.

  • RandIter3 – The type of the iterator representing the destination range (deduced). This iterator type must meet the requirements of an random access iterator.

  • Comp – The type of the function/function object to use (deduced). Unlike its sequential form, the parallel overload of merge requires Comp to meet the requirements of CopyConstructible. This defaults to std::less<>

Parameters

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

  • last1 – Refers to the end of the first range of elements the algorithm will be applied to.

  • first2 – Refers to the beginning of the second range of elements the algorithm will be applied to.

  • last2 – Refers to the end of the second range of elements the algorithm will be applied to.

  • dest – Refers to the beginning of the destination range.

  • comp – comp is a callable object which returns true if the first argument is less than the second, and false otherwise. The signature of this comparison should be equivalent to: 

    bool comp(const Type1 &a, const Type2 &b);
    The signature does not need to have const&, but the function must not modify the objects passed to it. The types Type1 and Type2 must be such that objects of types RandIter1 and RandIter2 can be dereferenced and then implicitly converted to both Type1 and Type2

Returns

The merge algorithm returns a RandIter3. The merge algorithm returns the destination iterator to the end of the dest range.

template<typename ExPolicy, typename RandIter, typename Comp = hpx::parallel::detail::less>
hpx::parallel::util::detail::algorithm_result_t<ExPolicy> inplace_merge(ExPolicy &&policy, RandIter first, RandIter middle, RandIter last, Comp &&comp = Comp())#

Merges two consecutive sorted ranges [first, middle) and [middle, last) into one sorted range [first, last). The order of equivalent elements in the each of original two ranges is preserved. For equivalent elements in the original two ranges, the elements from the first range precede the elements from the second range. Executed according to the policy.

The assignments in the parallel inplace_merge algorithm invoked with an execution policy object of type sequenced_policy execute in sequential order in the calling thread.

The assignments in the parallel inplace_merge 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: Performs O(std::distance(first, last)) applications of the comparison comp and the each 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 assignments.

  • RandIter – The type of the source iterators used (deduced). This iterator type must meet the requirements of an random access iterator.

  • Comp – The type of the function/function object to use (deduced). Unlike its sequential form, the parallel overload of inplace_merge requires Comp 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 first sorted range the algorithm will be applied to.

  • middle – Refers to the end of the first sorted range and the beginning of the second sorted range the algorithm will be applied to.

  • last – Refers to the end of the second sorted range the algorithm will be applied to.

  • comp – comp is a callable object which returns true if the first argument is less than the second, and false otherwise. The signature of this comparison should be equivalent to: 

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

Returns

The inplace_merge algorithm returns a hpx::future<void> if the execution policy is of type sequenced_task_policy or parallel_task_policy and returns void otherwise. The inplace_merge algorithm returns the source iterator last.

template<typename RandIter, typename Comp = hpx::parallel::detail::less>
void inplace_merge(RandIter first, RandIter middle, RandIter last, Comp &&comp = Comp())#

Merges two consecutive sorted ranges [first, middle) and [middle, last) into one sorted range [first, last). The order of equivalent elements in the each of original two ranges is preserved. For equivalent elements in the original two ranges, the elements from the first range precede the elements from the second range.

Note

Complexity: Performs O(std::distance(first, last)) applications of the comparison comp and the each projection.

Template Parameters

  • RandIter – The type of the source iterators used (deduced). This iterator type must meet the requirements of an random access iterator.

  • Comp – The type of the function/function object to use (deduced). Unlike its sequential form, the parallel overload of inplace_merge requires Comp to meet the requirements of CopyConstructible. This defaults to std::less<>

Parameters

  • first – Refers to the beginning of the first sorted range the algorithm will be applied to.

  • middle – Refers to the end of the first sorted range and the beginning of the second sorted range the algorithm will be applied to.

  • last – Refers to the end of the second sorted range the algorithm will be applied to.

  • comp – comp is a callable object which returns true if the first argument is less than the second, and false otherwise. The signature of this comparison should be equivalent to: 

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

Returns

The inplace_merge algorithm returns a void. The inplace_merge algorithm returns the source iterator last.