home | help 
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) (constexpr
     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) (constexpr
     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  overloads
     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 proper-
     ties:

	  * Two ranges are compared element by element.
	  * The first mismatching element defines which range  is  lexicographi-
     cally less or
	    greater than the other.
	  *  If  one  range is a prefix of another, the shorter range is lexico-
     graphically 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  satis-
     fies 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  regard-
     less 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 im-
     plicitly
			converted to both Type1 and Type2.

Type requirements
	-
	InputIt1, InputIt2 must meet the requirements of LegacyInputIterator.
	-
	ForwardIt1, ForwardIt2 must meet the requirements of LegacyForwardItera-
     tor.
	-
	Compare must meet the requirements of Compare.

Return value
	true if the first range is lexicographically less than the second,  oth-
     erwise 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 er-
     rors 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  other  ExecutionPolicy, the behavior is implementation-de-
     fined.
	  * 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, 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 <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		    Cor-
     rect behavior
			    at most \(\scriptsize \min(N_1,N_2)\)min(N
			    1,N
	LWG  142  C++98      2) comparisons were allowed, but that	    dou-
     bled 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  lexico-
     graphically
	(C++20) 			  less than another
					  (niebloid)

http://cppreference.com 	   2024.06.10	    std::lexico...cal_compare(3)
home | help