hpx/parallel/container_algorithms/merge.hpp#

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

namespace hpx

Top-level namespace.

namespace ranges

Functions

template<typename ExPolicy, typename Rng1, typename Rng2, typename Iter3, typename Comp = hpx::ranges::less, typename Proj1 = hpx::parallel::util::projection_identity, typename Proj2 = hpx::parallel::util::projection_identity>
hpx::parallel::util::detail::algorithm_result<ExPolicy, hpx::ranges::merge_result<typename hpx::traits::range_iterator<Rng1>::type, typename hpx::traits::range_iterator<Rng2>::type, Iter3>>::type merge(ExPolicy &&policy, Rng1 &&rng1, Rng2 &&rng2, Iter3 dest, Comp &&comp = Comp(), Proj1 &&proj1 = Proj1(), Proj2 &&proj2 = Proj2())#

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.

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.

  • Rng1 – The type of the first source range used (deduced). The iterators extracted from this range type must meet the requirements of an random access iterator.

  • Rng2 – The type of the second source range used (deduced). The iterators extracted from this range type must meet the requirements of an random access iterator.

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

  • Proj1 – The type of an optional projection function to be used for elements of the first range. This defaults to util::projection_identity

  • Proj2 – The type of an optional projection function to be used for elements of the second range. This defaults to util::projection_identity

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

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

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

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

  • compcomp 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 Iter1 and Iter2 can be dereferenced and then implicitly converted to both Type1 and Type2

  • proj1 – Specifies the function (or function object) which will be invoked for each of the elements of the first range as a projection operation before the actual comparison comp is invoked.

  • proj2 – Specifies the function (or function object) which will be invoked for each of the elements of the second range as a projection operation before the actual comparison comp is invoked.

Returns

The merge algorithm returns a hpx::future<merge_result<Iter1, Iter2, Iter3>> if the execution policy is of type sequenced_task_policy or parallel_task_policy and returns merge_result<Iter1, Iter2, Iter3> otherwise. The merge algorithm returns the tuple of the source iterator last1, the source iterator last2, the destination iterator to the end of the dest range.

template<typename ExPolicy, typename Iter1, typename Sent1, typename Iter2, typename Sent2, typename Iter3, typename Comp = hpx::ranges::less, typename Proj1 = hpx::parallel::util::projection_identity, typename Proj2 = hpx::parallel::util::projection_identity>
hpx::parallel::util::detail::algorithm_result<ExPolicy, hpx::ranges::merge_result<Iter1, Iter2, Iter3>>::type merge(ExPolicy &&policy, Iter1 first1, Sent1 last1, Iter2 first2, Sent2 last2, Iter3 dest, Comp &&comp = Comp(), Proj1 &&proj1 = Proj1(), Proj2 &&proj2 = Proj2())#

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.

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.

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

  • Sent1 – The type of the end source iterators used (deduced). This iterator type must meet the requirements of an sentinel for Iter1.

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

  • Sent2 – The type of the end source iterators used (deduced) representing the second sequence. This iterator type must meet the requirements of an sentinel for Iter2.

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

  • Proj1 – The type of an optional projection function to be used for elements of the first range. This defaults to util::projection_identity

  • Proj2 – The type of an optional projection function to be used for elements of the second range. This defaults to util::projection_identity

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

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

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

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

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

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

  • compcomp 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 Iter1 and Iter2 can be dereferenced and then implicitly converted to both Type1 and Type2

  • proj1 – Specifies the function (or function object) which will be invoked for each of the elements of the first range as a projection operation before the actual comparison comp is invoked.

  • proj2 – Specifies the function (or function object) which will be invoked for each of the elements of the second range as a projection operation before the actual comparison comp is invoked.

Returns

The merge algorithm returns a hpx::future<merge_result<Iter1, Iter2, Iter3>> if the execution policy is of type sequenced_task_policy or parallel_task_policy and returns merge_result<Iter1, Iter2, Iter3> otherwise. The merge algorithm returns the tuple of the source iterator last1, the source iterator last2, the destination iterator to the end of the dest range.

template<typename Rng1, typename Rng2, typename Iter3, typename Comp = hpx::ranges::less, typename Proj1 = hpx::parallel::util::projection_identity, typename Proj2 = hpx::parallel::util::projection_identity>
hpx::ranges::merge_result<typename hpx::traits::range_iterator<Rng1>::type, typename hpx::traits::range_iterator<Rng2>::type, Iter3> merge(Rng1 &&rng1, Rng2 &&rng2, Iter3 dest, Comp &&comp = Comp(), Proj1 &&proj1 = Proj1(), Proj2 &&proj2 = Proj2())#

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
  • Rng1 – The type of the first source range used (deduced). The iterators extracted from this range type must meet the requirements of an random access iterator.

  • Rng2 – The type of the second source range used (deduced). The iterators extracted from this range type must meet the requirements of an random access iterator.

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

  • Proj1 – The type of an optional projection function to be used for elements of the first range. This defaults to util::projection_identity

  • Proj2 – The type of an optional projection function to be used for elements of the second range. This defaults to util::projection_identity

Parameters
  • rng1 – Refers to the first range of elements the algorithm will be applied to.

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

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

  • compcomp 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 Iter1 and Iter2 can be dereferenced and then implicitly converted to both Type1 and Type2

  • proj1 – Specifies the function (or function object) which will be invoked for each of the elements of the first range as a projection operation before the actual comparison comp is invoked.

  • proj2 – Specifies the function (or function object) which will be invoked for each of the elements of the second range as a projection operation before the actual comparison comp is invoked.

Returns

The merge algorithm returns merge_result<Iter1, Iter2, Iter3>. The merge algorithm returns the tuple of the source iterator last1, the source iterator last2, the destination iterator to the end of the dest range.

template<typename Iter1, typename Sent1, typename Iter2, typename Sent2, typename Iter3, typename Comp = hpx::ranges::less, typename Proj1 = hpx::parallel::util::projection_identity, typename Proj2 = hpx::parallel::util::projection_identity>
hpx::ranges::merge_result<Iter1, Iter2, Iter3> merge(Iter1 first1, Sent1 last1, Iter2 first2, Sent2 last2, Iter3 dest, Comp &&comp = Comp(), Proj1 &&proj1 = Proj1(), Proj2 &&proj2 = Proj2())#

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
  • Iter1 – The type of the source iterators used (deduced) representing the first sequence. This iterator type must meet the requirements of an random access iterator.

  • Sent1 – The type of the end source iterators used (deduced). This iterator type must meet the requirements of an sentinel for Iter1.

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

  • Sent2 – The type of the end source iterators used (deduced) representing the second sequence. This iterator type must meet the requirements of an sentinel for Iter2.

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

  • Proj1 – The type of an optional projection function to be used for elements of the first range. This defaults to util::projection_identity

  • Proj2 – The type of an optional projection function to be used for elements of the second range. This defaults to util::projection_identity

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

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

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

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

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

  • compcomp 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 Iter1 and Iter2 can be dereferenced and then implicitly converted to both Type1 and Type2

  • proj1 – Specifies the function (or function object) which will be invoked for each of the elements of the first range as a projection operation before the actual comparison comp is invoked.

  • proj2 – Specifies the function (or function object) which will be invoked for each of the elements of the second range as a projection operation before the actual comparison comp is invoked.

Returns

The merge algorithm returns merge_result<Iter1, Iter2, Iter3>. The merge algorithm returns the tuple of the source iterator last1, the source iterator last2, the destination iterator to the end of the dest range.

template<typename ExPolicy, typename Rng, typename Iter, typename Comp = hpx::ranges::less, typename Proj = hpx::parallel::util::projection_identity>
hpx::parallel::util::detail::algorithm_result<ExPolicy, Iter>::type inplace_merge(ExPolicy &&policy, Rng &&rng, Iter middle, Comp &&comp = Comp(), Proj &&proj = Proj())#

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.

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.

  • Rng – The type of the source range used (deduced). The iterators extracted from this range type must meet the requirements of an random access iterator.

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

  • 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 range of elements 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.

  • compcomp 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 Iter can be dereferenced and then implicitly converted to both Type1 and Type2

  • proj – Specifies the function (or function object) which will be invoked for each of the elements as a projection operation before the actual predicate is invoked.

Returns

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

template<typename ExPolicy, typename Iter, typename Sent, typename Comp = hpx::ranges::less, typename Proj = hpx::parallel::util::projection_identity>
hpx::parallel::util::detail::algorithm_result<ExPolicy, Iter>::type inplace_merge(ExPolicy &&policy, Iter first, Iter middle, Sent last, Comp &&comp = Comp(), Proj &&proj = Proj())#

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.

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.

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

  • Sent – The type of the end source iterators used (deduced). This iterator type must meet the requirements of an sentinel for Iter1.

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

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

  • compcomp 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 Iter can be dereferenced and then implicitly converted to both Type1 and Type2

  • proj – Specifies the function (or function object) which will be invoked for each of the elements as a projection operation before the actual predicate is invoked.

Returns

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

template<typename Rng, typename Iter, typename Comp = hpx::ranges::less, typename Proj = hpx::parallel::util::projection_identity>
Iter inplace_merge(Rng &&rng, Iter middle, Comp &&comp = Comp(), Proj &&proj = Proj())#

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
  • Rng – The type of the source range used (deduced). The iterators extracted from this range type must meet the requirements of an random access iterator.

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

  • Proj – The type of an optional projection function. This defaults to util::projection_identity

Parameters
  • rng – Refers to the range of elements 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.

  • compcomp 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 Iter can be dereferenced and then implicitly converted to both Type1 and Type2

  • proj – Specifies the function (or function object) which will be invoked for each of the elements as a projection operation before the actual predicate is invoked.

Returns

The inplace_merge algorithm returns Iter. The inplace_merge algorithm returns the source iterator last

template<typename Iter, typename Sent, typename Comp = hpx::ranges::less, typename Proj = hpx::parallel::util::projection_identity>
Iter inplace_merge(Iter first, Iter middle, Sent last, Comp &&comp = Comp(), Proj &&proj = Proj())#

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
  • Iter – The type of the source iterators used (deduced). This iterator type must meet the requirements of an random access iterator.

  • Sent – The type of the end source iterators used (deduced). This iterator type must meet the requirements of an sentinel for Iter1.

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

  • Proj – The type of an optional projection function. This defaults to util::projection_identity

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.

  • compcomp 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 Iter can be dereferenced and then implicitly converted to both Type1 and Type2

  • proj – Specifies the function (or function object) which will be invoked for each of the elements as a projection operation before the actual predicate is invoked.

Returns

The inplace_merge algorithm Iter. The inplace_merge algorithm returns the source iterator last