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, InputIt1 last1, (1) (const- expr since C++20) InputIt2 first2, InputIt2 last2 ); template< class ExecutionPolicy, class ForwardIt1, class ForwardIt2 > bool lexicographical_compare( ExecutionPolicy&& policy, ForwardIt1 first1, (2) (since C++17) ForwardIt1 last1, ForwardIt2 first2, ForwardIt2 last2 ); template< class InputIt1, class InputIt2, class Compare > bool lexicographical_compare( InputIt1 first1, InputIt1 last1, (3) (const- expr since C++20) InputIt2 first2, InputIt2 last2, Compare comp ); template< class ExecutionPolicy, class ForwardIt1, class ForwardIt2, class Compare > bool lexicographical_compare( ExecutionPolicy&& policy, ForwardIt1 first1, (4) (since C++17) 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 participate in overload resolution only if std::is_execution_policy_v<std::decay_t<ExecutionPolicy>> is true. (until C++20) std::is_execution_policy_v<std::remove_cvref_t<ExecutionPolicy>> is true. (since C++20) 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. - Compare must meet the requirements of Compare. Return value true if the first range is lexicographically less than the second, otherwise false. Complexity Given \(\scriptsize N_1\)N 1 as std::distance(first1, last1) and \(\scriptsize N_2\)N 2 as std::distance(first2, last2): 1,2) At most \(\scriptsize 2\min(N_1,N_2)\)2min( 1,N 2) comparisons using operator<. 3,4) At most \(\scriptsize 2\min(N_1,N_2)\)2min(N 1,N 2) applications of the comparison function comp. 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 lexicographical_compare (1) 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); } lexicographical_compare (3) template<class InputIt1, class InputIt2, class Compare> bool lexicographical_compare(InputIt1 first1, InputIt1 last1, InputIt2 first2, InputIt2 last2, Com- pare 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 <random> #include <vector> void print(const std::vector<char>& v, auto suffix) { for (char c : v) std::cout << c << ' '; std::cout << suffix; } int main() { std::vector<char> v1{'a', 'b', 'c', 'd'}; std::vector<char> v2{'a', 'b', 'c', 'd'}; for (std::mt19937 g{std::random_device{}()}; !std::lexicographical_compare(v1.begin(), v1.end(), v2.begin(), v2.end());) { print(v1, ">= "); print(v2, '\n'); std::shuffle(v1.begin(), v1.end(), g); std::shuffle(v2.begin(), v2.end(), g); } print(v1, "< "); print(v2, '\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 Defect reports The following behavior-changing defect reports were applied retroac- tively to previously published C++ standards. DR Applied to Behavior as published Correct behavior at most \(\scriptsize \min(N_1,N_2)\)min(N 1,N LWG 142 C++98 2) comparisons were allowed, but that doubled the limit is not possible (equivalence is determined by 2 comparisons) LWG 1205 C++98 the results of lexicographical comparisons made clear involving empty ranges were unclear See also equal determines if two sets of elements are the same (function template) lexicographical_compare_three_way compares two ranges using three- way comparison (C++20) (function template) ranges::lexicographical_compare returns true if one range is lexi- cographically (C++20) less than another (niebloid) http://cppreference.com 2024.06.10 std::lexico...cal_compare(3)
NAME | Synopsis | Parameters | Type requirements | Return value | Complexity | Exceptions | Possible implementation | 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.1.quarterly>