std::lexicographical_compare_three_way
From cppreference.com
| Defined in header <algorithm>
|
||
template< class InputIt1, class InputIt2, class Cmp >
constexpr auto lexicographical_compare_three_way
( InputIt1 first1, InputIt1 last1, InputIt2 first2, InputIt2 last2,
Cmp comp ) -> decltype(comp(*first1, *first2));
|
(1) | (since C++20) |
template< class InputIt1, class InputIt2 >
constexpr auto lexicographical_compare_three_way
( InputIt1 first1, InputIt1 last1, InputIt2 first2, InputIt2 last2 );
|
(2) | (since C++20) |
Checks the lexicographical order between the two target ranges [first1, last1) and [first2, last2) using three-way comparison.
1) Elements are compared using
comp.2) Elements are compared using
std::compare_three_way().Lexicographical comparison is an operation with the following properties:
- Two empty ranges are lexicographically equal.
- An empty range is lexicographically less than any non-empty range.
- Non-empty ranges are compared element by element:
- The first pair of mismatching elements defines which range is lexicographically less or greater than the other.
- If two ranges have equivalent elements and are of the same length, then the ranges are lexicographically equal.
- If one range is a prefix of another, the shorter range is lexicographically less than the other.
If the return type is not one of the three comparison category types, the program is ill-formed:
Parameters
| first1, last1 | - | the pair of iterators defining the first target range |
| first2, last2 | - | the pair of iterators defining the second target range |
| comp | - | the three-way comparator |
| Type requirements | ||
-InputIt1, InputIt2 must meet the requirements of LegacyInputIterator.
| ||
Return value
The result of three-way comparison between the first pair of mismatching elements, or std::distance(first1, last1) <=> std::distance(first2, last2) is no such elements exist.
Complexity
Given
- N1 as
std::distance(first1, last1)， - N2 as
std::distance(first2, last2):
1) At most min(1,N2) applications of
comp.2) At most min(N1,N2) applications of
std::compare_three_way().Possible implementation
template<class I1, class I2, class Cmp>
constexpr auto lexicographical_compare_three_way(I1 f1, I1 l1, I2 f2, I2 l2, Cmp comp)
-> decltype(comp(*f1, *f2))
{
using ret_t = decltype(comp(*f1, *f2));
static_assert(std::disjunction_v
<std::is_same<ret_t, std::strong_ordering>,
std::is_same<ret_t, std::weak_ordering>,
std::is_same<ret_t, std::partial_ordering>>,
"The return type must be a comparison category type.");
bool exhaust1 = (f1 == l1);
bool exhaust2 = (f2 == l2);
for (; !exhaust1 && !exhaust2; exhaust1 = (++f1 == l1), exhaust2 = (++f2 == l2))
if (auto c = comp(*f1, *f2); c != 0)
return c;
return !exhaust1 ? std::strong_ordering::greater:
!exhaust2 ? std::strong_ordering::less:
std::strong_ordering::equal;
}
|
Example
Run this code
#include <algorithm>
#include <cctype>
#include <compare>
#include <iomanip>
#include <iostream>
#include <string_view>
#include <utility>
using namespace std::literals;
void show_result(std::string_view s1, std::string_view s2, std::strong_ordering o)
{
std::cout << std::quoted(s1) << " is ";
std::is_lt(o) ? std::cout << "less than ":
std::is_gt(o) ? std::cout << "greater than ":
std::cout << "equal to ";
std::cout << std::quoted(s2) << '\n';
}
std::strong_ordering cmp_icase(unsigned char x, unsigned char y)
{
return std::toupper(x) <=> std::toupper(y);
};
int main()
{
for (const auto& [s1, s2] :
{
std::pair{"one"sv, "ONE"sv}, {"two"sv, "four"sv}, {"three"sv, "two"sv}
})
{
const auto res = std::lexicographical_compare_three_way(
s1.cbegin(), s1.cend(), s2.cbegin(), s2.cend(), cmp_icase);
show_result(s1, s2, res);
}
}
Output:
"one" is equal to "ONE"
"two" is greater than "four"
"three" is less than "two"
Defect reports
The following behavior-changing defect reports were applied retroactively to previously published C++ standards.
| DR | Applied to | Behavior as published | Correct behavior |
|---|---|---|---|
| LWG 3410 | C++20 | extraneous comparisons between iterators were required | such requirement removed |
See also
| compares two ranges lexicographically (function template & algorithm function object) | |
(C++20) |
constrained function object implementing x <=> y (class) |