std::lexicographical_compare() algorithm
- since C++20
- since C++17
- until C++17
// (1)
template< class InputIt1, class InputIt2 >
constexpr bool lexicographical_compare( InputIt1 first1, InputIt1 last1, InputIt2 first2, InputIt2 last2 );
// (2)
template< class InputIt1, class InputIt2, class Compare >
constexpr bool lexicographical_compare( InputIt1 first1, InputIt1 last1, InputIt2 first2, InputIt2 last2, Compare comp );
// (3)
template< class ExecutionPolicy, class ForwardIt1, class ForwardIt2 >
bool lexicographical_compare( ExecutionPolicy&& policy,
ForwardIt1 first1, ForwardIt1 last1,
ForwardIt2 first2, ForwardIt2 last2 );
// (4)
template< class ExecutionPolicy, class ForwardIt1, class ForwardIt2, class Compare >
bool lexicographical_compare( ExecutionPolicy&& policy,
ForwardIt1 first1, ForwardIt1 last1,
ForwardIt2 first2, ForwardIt2 last2,
Compare comp );
// (1)
template< class InputIt1, class InputIt2 >
bool lexicographical_compare( InputIt1 first1, InputIt1 last1, InputIt2 first2, InputIt2 last2 );
// (2)
template< class InputIt1, class InputIt2, class Compare >
bool lexicographical_compare( InputIt1 first1, InputIt1 last1, InputIt2 first2, InputIt2 last2, Compare comp );
// (3)
template< class ExecutionPolicy, class ForwardIt1, class ForwardIt2 >
bool lexicographical_compare( ExecutionPolicy&& policy,
ForwardIt1 first1, ForwardIt1 last1,
ForwardIt2 first2, ForwardIt2 last2 );
// (4)
template< class ExecutionPolicy, class ForwardIt1, class ForwardIt2, class Compare >
bool lexicographical_compare( ExecutionPolicy&& policy,
ForwardIt1 first1, ForwardIt1 last1,
ForwardIt2 first2, ForwardIt2 last2,
Compare comp );
// (1)
template< class InputIt1, class InputIt2 >
bool lexicographical_compare( InputIt1 first1, InputIt1 last1, InputIt2 first2, InputIt2 last2 );
// (2)
template< class InputIt1, class InputIt2, class Compare >
bool lexicographical_compare( InputIt1 first1, InputIt1 last1, InputIt2 first2, InputIt2 last2, Compare comp );
Checks if the first range [first1
; last1
) is lexicographically less than the second range [first2
; last2
).
-
(1) Elements are compared using
operator<
. -
(2) Elements are compared using the given binary comparison function
comp
. -
(2 - 4) Same as (1), but executed according to
policy
.Overload ResolutionThese overloads participate in overload resolution only if
std::is_execution_policy_v<std::decay_t<ExecutionPolicy>>
(until C++20)std::is_execution_policy_v<std::remove_cvref_t<ExecutionPolicy>>
(since C++20) istrue
.
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.
Parameters
first1 last1 | The first range of elements compare. |
r1 | The first range of elements compare. |
first2 last2 | The second range of elements compare. |
r2 | The second range of elements compare. |
proj1 | Projection to apply to the elements of the first range. |
proj2 | Projection to apply to the elements of the second range. |
comp | Comparison function object (i.e. an object that satisfies the requirements of Compare),
which returns The signature of the comparison function should be equivalent to the following:
|
Type requirements
InputIt1 InputIt2 | LegacyInputIterator |
ForwardIt1 ForwardIt2 | LegacyForwardIterator |
Compare | Compare |
Return value
true
if the first range is lexicographically less than the second..
Complexity
Given N1
as ranges::distance(first1, last1)
and N2
as ranges::distance(first2, last2)
At most 2 * min(N1, N2) applications of the comparison and corresponding projections.
Exceptions
The overloads with a template parameter named ExecutionPolicy
report errors as follows:
- If execution of a function invoked as part of the algorithm throws an exception and
ExecutionPolicy
is one of the standard policies,std::terminate
is called. For any otherExecutionPolicy
, the behavior is implementation-defined. - If the algorithm fails to allocate memory,
std::bad_alloc
is thrown.
Possible implementation
lexicographical_compare(1) and lexicographical_compare(2)
struct lexicographical_compare_fn
{
template<std::input_iterator I1, std::sentinel_for<I1> S1,
std::input_iterator I2, std::sentinel_for<I2> S2,
class Proj1 = std::identity, class Proj2 = std::identity,
std::indirect_strict_weak_order<
std::projected<I1, Proj1>,
std::projected<I2, Proj2>> Comp = ranges::less>
constexpr bool operator()(I1 first1, S1 last1, I2 first2, S2 last2,
Comp comp = {}, Proj1 proj1 = {}, Proj2 proj2 = {}) const
{
for (; (first1 != last1) && (first2 != last2); ++first1, (void) ++first2)
{
if (std::invoke(comp, std::invoke(proj1, *first1), std::invoke(proj2, *first2)))
return true;
if (std::invoke(comp, std::invoke(proj2, *first2), std::invoke(proj1, *first1)))
return false;
}
return (first1 == last1) && (first2 != last2);
}
template<ranges::input_range R1, ranges::input_range R2,
class Proj1 = std::identity, class Proj2 = std::identity,
std::indirect_strict_weak_order<
std::projected<ranges::iterator_t<R1>, Proj1>,
std::projected<ranges::iterator_t<R2>, Proj2>> Comp = ranges::less>
constexpr bool operator()(R1&& r1, R2&& r2, Comp comp = {},
Proj1 proj1 = {}, Proj2 proj2 = {}) const
{
return (*this)(ranges::begin(r1), ranges::end(r1),
ranges::begin(r2), ranges::end(r2),
std::ref(comp), std::ref(proj1), std::ref(proj2));
}
};
inline constexpr lexicographical_compare_fn lexicographical_compare;
Examples
#include <algorithm>
#include <iostream>
#include <iterator>
#include <random>
#include <vector>
int main()
{
std::vector<char> v1 {'a', 'b', 'c', 'd'};
std::vector<char> v2 {'a', 'b', 'c', 'd'};
namespace ranges = std::ranges;
auto os = std::ostream_iterator<char>(std::cout, " ");
std::mt19937 g {std::random_device {}()};
while (not ranges::lexicographical_compare(v1, v2))
{
ranges::copy(v1, os);
std::cout << ">= ";
ranges::copy(v2, os);
std::cout << '\n';
ranges::shuffle(v1, g);
ranges::shuffle(v2, g);
}
ranges::copy(v1, os);
std::cout << "< ";
ranges::copy(v2, os);
std::cout << '\n';
}
a b c d >= a b c d
d a b c >= c b d a
b d a c >= a d c b
a c d b < c d a b
Hover to see the original license.