hpx/parallel/algorithms/lexicographical_compare.hpp#

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

namespace hpx

Functions

template<typename InIter1, typename InIter2, typename Pred = hpx::parallel::detail::less>
bool lexicographical_compare(InIter1 first1, InIter1 last1, InIter2 first2, InIter2 last2, Pred &&pred)#

Checks if the first range [first1, last1) is lexicographically less than the second range [first2, last2). uses a provided predicate to compare elements.

The comparison operations in the parallel lexicographical_compare algorithm invoked without an execution policy object execute in sequential order in the calling thread.

Note

Complexity: At most 2 * min(N1, N2) applications of the comparison operation, where N1 = std::distance(first1, last) and N2 = std::distance(first2, last2).

Note

Lexicographical comparison is an operation with the following properties

  • Two ranges are compared element by element

  • The first mismatching element defines which range is lexicographically less or greater than the other

  • If one range is a prefix of another, the shorter range is lexicographically less than the other

  • If two ranges have equivalent elements and are of the same length, then the ranges are lexicographically equal

  • An empty range is lexicographically less than any non-empty range

  • Two empty ranges are lexicographically equal

Template Parameters
  • InIter1 – The type of the source iterators used for the first range (deduced). This iterator type must meet the requirements of an input iterator.

  • InIter2 – The type of the source iterators used for the second range (deduced). This iterator type must meet the requirements of an input iterator.

  • Pred – The type of an optional function/function object to use. Unlike its sequential form, the parallel overload of lexicographical_compare requires Pred to meet the requirements of CopyConstructible. This defaults to std::less<>

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.

  • pred – Refers to the comparison function that the first and second ranges will be applied to

Returns

The lexicographically_compare algorithm returns a returns bool if the execution policy object is not passed in. The lexicographically_compare algorithm returns true if the first range is lexicographically less, otherwise it returns false. range [first2, last2), it returns false.

template<typename ExPolicy, typename FwdIter1, typename FwdIter2, typename Pred = hpx::parallel::detail::less>
hpx::parallel::util::detail::algorithm_result_t<ExPolicy, bool> lexicographical_compare(ExPolicy &&policy, FwdIter1 first1, FwdIter1 last1, FwdIter2 first2, FwdIter2 last2, Pred &&pred)#

Checks if the first range [first1, last1) is lexicographically less than the second range [first2, last2). uses a provided predicate to compare elements.

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

The comparison operations in the parallel lexicographical_compare 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 2 * min(N1, N2) applications of the comparison operation, where N1 = std::distance(first1, last) and N2 = std::distance(first2, last2).

Note

Lexicographical comparison is an operation with the following properties

  • Two ranges are compared element by element

  • The first mismatching element defines which range is lexicographically less or greater than the other

  • If one range is a prefix of another, the shorter range is lexicographically less than the other

  • If two ranges have equivalent elements and are of the same length, then the ranges are lexicographically equal

  • An empty range is lexicographically less than any non-empty range

  • Two empty ranges are lexicographically equal

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.

  • FwdIter1 – The type of the source iterators used for the first range (deduced). This iterator type must meet the requirements of an forward iterator.

  • FwdIter2 – The type of the source iterators used for the second range (deduced). This iterator type must meet the requirements of an forward iterator.

  • Pred – The type of an optional function/function object to use. Unlike its sequential form, the parallel overload of lexicographical_compare requires Pred 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 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.

  • pred – Refers to the comparison function that the first and second ranges will be applied to

Returns

The lexicographically_compare algorithm returns a hpx::future<bool> if the execution policy is of type sequenced_task_policy or parallel_task_policy and returns bool otherwise. The lexicographically_compare algorithm returns true if the first range is lexicographically less, otherwise it returns false. range [first2, last2), it returns false.