stl_algobase.h
上传用户:sichengcw
上传日期:2009-02-17
资源大小:202k
文件大小:14k
源码类别:

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
  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. #include <iostream.h>
  49. #ifndef __SGI_STL_INTERNAL_ITERATOR_H
  50. #include <stl_iterator.h>
  51. #endif
  52. __STL_BEGIN_NAMESPACE
  53. template <class ForwardIterator1, class ForwardIterator2, class T>
  54. inline void __iter_swap(ForwardIterator1 a, ForwardIterator2 b, T*) {
  55.   T tmp = *a;
  56.   *a = *b;
  57.   *b = tmp;
  58. }
  59. template <class ForwardIterator1, class ForwardIterator2>
  60. inline void iter_swap(ForwardIterator1 a, ForwardIterator2 b) {
  61.   __iter_swap(a, b, value_type(a));
  62. }
  63. template <class T>
  64. inline void swap(T& a, T& b) {
  65.   T tmp = a;
  66.   a = b;
  67.   b = tmp;
  68. }
  69. #ifndef __BORLANDC__
  70. #undef min
  71. #undef max
  72. template <class T>
  73. inline const T& min(const T& a, const T& b) {
  74.   return b < a ? b : a;
  75. }
  76. template <class T>
  77. inline const T& max(const T& a, const T& b) {
  78.   return  a < b ? b : a;
  79. }
  80. #endif /* __BORLANDC__ */
  81. template <class T, class Compare>
  82. inline const T& min(const T& a, const T& b, Compare comp) {
  83.   return comp(b, a) ? b : a;
  84. }
  85. template <class T, class Compare>
  86. inline const T& max(const T& a, const T& b, Compare comp) {
  87.   return comp(a, b) ? b : a;
  88. }
  89. template <class InputIterator, class OutputIterator>
  90. inline OutputIterator __copy(InputIterator first, InputIterator last,
  91.                              OutputIterator result, input_iterator_tag)
  92. {
  93.   for ( ; first != last; ++result, ++first)
  94.     *result = *first;
  95.   return result;
  96. }
  97. template <class RandomAccessIterator, class OutputIterator, class Distance>
  98. inline OutputIterator
  99. __copy_d(RandomAccessIterator first, RandomAccessIterator last,
  100.          OutputIterator result, Distance*)
  101. {
  102.   for (Distance n = last - first; n > 0; --n, ++result, ++first) 
  103.     *result = *first;
  104.   return result;
  105. }
  106. template <class RandomAccessIterator, class OutputIterator>
  107. inline OutputIterator 
  108. __copy(RandomAccessIterator first, RandomAccessIterator last,
  109.        OutputIterator result, random_access_iterator_tag)
  110. {
  111.   return __copy_d(first, last, result, distance_type(first));
  112. }
  113. template <class InputIterator, class OutputIterator>
  114. struct __copy_dispatch
  115. {
  116.   OutputIterator operator()(InputIterator first, InputIterator last,
  117.                             OutputIterator result) {
  118.     return __copy(first, last, result, iterator_category(first));
  119.   }
  120. };
  121. #ifdef __STL_CLASS_PARTIAL_SPECIALIZATION 
  122. template <class T>
  123. inline T* __copy_t(const T* first, const T* last, T* result, __true_type) {
  124.   memmove(result, first, sizeof(T) * (last - first));
  125.   return result + (last - first);
  126. }
  127. template <class T>
  128. inline T* __copy_t(const T* first, const T* last, T* result, __false_type) {
  129.   return __copy_d(first, last, result, (ptrdiff_t*) 0);
  130. }
  131. template <class T>
  132. struct __copy_dispatch<T*, T*>
  133. {
  134.   T* operator()(T* first, T* last, T* result) {
  135.     typedef typename __type_traits<T>::has_trivial_assignment_operator t; 
  136.     return __copy_t(first, last, result, t());
  137.   }
  138. };
  139. template <class T>
  140. struct __copy_dispatch<const T*, T*>
  141. {
  142.   T* operator()(const T* first, const T* last, T* result) {
  143.     typedef typename __type_traits<T>::has_trivial_assignment_operator t; 
  144.     return __copy_t(first, last, result, t());
  145.   }
  146. };
  147. #endif /* __STL_CLASS_PARTIAL_SPECIALIZATION */
  148. template <class InputIterator, class OutputIterator>
  149. inline OutputIterator copy(InputIterator first, InputIterator last,
  150.                            OutputIterator result)
  151. {
  152.   return __copy_dispatch<InputIterator,OutputIterator>()(first, last, result);
  153. }
  154. inline char* copy(const char* first, const char* last, char* result) {
  155.   memmove(result, first, last - first);
  156.   return result + (last - first);
  157. }
  158. inline wchar_t* copy(const wchar_t* first, const wchar_t* last,
  159.                      wchar_t* result) {
  160.   memmove(result, first, sizeof(wchar_t) * (last - first));
  161.   return result + (last - first);
  162. }
  163. template <class BidirectionalIterator1, class BidirectionalIterator2>
  164. inline BidirectionalIterator2 __copy_backward(BidirectionalIterator1 first, 
  165.                                               BidirectionalIterator1 last, 
  166.                                               BidirectionalIterator2 result) {
  167.   while (first != last) *--result = *--last;
  168.   return result;
  169. }
  170. template <class BidirectionalIterator1, class BidirectionalIterator2>
  171. struct __copy_backward_dispatch
  172. {
  173.   BidirectionalIterator2 operator()(BidirectionalIterator1 first, 
  174.                                     BidirectionalIterator1 last, 
  175.                                     BidirectionalIterator2 result) {
  176.     return __copy_backward(first, last, result);
  177.   }
  178. };
  179. #ifdef __STL_CLASS_PARTIAL_SPECIALIZATION 
  180. template <class T>
  181. inline T* __copy_backward_t(const T* first, const T* last, T* result,
  182.                             __true_type) {
  183.   const ptrdiff_t N = last - first;
  184.   memmove(result - N, first, sizeof(T) * N);
  185.   return result - N;
  186. }
  187. template <class T>
  188. inline T* __copy_backward_t(const T* first, const T* last, T* result,
  189.                             __false_type) {
  190.   return __copy_backward(first, last, result);
  191. }
  192. template <class T>
  193. struct __copy_backward_dispatch<T*, T*>
  194. {
  195.   T* operator()(T* first, T* last, T* result) {
  196.     typedef typename __type_traits<T>::has_trivial_assignment_operator t; 
  197.     return __copy_backward_t(first, last, result, t());
  198.   }
  199. };
  200. template <class T>
  201. struct __copy_backward_dispatch<const T*, T*>
  202. {
  203.   T* operator()(const T* first, const T* last, T* result) {
  204.     typedef typename __type_traits<T>::has_trivial_assignment_operator t; 
  205.     return __copy_backward_t(first, last, result, t());
  206.   }
  207. };
  208. #endif /* __STL_CLASS_PARTIAL_SPECIALIZATION */
  209. template <class BidirectionalIterator1, class BidirectionalIterator2>
  210. inline BidirectionalIterator2 copy_backward(BidirectionalIterator1 first, 
  211.                                             BidirectionalIterator1 last, 
  212.                                             BidirectionalIterator2 result) {
  213.   return __copy_backward_dispatch<BidirectionalIterator1, 
  214.                                   BidirectionalIterator2>()(first, last, 
  215.                                                             result);
  216. }
  217. template <class InputIterator, class Size, class OutputIterator>
  218. pair<InputIterator, OutputIterator> __copy_n(InputIterator first, Size count,
  219.                                              OutputIterator result,
  220.                                              input_iterator_tag) {
  221.   for ( ; count > 0; --count, ++first, ++result)
  222.     *result = *first;
  223.   return pair<InputIterator, OutputIterator>(first, result);
  224. }
  225. template <class RandomAccessIterator, class Size, class OutputIterator>
  226. inline pair<RandomAccessIterator, OutputIterator>
  227. __copy_n(RandomAccessIterator first, Size count,
  228.          OutputIterator result,
  229.          random_access_iterator_tag) {
  230.   RandomAccessIterator last = first + count;
  231.   return pair<RandomAccessIterator, OutputIterator>(last,
  232.                                                     copy(first, last, result));
  233. }
  234. template <class InputIterator, class Size, class OutputIterator>
  235. inline pair<InputIterator, OutputIterator>
  236. copy_n(InputIterator first, Size count,
  237.        OutputIterator result) {
  238.   return __copy_n(first, count, result, iterator_category(first));
  239. }
  240. template <class ForwardIterator, class T>
  241. void fill(ForwardIterator first, ForwardIterator last, const T& value) {
  242.   for ( ; first != last; ++first)
  243.     *first = value;
  244. }
  245. template <class OutputIterator, class Size, class T>
  246. OutputIterator fill_n(OutputIterator first, Size n, const T& value) {
  247.   for ( ; n > 0; --n, ++first)
  248.     *first = value;
  249.   return first;
  250. }
  251. template <class InputIterator1, class InputIterator2>
  252. pair<InputIterator1, InputIterator2> mismatch(InputIterator1 first1,
  253.       InputIterator1 last1,
  254.       InputIterator2 first2) {
  255.   while (first1 != last1 && *first1 == *first2) {
  256.     ++first1;
  257.     ++first2;
  258.   }
  259.   return pair<InputIterator1, InputIterator2>(first1, first2);
  260. }
  261. template <class InputIterator1, class InputIterator2, class BinaryPredicate>
  262. pair<InputIterator1, InputIterator2> mismatch(InputIterator1 first1,
  263.       InputIterator1 last1,
  264.       InputIterator2 first2,
  265.       BinaryPredicate binary_pred) {
  266.   while (first1 != last1 && binary_pred(*first1, *first2)) {
  267.     ++first1;
  268.     ++first2;
  269.   }
  270.   return pair<InputIterator1, InputIterator2>(first1, first2);
  271. }
  272. template <class InputIterator1, class InputIterator2>
  273. inline bool equal(InputIterator1 first1, InputIterator1 last1,
  274.   InputIterator2 first2) {
  275.   for ( ; first1 != last1; ++first1, ++first2)
  276.     if (*first1 != *first2)
  277.       return false;
  278.   return true;
  279. }
  280. template <class InputIterator1, class InputIterator2, class BinaryPredicate>
  281. inline bool equal(InputIterator1 first1, InputIterator1 last1,
  282.   InputIterator2 first2, BinaryPredicate binary_pred) {
  283.   for ( ; first1 != last1; ++first1, ++first2)
  284.     if (!binary_pred(*first1, *first2))
  285.       return false;
  286.   return true;
  287. }
  288. template <class InputIterator1, class InputIterator2>
  289. bool lexicographical_compare(InputIterator1 first1, InputIterator1 last1,
  290.      InputIterator2 first2, InputIterator2 last2) {
  291.   for ( ; first1 != last1 && first2 != last2; ++first1, ++first2) {
  292.     if (*first1 < *first2)
  293.       return true;
  294.     if (*first2 < *first1)
  295.       return false;
  296.   }
  297.   return first1 == last1 && first2 != last2;
  298. }
  299. template <class InputIterator1, class InputIterator2, class Compare>
  300. bool lexicographical_compare(InputIterator1 first1, InputIterator1 last1,
  301.      InputIterator2 first2, InputIterator2 last2,
  302.      Compare comp) {
  303.   for ( ; first1 != last1 && first2 != last2; ++first1, ++first2) {
  304.     if (comp(*first1, *first2))
  305.       return true;
  306.     if (comp(*first2, *first1))
  307.       return false;
  308.   }
  309.   return first1 == last1 && first2 != last2;
  310. }
  311. inline bool 
  312. lexicographical_compare(const unsigned char* first1,
  313.                         const unsigned char* last1,
  314.                         const unsigned char* first2,
  315.                         const unsigned char* last2)
  316. {
  317.   const size_t len1 = last1 - first1;
  318.   const size_t len2 = last2 - first2;
  319.   const int result = memcmp(first1, first2, min(len1, len2));
  320.   return result != 0 ? result < 0 : len1 < len2;
  321. }
  322. inline bool lexicographical_compare(const char* first1, const char* last1,
  323.                                     const char* first2, const char* last2)
  324. {
  325. #if CHAR_MAX == SCHAR_MAX
  326.   return lexicographical_compare((const signed char*) first1,
  327.                                  (const signed char*) last1,
  328.                                  (const signed char*) first2,
  329.                                  (const signed char*) last2);
  330. #else
  331.   return lexicographical_compare((const unsigned char*) first1,
  332.                                  (const unsigned char*) last1,
  333.                                  (const unsigned char*) first2,
  334.                                  (const unsigned char*) last2);
  335. #endif
  336. }
  337. template <class InputIterator1, class InputIterator2>
  338. int lexicographical_compare_3way(InputIterator1 first1, InputIterator1 last1,
  339.                                  InputIterator2 first2, InputIterator2 last2)
  340. {
  341.   while (first1 != last1 && first2 != last2) {
  342.     if (*first1 < *first2) return -1;
  343.     if (*first2 < *first1) return 1;
  344.     ++first1; ++first2;
  345.   }
  346.   if (first2 == last2) {
  347.     return !(first1 == last1);
  348.   } else {
  349.     return -1;
  350.   }
  351. }
  352. inline int
  353. lexicographical_compare_3way(const unsigned char* first1,
  354.                              const unsigned char* last1,
  355.                              const unsigned char* first2,
  356.                              const unsigned char* last2)
  357. {
  358.   const ptrdiff_t len1 = last1 - first1;
  359.   const ptrdiff_t len2 = last2 - first2;
  360.   const int result = memcmp(first1, first2, min(len1, len2));
  361.   return result != 0 ? result : (len1 == len2 ? 0 : (len1 < len2 ? -1 : 1));
  362. }
  363. inline int lexicographical_compare_3way(const char* first1, const char* last1,
  364.                                         const char* first2, const char* last2)
  365. {
  366. #if CHAR_MAX == SCHAR_MAX
  367.   return lexicographical_compare_3way(
  368. (const signed char*) first1,
  369.                                 (const signed char*) last1,
  370.                                 (const signed char*) first2,
  371.                                 (const signed char*) last2);
  372. #else
  373.   return lexicographical_compare_3way((const unsigned char*) first1,
  374.                                       (const unsigned char*) last1,
  375.                                       (const unsigned char*) first2,
  376.                                       (const unsigned char*) last2);
  377. #endif
  378. }
  379. __STL_END_NAMESPACE
  380. #endif /* __SGI_STL_INTERNAL_ALGOBASE_H */
  381. // Local Variables:
  382. // mode:C++
  383. // End: