STL之lexicographical_compare

//--------------------------------------------------
// lexicographical_compare and lexicographical_compare_3way.
// (the latter is not part of the C++ standard.)

/*功能：Returns true if the range [first1,last1) compares lexicographically less than the range [first2,last2).
default (1)	
	template <class InputIterator1, class InputIterator2>
	bool lexicographical_compare (InputIterator1 first1, InputIterator1 last1,
                                InputIterator2 first2, InputIterator2 last2);
custom (2)	
	template <class InputIterator1, class InputIterator2, class Compare>
	bool lexicographical_compare (InputIterator1 first1, InputIterator1 last1,
                                InputIterator2 first2, InputIterator2 last2,
                                Compare comp);
*/
/*
对两个序列[first1,last1)和[first2,last2)进行比较，比较操作针对两个序列对应位置上的元素进行；
并持续到：
（1）某一组对应元素不相等
（2）同时达到last1和last2(即两个序列大小相等)
（3）达到last1或last2(两个序列大小不相等)
*/

//版本一：默认比较操作为less
template <class _InputIter1, class _InputIter2>
bool lexicographical_compare(_InputIter1 __first1, _InputIter1 __last1,
                             _InputIter2 __first2, _InputIter2 __last2) {
  __STL_REQUIRES(_InputIter1, _InputIterator);
  __STL_REQUIRES(_InputIter2, _InputIterator);
  __STL_REQUIRES(typename iterator_traits<_InputIter1>::value_type,
                 _LessThanComparable);
  __STL_REQUIRES(typename iterator_traits<_InputIter2>::value_type,
                 _LessThanComparable);
  //以下任何一个序列到达尾端，则结束，否则两序列就相应元素进行比较
  for ( ; __first1 != __last1 && __first2 != __last2
        ; ++__first1, ++__first2) {
    if (*__first1 < *__first2)//若第一序列对应元素小于第二序列对应元素
      return true;//返回TRUE
    if (*__first2 < *__first1)//若第二序列对应元素小于第一序列对应元素
      return false;//返回FALSE
	//若两序列对应元素相等，则继续进入下一组对应元素比较
  }
  //如果第一序列已到达尾端，而第二序列还存在元素，则第一序列小于第二序列
  return __first1 == __last1 && __first2 != __last2;
}

//版本二：用户可自行指定比较规则
template <class _InputIter1, class _InputIter2, class _Compare>
bool lexicographical_compare(_InputIter1 __first1, _InputIter1 __last1,
                             _InputIter2 __first2, _InputIter2 __last2,
                             _Compare __comp) {
  __STL_REQUIRES(_InputIter1, _InputIterator);
  __STL_REQUIRES(_InputIter2, _InputIterator);
  //以下任何一个序列到达尾端，则结束，否则两序列就相应元素进行比较
  for ( ; __first1 != __last1 && __first2 != __last2
        ; ++__first1, ++__first2) {
    if (__comp(*__first1, *__first2))//若第一序列对应元素符合规则于第二序列对应元素
      return true;//返回TRUE
    if (__comp(*__first2, *__first1))//若第二序列对应元素符合规则于第一序列对应元素
      return false;//返回FALSE
	//若两序列对应元素相等，则继续进入下一组对应元素比较
  }
  //如果第一序列已到达尾端，而第二序列还存在元素，则第一序列符合规则于第二序列
  return __first1 == __last1 && __first2 != __last2;
}

//这是针对const unsigned cahr*的特化版本
inline bool 
lexicographical_compare(const unsigned char* __first1,
                        const unsigned char* __last1,
                        const unsigned char* __first2,
                        const unsigned char* __last2)
{
  const size_t __len1 = __last1 - __first1;//第一序列长度
  const size_t __len2 = __last2 - __first2;//第二序列长度
  //先比较长度相同的一小段
  /*
  memcmp函数的描述：
  原型：int memcmp ( const void * ptr1, const void * ptr2, size_t num );

Compares the first num bytes of the block of memory pointed by ptr1 to the first num bytes pointed by ptr2, 
returning zero if they all match or a value different from zero representing which is greater if they do not.
  */
  const int __result = memcmp(__first1, __first2, min(__len1, __len2));
  //根据返回结果result的值与0比较进行判断
  //result<0：第一序列小于第二序列
  //result>0：第一序列大于第二序列
  //result=0：两个序列相等
  return __result != 0 ? __result < 0 : __len1 < __len2;
}