stl_alg1.h
上传用户:nizebo
上传日期:2022-05-14
资源大小:882k
文件大小:24k
源码类别:

STL

开发平台:

Visual C++

  1. /*
  2.  *
  3.  * Copyright (c) 1994
  4.  * Hewlett-Packard Company
  5.  *
  6.  * Permission to use, copy, modify, distribute and sell this software
  7.  * and its documentation for any purpose is hereby granted without fee,
  8.  * provided that the above copyright notice appear in all copies and
  9.  * that both that copyright notice and this permission notice appear
  10.  * in supporting documentation.  Hewlett-Packard Company makes no
  11.  * representations about the suitability of this software for any
  12.  * purpose.  It is provided "as is" without express or implied warranty.
  13.  *
  14.  *
  15.  * Copyright (c) 1996-1998
  16.  * Silicon Graphics Computer Systems, Inc.
  17.  *
  18.  * Permission to use, copy, modify, distribute and sell this software
  19.  * and its documentation for any purpose is hereby granted without fee,
  20.  * provided that the above copyright notice appear in all copies and
  21.  * that both that copyright notice and this permission notice appear
  22.  * in supporting documentation.  Silicon Graphics makes no
  23.  * representations about the suitability of this software for any
  24.  * purpose.  It is provided "as is" without express or implied warranty.
  25.  */
  26. /* NOTE: This is an internal header file, included by other STL headers.
  27.  *   You should not attempt to use it directly.
  28.  */
  29. #ifndef __SGI_STL_INTERNAL_ALGOBASE_H
  30. #define __SGI_STL_INTERNAL_ALGOBASE_H
  31. #ifndef __STL_CONFIG_H
  32. #include <stl_config.h>
  33. #endif
  34. #ifndef __SGI_STL_INTERNAL_RELOPS
  35. #include <stl_relops.h>
  36. #endif
  37. #ifndef __SGI_STL_INTERNAL_PAIR_H
  38. #include <stl_pair.h>
  39. #endif
  40. #ifndef __TYPE_TRAITS_H
  41. #include <type_traits.h>
  42. #endif
  43. #include <string.h>
  44. #include <limits.h>
  45. #include <stdlib.h>
  46. #include <stddef.h>
  47. #include <new.h>
  48. #ifdef __STL_USE_NEW_IOSTREAMS 
  49. #include <iosfwd>
  50. #else /* __STL_USE_NEW_IOSTREAMS */
  51. #include <iostream.h>
  52. #endif /* __STL_USE_NEW_IOSTREAMS */
  53. #ifndef __SGI_STL_INTERNAL_ITERATOR_H
  54. #include <stl_iterator_base.h>
  55. #include <stl_iterator.h>
  56. #endif
  57. // We pick up concept_checks.h from stl_iterator_base.h.
  58. __STL_BEGIN_NAMESPACE
  59. // swap and iter_swap
  60. template <class _ForwardIter1, class _ForwardIter2, class _Tp>
  61. inline void __iter_swap(_ForwardIter1 __a, _ForwardIter2 __b, _Tp*) {
  62.   _Tp __tmp = *__a;
  63.   *__a = *__b;
  64.   *__b = __tmp;
  65. }
  66. template <class _ForwardIter1, class _ForwardIter2>
  67. inline void iter_swap(_ForwardIter1 __a, _ForwardIter2 __b) {
  68.   __STL_REQUIRES(_ForwardIter1, _Mutable_ForwardIterator);
  69.   __STL_REQUIRES(_ForwardIter2, _Mutable_ForwardIterator);
  70.   __STL_CONVERTIBLE(typename iterator_traits<_ForwardIter1>::value_type,
  71.                     typename iterator_traits<_ForwardIter2>::value_type);
  72.   __STL_CONVERTIBLE(typename iterator_traits<_ForwardIter2>::value_type,
  73.                     typename iterator_traits<_ForwardIter1>::value_type);
  74.   __iter_swap(__a, __b, __VALUE_TYPE(__a));
  75. }
  76. template <class _Tp>
  77. inline void swap(_Tp& __a, _Tp& __b) {
  78.   __STL_REQUIRES(_Tp, _Assignable);
  79.   _Tp __tmp = __a;
  80.   __a = __b;
  81.   __b = __tmp;
  82. }
  83. //--------------------------------------------------
  84. // min and max
  85. #if !defined(__BORLANDC__) || __BORLANDC__ >= 0x540 /* C++ Builder 4.0 */
  86. #undef min
  87. #undef max
  88. template <class _Tp>
  89. inline const _Tp& min(const _Tp& __a, const _Tp& __b) {
  90.   __STL_REQUIRES(_Tp, _LessThanComparable);
  91.   return __b < __a ? __b : __a;
  92. }
  93. template <class _Tp>
  94. inline const _Tp& max(const _Tp& __a, const _Tp& __b) {
  95.   __STL_REQUIRES(_Tp, _LessThanComparable);
  96.   return  __a < __b ? __b : __a;
  97. }
  98. #endif /* __BORLANDC__ */
  99. template <class _Tp, class _Compare>
  100. inline const _Tp& min(const _Tp& __a, const _Tp& __b, _Compare __comp) {
  101.   return __comp(__b, __a) ? __b : __a;
  102. }
  103. template <class _Tp, class _Compare>
  104. inline const _Tp& max(const _Tp& __a, const _Tp& __b, _Compare __comp) {
  105.   return __comp(__a, __b) ? __b : __a;
  106. }
  107. //--------------------------------------------------
  108. // copy
  109. // All of these auxiliary functions serve two purposes.  (1) Replace
  110. // calls to copy with memmove whenever possible.  (Memmove, not memcpy,
  111. // because the input and output ranges are permitted to overlap.)
  112. // (2) If we're using random access iterators, then write the loop as
  113. // a for loop with an explicit count.
  114. template <class _InputIter, class _OutputIter, class _Distance>
  115. inline _OutputIter __copy(_InputIter __first, _InputIter __last,
  116.                           _OutputIter __result,
  117.                           input_iterator_tag, _Distance*)
  118. {
  119.   for ( ; __first != __last; ++__result, ++__first)
  120.     *__result = *__first;
  121.   return __result;
  122. }
  123. template <class _RandomAccessIter, class _OutputIter, class _Distance>
  124. inline _OutputIter
  125. __copy(_RandomAccessIter __first, _RandomAccessIter __last,
  126.        _OutputIter __result, random_access_iterator_tag, _Distance*)
  127. {
  128.   for (_Distance __n = __last - __first; __n > 0; --__n) {
  129.     *__result = *__first;
  130.     ++__first;
  131.     ++__result;
  132.   }
  133.   return __result;
  134. }
  135. template <class _Tp>
  136. inline _Tp*
  137. __copy_trivial(const _Tp* __first, const _Tp* __last, _Tp* __result) {
  138.   memmove(__result, __first, sizeof(_Tp) * (__last - __first));
  139.   return __result + (__last - __first);
  140. }
  141. #if defined(__STL_FUNCTION_TMPL_PARTIAL_ORDER)
  142. template <class _InputIter, class _OutputIter>
  143. inline _OutputIter __copy_aux2(_InputIter __first, _InputIter __last,
  144.                                _OutputIter __result, __false_type) {
  145.   return __copy(__first, __last, __result,
  146.                 __ITERATOR_CATEGORY(__first),
  147.                 __DISTANCE_TYPE(__first));
  148. }
  149. template <class _InputIter, class _OutputIter>
  150. inline _OutputIter __copy_aux2(_InputIter __first, _InputIter __last,
  151.                                _OutputIter __result, __true_type) {
  152.   return __copy(__first, __last, __result,
  153.                 __ITERATOR_CATEGORY(__first),
  154.                 __DISTANCE_TYPE(__first));
  155. }
  156. #ifndef __USLC__
  157. template <class _Tp>
  158. inline _Tp* __copy_aux2(_Tp* __first, _Tp* __last, _Tp* __result,
  159.                         __true_type) {
  160.   return __copy_trivial(__first, __last, __result);
  161. }
  162. #endif /* __USLC__ */
  163. template <class _Tp>
  164. inline _Tp* __copy_aux2(const _Tp* __first, const _Tp* __last, _Tp* __result,
  165.                         __true_type) {
  166.   return __copy_trivial(__first, __last, __result);
  167. }
  168. template <class _InputIter, class _OutputIter, class _Tp>
  169. inline _OutputIter __copy_aux(_InputIter __first, _InputIter __last,
  170.                               _OutputIter __result, _Tp*) {
  171.   typedef typename __type_traits<_Tp>::has_trivial_assignment_operator
  172.           _Trivial;
  173.   return __copy_aux2(__first, __last, __result, _Trivial());
  174. }
  175. template <class _InputIter, class _OutputIter>
  176. inline _OutputIter copy(_InputIter __first, _InputIter __last,
  177.                         _OutputIter __result) {
  178.   __STL_REQUIRES(_InputIter, _InputIterator);
  179.   __STL_REQUIRES(_OutputIter, _OutputIterator);
  180.   return __copy_aux(__first, __last, __result, __VALUE_TYPE(__first));
  181. }
  182. // Hack for compilers that don't have partial ordering of function templates
  183. // but do have partial specialization of class templates.
  184. #elif defined(__STL_CLASS_PARTIAL_SPECIALIZATION)
  185. template <class _InputIter, class _OutputIter, class _BoolType>
  186. struct __copy_dispatch {
  187.   static _OutputIter copy(_InputIter __first, _InputIter __last,
  188.                           _OutputIter __result) {
  189.     typedef typename iterator_traits<_InputIter>::iterator_category _Category;
  190.     typedef typename iterator_traits<_InputIter>::difference_type _Distance;
  191.     return __copy(__first, __last, __result, _Category(), (_Distance*) 0);
  192.   }
  193. };
  194. template <class _Tp>
  195. struct __copy_dispatch<_Tp*, _Tp*, __true_type>
  196. {
  197.   static _Tp* copy(const _Tp* __first, const _Tp* __last, _Tp* __result) {
  198.     return __copy_trivial(__first, __last, __result);
  199.   }
  200. };
  201. template <class _Tp>
  202. struct __copy_dispatch<const _Tp*, _Tp*, __true_type>
  203. {
  204.   static _Tp* copy(const _Tp* __first, const _Tp* __last, _Tp* __result) {
  205.     return __copy_trivial(__first, __last, __result);
  206.   }
  207. };
  208. template <class _InputIter, class _OutputIter>
  209. inline _OutputIter copy(_InputIter __first, _InputIter __last,
  210.                         _OutputIter __result) {
  211.   __STL_REQUIRES(_InputIter, _InputIterator);
  212.   __STL_REQUIRES(_OutputIter, _OutputIterator);
  213.   typedef typename iterator_traits<_InputIter>::value_type _Tp;
  214.   typedef typename __type_traits<_Tp>::has_trivial_assignment_operator
  215.           _Trivial;
  216.   return __copy_dispatch<_InputIter, _OutputIter, _Trivial>
  217.     ::copy(__first, __last, __result);
  218. }
  219. // Fallback for compilers with neither partial ordering nor partial
  220. // specialization.  Define the faster version for the basic builtin
  221. // types.
  222. #else /* __STL_CLASS_PARTIAL_SPECIALIZATION */
  223. template <class _InputIter, class _OutputIter>
  224. inline _OutputIter copy(_InputIter __first, _InputIter __last,
  225.                         _OutputIter __result)
  226. {
  227.   return __copy(__first, __last, __result,
  228.                 __ITERATOR_CATEGORY(__first),
  229.                 __DISTANCE_TYPE(__first));
  230. }
  231. #define __SGI_STL_DECLARE_COPY_TRIVIAL(_Tp)                                
  232.   inline _Tp* copy(const _Tp* __first, const _Tp* __last, _Tp* __result) { 
  233.     memmove(__result, __first, sizeof(_Tp) * (__last - __first));          
  234.     return __result + (__last - __first);                                  
  235.   }
  236. __SGI_STL_DECLARE_COPY_TRIVIAL(char)
  237. __SGI_STL_DECLARE_COPY_TRIVIAL(signed char)
  238. __SGI_STL_DECLARE_COPY_TRIVIAL(unsigned char)
  239. __SGI_STL_DECLARE_COPY_TRIVIAL(short)
  240. __SGI_STL_DECLARE_COPY_TRIVIAL(unsigned short)
  241. __SGI_STL_DECLARE_COPY_TRIVIAL(int)
  242. __SGI_STL_DECLARE_COPY_TRIVIAL(unsigned int)
  243. __SGI_STL_DECLARE_COPY_TRIVIAL(long)
  244. __SGI_STL_DECLARE_COPY_TRIVIAL(unsigned long)
  245. #ifdef __STL_HAS_WCHAR_T
  246. __SGI_STL_DECLARE_COPY_TRIVIAL(wchar_t)
  247. #endif
  248. #ifdef _STL_LONG_LONG
  249. __SGI_STL_DECLARE_COPY_TRIVIAL(long long)
  250. __SGI_STL_DECLARE_COPY_TRIVIAL(unsigned long long)
  251. #endif 
  252. __SGI_STL_DECLARE_COPY_TRIVIAL(float)
  253. __SGI_STL_DECLARE_COPY_TRIVIAL(double)
  254. __SGI_STL_DECLARE_COPY_TRIVIAL(long double)
  255. #undef __SGI_STL_DECLARE_COPY_TRIVIAL
  256. #endif /* __STL_CLASS_PARTIAL_SPECIALIZATION */
  257. //--------------------------------------------------
  258. // copy_backward
  259. template <class _BidirectionalIter1, class _BidirectionalIter2, 
  260.           class _Distance>
  261. inline _BidirectionalIter2 __copy_backward(_BidirectionalIter1 __first, 
  262.                                            _BidirectionalIter1 __last, 
  263.                                            _BidirectionalIter2 __result,
  264.                                            bidirectional_iterator_tag,
  265.                                            _Distance*)
  266. {
  267.   while (__first != __last)
  268.     *--__result = *--__last;
  269.   return __result;
  270. }
  271. template <class _RandomAccessIter, class _BidirectionalIter, class _Distance>
  272. inline _BidirectionalIter __copy_backward(_RandomAccessIter __first, 
  273.                                           _RandomAccessIter __last, 
  274.                                           _BidirectionalIter __result,
  275.                                           random_access_iterator_tag,
  276.                                           _Distance*)
  277. {
  278.   for (_Distance __n = __last - __first; __n > 0; --__n)
  279.     *--__result = *--__last;
  280.   return __result;
  281. }
  282. #ifdef __STL_CLASS_PARTIAL_SPECIALIZATION 
  283. // This dispatch class is a workaround for compilers that do not 
  284. // have partial ordering of function templates.  All we're doing is
  285. // creating a specialization so that we can turn a call to copy_backward
  286. // into a memmove whenever possible.
  287. template <class _BidirectionalIter1, class _BidirectionalIter2,
  288.           class _BoolType>
  289. struct __copy_backward_dispatch
  290. {
  291.   typedef typename iterator_traits<_BidirectionalIter1>::iterator_category 
  292.           _Cat;
  293.   typedef typename iterator_traits<_BidirectionalIter1>::difference_type
  294.           _Distance;
  295.   static _BidirectionalIter2 copy(_BidirectionalIter1 __first, 
  296.                                   _BidirectionalIter1 __last, 
  297.                                   _BidirectionalIter2 __result) {
  298.     return __copy_backward(__first, __last, __result, _Cat(), (_Distance*) 0);
  299.   }
  300. };
  301. template <class _Tp>
  302. struct __copy_backward_dispatch<_Tp*, _Tp*, __true_type>
  303. {
  304.   static _Tp* copy(const _Tp* __first, const _Tp* __last, _Tp* __result) {
  305.     const ptrdiff_t _Num = __last - __first;
  306.     memmove(__result - _Num, __first, sizeof(_Tp) * _Num);
  307.     return __result - _Num;
  308.   }
  309. };
  310. template <class _Tp>
  311. struct __copy_backward_dispatch<const _Tp*, _Tp*, __true_type>
  312. {
  313.   static _Tp* copy(const _Tp* __first, const _Tp* __last, _Tp* __result) {
  314.     return  __copy_backward_dispatch<_Tp*, _Tp*, __true_type>
  315.       ::copy(__first, __last, __result);
  316.   }
  317. };
  318. template <class _BI1, class _BI2>
  319. inline _BI2 copy_backward(_BI1 __first, _BI1 __last, _BI2 __result) {
  320.   __STL_REQUIRES(_BI1, _BidirectionalIterator);
  321.   __STL_REQUIRES(_BI2, _Mutable_BidirectionalIterator);
  322.   __STL_CONVERTIBLE(typename iterator_traits<_BI1>::value_type,
  323.                     typename iterator_traits<_BI2>::value_type);
  324.   typedef typename __type_traits<typename iterator_traits<_BI2>::value_type>
  325.                         ::has_trivial_assignment_operator
  326.           _Trivial;
  327.   return __copy_backward_dispatch<_BI1, _BI2, _Trivial>
  328.               ::copy(__first, __last, __result);
  329. }
  330. #else /* __STL_CLASS_PARTIAL_SPECIALIZATION */
  331. template <class _BI1, class _BI2>
  332. inline _BI2 copy_backward(_BI1 __first, _BI1 __last, _BI2 __result) {
  333.   return __copy_backward(__first, __last, __result,
  334.                          __ITERATOR_CATEGORY(__first),
  335.                          __DISTANCE_TYPE(__first));
  336. }
  337. #endif /* __STL_CLASS_PARTIAL_SPECIALIZATION */
  338. //--------------------------------------------------
  339. // copy_n (not part of the C++ standard)
  340. template <class _InputIter, class _Size, class _OutputIter>
  341. pair<_InputIter, _OutputIter> __copy_n(_InputIter __first, _Size __count,
  342.                                        _OutputIter __result,
  343.                                        input_iterator_tag) {
  344.   for ( ; __count > 0; --__count) {
  345.     *__result = *__first;
  346.     ++__first;
  347.     ++__result;
  348.   }
  349.   return pair<_InputIter, _OutputIter>(__first, __result);
  350. }
  351. template <class _RAIter, class _Size, class _OutputIter>
  352. inline pair<_RAIter, _OutputIter>
  353. __copy_n(_RAIter __first, _Size __count,
  354.          _OutputIter __result,
  355.          random_access_iterator_tag) {
  356.   _RAIter __last = __first + __count;
  357.   return pair<_RAIter, _OutputIter>(__last, copy(__first, __last, __result));
  358. }
  359. template <class _InputIter, class _Size, class _OutputIter>
  360. inline pair<_InputIter, _OutputIter>
  361. __copy_n(_InputIter __first, _Size __count, _OutputIter __result) {
  362.   return __copy_n(__first, __count, __result,
  363.                   __ITERATOR_CATEGORY(__first));
  364. }
  365. template <class _InputIter, class _Size, class _OutputIter>
  366. inline pair<_InputIter, _OutputIter>
  367. copy_n(_InputIter __first, _Size __count, _OutputIter __result) {
  368.   __STL_REQUIRES(_InputIter, _InputIterator);
  369.   __STL_REQUIRES(_OutputIter, _OutputIterator);
  370.   return __copy_n(__first, __count, __result);
  371. }
  372. //--------------------------------------------------
  373. // fill and fill_n
  374. template <class _ForwardIter, class _Tp>
  375. void fill(_ForwardIter __first, _ForwardIter __last, const _Tp& __value) {
  376.   __STL_REQUIRES(_ForwardIter, _Mutable_ForwardIterator);
  377.   for ( ; __first != __last; ++__first)
  378.     *__first = __value;
  379. }
  380. template <class _OutputIter, class _Size, class _Tp>
  381. _OutputIter fill_n(_OutputIter __first, _Size __n, const _Tp& __value) {
  382.   __STL_REQUIRES(_OutputIter, _OutputIterator);
  383.   for ( ; __n > 0; --__n, ++__first)
  384.     *__first = __value;
  385.   return __first;
  386. }
  387. // Specialization: for one-byte types we can use memset.
  388. inline void fill(unsigned char* __first, unsigned char* __last,
  389.                  const unsigned char& __c) {
  390.   unsigned char __tmp = __c;
  391.   memset(__first, __tmp, __last - __first);
  392. }
  393. inline void fill(signed char* __first, signed char* __last,
  394.                  const signed char& __c) {
  395.   signed char __tmp = __c;
  396.   memset(__first, static_cast<unsigned char>(__tmp), __last - __first);
  397. }
  398. inline void fill(char* __first, char* __last, const char& __c) {
  399.   char __tmp = __c;
  400.   memset(__first, static_cast<unsigned char>(__tmp), __last - __first);
  401. }
  402. #ifdef __STL_FUNCTION_TMPL_PARTIAL_ORDER
  403. template <class _Size>
  404. inline unsigned char* fill_n(unsigned char* __first, _Size __n,
  405.                              const unsigned char& __c) {
  406.   fill(__first, __first + __n, __c);
  407.   return __first + __n;
  408. }
  409. template <class _Size>
  410. inline signed char* fill_n(char* __first, _Size __n,
  411.                            const signed char& __c) {
  412.   fill(__first, __first + __n, __c);
  413.   return __first + __n;
  414. }
  415. template <class _Size>
  416. inline char* fill_n(char* __first, _Size __n, const char& __c) {
  417.   fill(__first, __first + __n, __c);
  418.   return __first + __n;
  419. }
  420. #endif /* __STL_FUNCTION_TMPL_PARTIAL_ORDER */
  421. //--------------------------------------------------
  422. // equal and mismatch
  423. template <class _InputIter1, class _InputIter2>
  424. pair<_InputIter1, _InputIter2> mismatch(_InputIter1 __first1,
  425.                                         _InputIter1 __last1,
  426.                                         _InputIter2 __first2) {
  427.   __STL_REQUIRES(_InputIter1, _InputIterator);
  428.   __STL_REQUIRES(_InputIter2, _InputIterator);
  429.   __STL_REQUIRES(typename iterator_traits<_InputIter1>::value_type,
  430.                  _EqualityComparable);
  431.   __STL_REQUIRES(typename iterator_traits<_InputIter2>::value_type,
  432.                  _EqualityComparable);
  433.   while (__first1 != __last1 && *__first1 == *__first2) {
  434.     ++__first1;
  435.     ++__first2;
  436.   }
  437.   return pair<_InputIter1, _InputIter2>(__first1, __first2);
  438. }
  439. template <class _InputIter1, class _InputIter2, class _BinaryPredicate>
  440. pair<_InputIter1, _InputIter2> mismatch(_InputIter1 __first1,
  441.                                         _InputIter1 __last1,
  442.                                         _InputIter2 __first2,
  443.                                         _BinaryPredicate __binary_pred) {
  444.   __STL_REQUIRES(_InputIter1, _InputIterator);
  445.   __STL_REQUIRES(_InputIter2, _InputIterator);
  446.   while (__first1 != __last1 && __binary_pred(*__first1, *__first2)) {
  447.     ++__first1;
  448.     ++__first2;
  449.   }
  450.   return pair<_InputIter1, _InputIter2>(__first1, __first2);
  451. }
  452. template <class _InputIter1, class _InputIter2>
  453. inline bool equal(_InputIter1 __first1, _InputIter1 __last1,
  454.                   _InputIter2 __first2) {
  455.   __STL_REQUIRES(_InputIter1, _InputIterator);
  456.   __STL_REQUIRES(_InputIter2, _InputIterator);
  457.   __STL_REQUIRES(typename iterator_traits<_InputIter1>::value_type,
  458.                  _EqualityComparable);
  459.   __STL_REQUIRES(typename iterator_traits<_InputIter2>::value_type,
  460.                  _EqualityComparable);
  461.   for ( ; __first1 != __last1; ++__first1, ++__first2)
  462.     if (*__first1 != *__first2)
  463.       return false;
  464.   return true;
  465. }
  466. template <class _InputIter1, class _InputIter2, class _BinaryPredicate>
  467. inline bool equal(_InputIter1 __first1, _InputIter1 __last1,
  468.                   _InputIter2 __first2, _BinaryPredicate __binary_pred) {
  469.   __STL_REQUIRES(_InputIter1, _InputIterator);
  470.   __STL_REQUIRES(_InputIter2, _InputIterator);
  471.   for ( ; __first1 != __last1; ++__first1, ++__first2)
  472.     if (!__binary_pred(*__first1, *__first2))
  473.       return false;
  474.   return true;
  475. }
  476. //--------------------------------------------------
  477. // lexicographical_compare and lexicographical_compare_3way.
  478. // (the latter is not part of the C++ standard.)
  479. template <class _InputIter1, class _InputIter2>
  480. bool lexicographical_compare(_InputIter1 __first1, _InputIter1 __last1,
  481.                              _InputIter2 __first2, _InputIter2 __last2) {
  482.   __STL_REQUIRES(_InputIter1, _InputIterator);
  483.   __STL_REQUIRES(_InputIter2, _InputIterator);
  484.   __STL_REQUIRES(typename iterator_traits<_InputIter1>::value_type,
  485.                  _LessThanComparable);
  486.   __STL_REQUIRES(typename iterator_traits<_InputIter2>::value_type,
  487.                  _LessThanComparable);
  488.   for ( ; __first1 != __last1 && __first2 != __last2
  489.         ; ++__first1, ++__first2) {
  490.     if (*__first1 < *__first2)
  491.       return true;
  492.     if (*__first2 < *__first1)
  493.       return false;
  494.   }
  495.   return __first1 == __last1 && __first2 != __last2;
  496. }
  497. template <class _InputIter1, class _InputIter2, class _Compare>
  498. bool lexicographical_compare(_InputIter1 __first1, _InputIter1 __last1,
  499.                              _InputIter2 __first2, _InputIter2 __last2,
  500.                              _Compare __comp) {
  501.   __STL_REQUIRES(_InputIter1, _InputIterator);
  502.   __STL_REQUIRES(_InputIter2, _InputIterator);
  503.   for ( ; __first1 != __last1 && __first2 != __last2
  504.         ; ++__first1, ++__first2) {
  505.     if (__comp(*__first1, *__first2))
  506.       return true;
  507.     if (__comp(*__first2, *__first1))
  508.       return false;
  509.   }
  510.   return __first1 == __last1 && __first2 != __last2;
  511. }
  512. inline bool 
  513. lexicographical_compare(const unsigned char* __first1,
  514.                         const unsigned char* __last1,
  515.                         const unsigned char* __first2,
  516.                         const unsigned char* __last2)
  517. {
  518.   const size_t __len1 = __last1 - __first1;
  519.   const size_t __len2 = __last2 - __first2;
  520.   const int __result = memcmp(__first1, __first2, min(__len1, __len2));
  521.   return __result != 0 ? __result < 0 : __len1 < __len2;
  522. }
  523. inline bool lexicographical_compare(const char* __first1, const char* __last1,
  524.                                     const char* __first2, const char* __last2)
  525. {
  526. #if CHAR_MAX == SCHAR_MAX
  527.   return lexicographical_compare((const signed char*) __first1,
  528.                                  (const signed char*) __last1,
  529.                                  (const signed char*) __first2,
  530.                                  (const signed char*) __last2);
  531. #else /* CHAR_MAX == SCHAR_MAX */
  532.   return lexicographical_compare((const unsigned char*) __first1,
  533.                                  (const unsigned char*) __last1,
  534.                                  (const unsigned char*) __first2,
  535.                                  (const unsigned char*) __last2);
  536. #endif /* CHAR_MAX == SCHAR_MAX */
  537. }
  538. template <class _InputIter1, class _InputIter2>
  539. int __lexicographical_compare_3way(_InputIter1 __first1, _InputIter1 __last1,
  540.                                    _InputIter2 __first2, _InputIter2 __last2)
  541. {
  542.   while (__first1 != __last1 && __first2 != __last2) {
  543.     if (*__first1 < *__first2)
  544.       return -1;
  545.     if (*__first2 < *__first1)
  546.       return 1;
  547.     ++__first1;
  548.     ++__first2;
  549.   }
  550.   if (__first2 == __last2) {
  551.     return !(__first1 == __last1);
  552.   }
  553.   else {
  554.     return -1;
  555.   }
  556. }
  557. inline int
  558. __lexicographical_compare_3way(const unsigned char* __first1,
  559.                                const unsigned char* __last1,
  560.                                const unsigned char* __first2,
  561.                                const unsigned char* __last2)
  562. {
  563.   const ptrdiff_t __len1 = __last1 - __first1;
  564.   const ptrdiff_t __len2 = __last2 - __first2;
  565.   const int __result = memcmp(__first1, __first2, min(__len1, __len2));
  566.   return __result != 0 ? __result 
  567.                        : (__len1 == __len2 ? 0 : (__len1 < __len2 ? -1 : 1));
  568. }
  569. inline int 
  570. __lexicographical_compare_3way(const char* __first1, const char* __last1,
  571.                                const char* __first2, const char* __last2)
  572. {
  573. #if CHAR_MAX == SCHAR_MAX
  574.   return __lexicographical_compare_3way(
  575.                                 (const signed char*) __first1,
  576.                                 (const signed char*) __last1,
  577.                                 (const signed char*) __first2,
  578.                                 (const signed char*) __last2);
  579. #else
  580.   return __lexicographical_compare_3way((const unsigned char*) __first1,
  581.                                         (const unsigned char*) __last1,
  582.                                         (const unsigned char*) __first2,
  583.                                         (const unsigned char*) __last2);
  584. #endif
  585. }
  586. template <class _InputIter1, class _InputIter2>
  587. int lexicographical_compare_3way(_InputIter1 __first1, _InputIter1 __last1,
  588.                                  _InputIter2 __first2, _InputIter2 __last2)
  589. {
  590.   __STL_REQUIRES(_InputIter1, _InputIterator);
  591.   __STL_REQUIRES(_InputIter2, _InputIterator);
  592.   __STL_REQUIRES(typename iterator_traits<_InputIter1>::value_type,
  593.                  _LessThanComparable);
  594.   __STL_REQUIRES(typename iterator_traits<_InputIter2>::value_type,
  595.                  _LessThanComparable);
  596.   return __lexicographical_compare_3way(__first1, __last1, __first2, __last2);
  597. }
  598. __STL_END_NAMESPACE
  599. #endif /* __SGI_STL_INTERNAL_ALGOBASE_H */
  600. // Local Variables:
  601. // mode:C++
  602. // End: