FreeBSD Manual Pages
std::lexico...cal_compare(3) C++ Standard Libary std::lexico...cal_compare(3) NAME std::lexicographical_compare - std::lexicographical_compare Synopsis Defined in header <algorithm> template< class InputIt1, class InputIt2 > bool lexicographical_compare( InputIt1 first1, (until C++20) InputIt1 last1, InputIt2 first2, InputIt2 last2 ); template< class InputIt1, class InputIt2 > constexpr bool lexicographical_compare( InputIt1 (since C++20) first1, InputIt1 last1, InputIt2 first2, InputIt2 last2 ); template< class ExecutionPolicy, class ForwardIt1, class ForwardIt2 > bool lexicographical_compare( ExecutionPolicy&& (2) (since C++17) policy, ForwardIt1 first1, ForwardIt1 last1, ForwardIt2 first2, ForwardIt2 last2 ); template< class InputIt1, class InputIt2, class Compare > (1) bool lexicographical_compare( InputIt1 first1, (until C++20) InputIt1 last1, InputIt2 first2, InputIt2 last2, Compare comp ); template< class InputIt1, class InputIt2, class Compare > constexpr bool lexicographical_compare( InputIt1 (3) (since C++20) first1, InputIt1 last1, InputIt2 first2, InputIt2 last2, Compare comp ); template< class ExecutionPolicy, class ForwardIt1, class ForwardIt2, class Compare > bool lexicographical_compare( ExecutionPolicy&& (4) (since C++17) policy, ForwardIt1 first1, ForwardIt1 last1, ForwardIt2 first2, ForwardIt2 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<. 3) Elements are compared using the given binary comparison function comp. 2,4) Same as (1,3), but executed according to policy. These over- loads do not participate in overload resolution unless 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) is true. Lexicographical comparison is an operation with the following prop- erties: * Two ranges are compared element by element. * The first mismatching element defines which range is lexico- graphically less or greater than the other. * If one range is a prefix of another, the shorter range is lexi- cographically 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 to examine first2, last2 - the second range of elements to examine policy - the execution policy to use. See execution policy for details. comparison function object (i.e. an object that sat- isfies the requirements of Compare) which returns true if the first argument is less than the second. The signature of the comparison function should be equivalent to the following: bool cmp(const Type1 &a, const Type2 &b); comp - While the signature does not need to have const &, the function must not modify the objects passed to it and must be able to accept all values of type (possibly const) Type1 and Type2 re- gardless of value category (thus, Type1 & is not allowed , nor is Type1 unless for Type1 a move is equivalent to a copy (since C++11)). The types Type1 and Type2 must be such that objects of types InputIt1 and InputIt2 can be dereferenced and then implicitly converted to both Type1 and Type2. Type requirements - InputIt1, InputIt2 must meet the requirements of LegacyInputItera- tor. - ForwardIt1, ForwardIt2 must meet the requirements of LegacyFor- wardIterator. Return value true if the first range is lexicographically less than the second. Complexity At most 2min(N1, N2) applications of the comparison operation, where N1 = std::distance(first1, last1) and N2 = std::distance(first2, last2). 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::termi- nate is called. For any other ExecutionPolicy, the behavior is implementation- defined. * If the algorithm fails to allocate memory, std::bad_alloc is thrown. Possible implementation First version template<class InputIt1, class InputIt2> bool lexicographical_compare(InputIt1 first1, InputIt1 last1, InputIt2 first2, InputIt2 last2) { for ( ; (first1 != last1) && (first2 != last2); ++first1, (void) ++first2 ) { if (*first1 < *first2) return true; if (*first2 < *first1) return false; } return (first1 == last1) && (first2 != last2); } Second version template<class InputIt1, class InputIt2, class Compare> bool lexicographical_compare(InputIt1 first1, InputIt1 last1, InputIt2 first2, InputIt2 last2, Compare comp) { for ( ; (first1 != last1) && (first2 != last2); ++first1, (void) ++first2 ) { if (comp(*first1, *first2)) return true; if (comp(*first2, *first1)) return false; } return (first1 == last1) && (first2 != last2); } Example // Run this code #include <algorithm> #include <iostream> #include <vector> #include <random> int main() { std::vector<char> v1 {'a', 'b', 'c', 'd'}; std::vector<char> v2 {'a', 'b', 'c', 'd'}; std::mt19937 g{std::random_device{}()}; while (!std::lexicographical_compare(v1.begin(), v1.end(), v2.begin(), v2.end())) { for (auto c : v1) std::cout << c << ' '; std::cout << ">= "; for (auto c : v2) std::cout << c << ' '; std::cout << '\n'; std::shuffle(v1.begin(), v1.end(), g); std::shuffle(v2.begin(), v2.end(), g); } for (auto c : v1) std::cout << c << ' '; std::cout << "< "; for (auto c : v2) std::cout << c << ' '; std::cout << '\n'; } Possible output: 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 See also equal determines if two sets of elements are the same (function template) ranges::lexicographical_compare returns true if one range is lexico- graphically less (C++20) than another (niebloid) http://cppreference.com 2022.07.31 std::lexico...cal_compare(3)
NAME | Synopsis | Parameters | Type requirements | Return value | Complexity | Exceptions | Possible implementation | First version | Second version | Example | Possible output: | See also
Want to link to this manual page? Use this URL:
<https://man.freebsd.org/cgi/man.cgi?query=std::lexicographical_compare&sektion=3&manpath=FreeBSD+Ports+15.0>