std::ranges::lexicographical_compare() algorithm
- since C++20
- Simplified
- Detailed
// (1)
constexpr bool
lexicographical_compare( I1 first1, S1 last1, I2 first2, S2 last2,
Comp comp = {}, Proj1 proj1 = {}, Proj2 proj2 = {} );
// (2)
constexpr bool lexicographical_compare( R1&& r1, R2&& r2, Comp comp = {},
Proj1 proj1 = {}, Proj2 proj2 = {} );
The type of arguments are generic and have the following constraints:
-
I1
,I2
-std::input_iterator
-
S1
,S2
-std::sentinel_for<I1>
,std::sentinel_for<I2>
-
R1
,R2
-std::ranges::input_range
-
Comp
:- (1) -
std::indirect_strict_weak_order<std::projected<I1, Proj1>, std::projected<I2, Proj2>>
- (2) -
std::indirect_strict_weak_order<std::projected<ranges::iterator_t<R1>, Proj1>, std::projected<ranges::iterator_t<R2>, Proj2>
- (1) -
-
Proj1
,Proj2
- (none)
The Proj1
, Proj2
and Pred
template arguments have the following default types: std::identity
, ranges::less
for all overloads.
Additionally, each overload has the following constraints:
- (1) -
std::indirectly_comparable<I1, I2, Pred, Proj1, Proj2>
- (2) -
std::indirectly_comparable<ranges::iterator_t<R1>, ranges::iterator_t<R2>, Pred, Proj1, Proj2>
// (1)
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
lexicographical_compare( I1 first1, S1 last1, I2 first2, S2 last2,
Comp comp = {}, Proj1 proj1 = {}, Proj2 proj2 = {} );
// (2)
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 lexicographical_compare( R1&& r1, R2&& r2, Comp comp = {},
Proj1 proj1 = {}, Proj2 proj2 = {} );
Checks if the first range [first1
; last1
) is lexicographically less than the second range [first2
; last2
).
-
(1) Elements are compared using the given binary comparison function
comp
. -
(2) Same as (1), but uses
r
as the source range, as if usingranges::begin(r)
as first andranges::end(r)
aslast
.
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.
The function-like entities described on this page are niebloids.
Parameters
first1 last1 | The first range of elements to compare. |
r1 | The first range of elements to compare. |
first2 last2 | The second range of elements to compare. |
r2 | The first range of elements to compare. |
comp | Comparison function to apply to the projected elements. |
proj1 | Projection to apply to the elements of the first range. |
proj2 | Projection to apply to the elements of the first range. |
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
(none)
Possible implementation
ranges::lexicographical_compare
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.