home *** CD-ROM | disk | FTP | other *** search
/ PC World 2008 April / PCWorld_2008-04_cd.bin / temacd / devc++ / devcpp-4.9.9.2_setup.exe / stl_algobase.h < prev    next >
C/C++ Source or Header  |  2005-01-29  |  30KB  |  842 lines
  1. // Bits and pieces used in algorithms -*- C++ -*-
  2.  
  3. // Copyright (C) 2001, 2002, 2003, 2004 Free Software Foundation, Inc.
  4. //
  5. // This file is part of the GNU ISO C++ Library.  This library is free
  6. // software; you can redistribute it and/or modify it under the
  7. // terms of the GNU General Public License as published by the
  8. // Free Software Foundation; either version 2, or (at your option)
  9. // any later version.
  10.  
  11. // This library is distributed in the hope that it will be useful,
  12. // but WITHOUT ANY WARRANTY; without even the implied warranty of
  13. // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  14. // GNU General Public License for more details.
  15.  
  16. // You should have received a copy of the GNU General Public License along
  17. // with this library; see the file COPYING.  If not, write to the Free
  18. // Software Foundation, 59 Temple Place - Suite 330, Boston, MA 02111-1307,
  19. // USA.
  20.  
  21. // As a special exception, you may use this file as part of a free software
  22. // library without restriction.  Specifically, if other files instantiate
  23. // templates or use macros or inline functions from this file, or you compile
  24. // this file and link it with other files to produce an executable, this
  25. // file does not by itself cause the resulting executable to be covered by
  26. // the GNU General Public License.  This exception does not however
  27. // invalidate any other reasons why the executable file might be covered by
  28. // the GNU General Public License.
  29.  
  30. /*
  31.  *
  32.  * Copyright (c) 1994
  33.  * Hewlett-Packard Company
  34.  *
  35.  * Permission to use, copy, modify, distribute and sell this software
  36.  * and its documentation for any purpose is hereby granted without fee,
  37.  * provided that the above copyright notice appear in all copies and
  38.  * that both that copyright notice and this permission notice appear
  39.  * in supporting documentation.  Hewlett-Packard Company makes no
  40.  * representations about the suitability of this software for any
  41.  * purpose.  It is provided "as is" without express or implied warranty.
  42.  *
  43.  *
  44.  * Copyright (c) 1996-1998
  45.  * Silicon Graphics Computer Systems, Inc.
  46.  *
  47.  * Permission to use, copy, modify, distribute and sell this software
  48.  * and its documentation for any purpose is hereby granted without fee,
  49.  * provided that the above copyright notice appear in all copies and
  50.  * that both that copyright notice and this permission notice appear
  51.  * in supporting documentation.  Silicon Graphics makes no
  52.  * representations about the suitability of this software for any
  53.  * purpose.  It is provided "as is" without express or implied warranty.
  54.  */
  55.  
  56. /** @file stl_algobase.h
  57.  *  This is an internal header file, included by other library headers.
  58.  *  You should not attempt to use it directly.
  59.  */
  60.  
  61. #ifndef _ALGOBASE_H
  62. #define _ALGOBASE_H 1
  63.  
  64. #include <bits/c++config.h>
  65. #include <cstring>
  66. #include <climits>
  67. #include <cstdlib>
  68. #include <cstddef>
  69. #include <new>
  70. #include <iosfwd>
  71. #include <bits/stl_pair.h>
  72. #include <bits/type_traits.h>
  73. #include <bits/stl_iterator_base_types.h>
  74. #include <bits/stl_iterator_base_funcs.h>
  75. #include <bits/stl_iterator.h>
  76. #include <bits/concept_check.h>
  77. #include <debug/debug.h>
  78.  
  79. namespace std
  80. {
  81.   /**
  82.    *  @brief Swaps the contents of two iterators.
  83.    *  @param  a  An iterator.
  84.    *  @param  b  Another iterator.
  85.    *  @return   Nothing.
  86.    *
  87.    *  This function swaps the values pointed to by two iterators, not the
  88.    *  iterators themselves.
  89.   */
  90.   template<typename _ForwardIterator1, typename _ForwardIterator2>
  91.     inline void
  92.     iter_swap(_ForwardIterator1 __a, _ForwardIterator2 __b)
  93.     {
  94.       typedef typename iterator_traits<_ForwardIterator1>::value_type
  95.     _ValueType1;
  96.       typedef typename iterator_traits<_ForwardIterator2>::value_type
  97.     _ValueType2;
  98.  
  99.       // concept requirements
  100.       __glibcxx_function_requires(_Mutable_ForwardIteratorConcept<
  101.                   _ForwardIterator1>)
  102.       __glibcxx_function_requires(_Mutable_ForwardIteratorConcept<
  103.                   _ForwardIterator2>)
  104.       __glibcxx_function_requires(_ConvertibleConcept<_ValueType1,
  105.                   _ValueType2>)
  106.       __glibcxx_function_requires(_ConvertibleConcept<_ValueType2,
  107.                   _ValueType1>)
  108.  
  109.       const _ValueType1 __tmp = *__a;
  110.       *__a = *__b;
  111.       *__b = __tmp;
  112.     }
  113.  
  114.   /**
  115.    *  @brief Swaps two values.
  116.    *  @param  a  A thing of arbitrary type.
  117.    *  @param  b  Another thing of arbitrary type.
  118.    *  @return   Nothing.
  119.    *
  120.    *  This is the simple classic generic implementation.  It will work on
  121.    *  any type which has a copy constructor and an assignment operator.
  122.   */
  123.   template<typename _Tp>
  124.     inline void
  125.     swap(_Tp& __a, _Tp& __b)
  126.     {
  127.       // concept requirements
  128.       __glibcxx_function_requires(_SGIAssignableConcept<_Tp>)
  129.  
  130.       const _Tp __tmp = __a;
  131.       __a = __b;
  132.       __b = __tmp;
  133.     }
  134.  
  135.   #undef min
  136.   #undef max
  137.  
  138.   /**
  139.    *  @brief This does what you think it does.
  140.    *  @param  a  A thing of arbitrary type.
  141.    *  @param  b  Another thing of arbitrary type.
  142.    *  @return   The lesser of the parameters.
  143.    *
  144.    *  This is the simple classic generic implementation.  It will work on
  145.    *  temporary expressions, since they are only evaluated once, unlike a
  146.    *  preprocessor macro.
  147.   */
  148.   template<typename _Tp>
  149.     inline const _Tp&
  150.     min(const _Tp& __a, const _Tp& __b)
  151.     {
  152.       // concept requirements
  153.       __glibcxx_function_requires(_LessThanComparableConcept<_Tp>)
  154.       //return __b < __a ? __b : __a;
  155.       if (__b < __a)
  156.     return __b;
  157.       return __a;
  158.     }
  159.  
  160.   /**
  161.    *  @brief This does what you think it does.
  162.    *  @param  a  A thing of arbitrary type.
  163.    *  @param  b  Another thing of arbitrary type.
  164.    *  @return   The greater of the parameters.
  165.    *
  166.    *  This is the simple classic generic implementation.  It will work on
  167.    *  temporary expressions, since they are only evaluated once, unlike a
  168.    *  preprocessor macro.
  169.   */
  170.   template<typename _Tp>
  171.     inline const _Tp&
  172.     max(const _Tp& __a, const _Tp& __b)
  173.     {
  174.       // concept requirements
  175.       __glibcxx_function_requires(_LessThanComparableConcept<_Tp>)
  176.       //return  __a < __b ? __b : __a;
  177.       if (__a < __b)
  178.     return __b;
  179.       return __a;
  180.     }
  181.  
  182.   /**
  183.    *  @brief This does what you think it does.
  184.    *  @param  a  A thing of arbitrary type.
  185.    *  @param  b  Another thing of arbitrary type.
  186.    *  @param  comp  A @link s20_3_3_comparisons comparison functor@endlink.
  187.    *  @return   The lesser of the parameters.
  188.    *
  189.    *  This will work on temporary expressions, since they are only evaluated
  190.    *  once, unlike a preprocessor macro.
  191.   */
  192.   template<typename _Tp, typename _Compare>
  193.     inline const _Tp&
  194.     min(const _Tp& __a, const _Tp& __b, _Compare __comp)
  195.     {
  196.       //return __comp(__b, __a) ? __b : __a;
  197.       if (__comp(__b, __a))
  198.     return __b;
  199.       return __a;
  200.     }
  201.  
  202.   /**
  203.    *  @brief This does what you think it does.
  204.    *  @param  a  A thing of arbitrary type.
  205.    *  @param  b  Another thing of arbitrary type.
  206.    *  @param  comp  A @link s20_3_3_comparisons comparison functor@endlink.
  207.    *  @return   The greater of the parameters.
  208.    *
  209.    *  This will work on temporary expressions, since they are only evaluated
  210.    *  once, unlike a preprocessor macro.
  211.   */
  212.   template<typename _Tp, typename _Compare>
  213.     inline const _Tp&
  214.     max(const _Tp& __a, const _Tp& __b, _Compare __comp)
  215.     {
  216.       //return __comp(__a, __b) ? __b : __a;
  217.       if (__comp(__a, __b))
  218.     return __b;
  219.       return __a;
  220.     }
  221.  
  222.   // All of these auxiliary functions serve two purposes.  (1) Replace
  223.   // calls to copy with memmove whenever possible.  (Memmove, not memcpy,
  224.   // because the input and output ranges are permitted to overlap.)
  225.   // (2) If we're using random access iterators, then write the loop as
  226.   // a for loop with an explicit count.
  227.  
  228.   template<typename _InputIterator, typename _OutputIterator>
  229.     inline _OutputIterator
  230.     __copy(_InputIterator __first, _InputIterator __last,
  231.        _OutputIterator __result, input_iterator_tag)
  232.     {
  233.       for (; __first != __last; ++__result, ++__first)
  234.     *__result = *__first;
  235.       return __result;
  236.     }
  237.  
  238.   template<typename _RandomAccessIterator, typename _OutputIterator>
  239.     inline _OutputIterator
  240.     __copy(_RandomAccessIterator __first, _RandomAccessIterator __last,
  241.        _OutputIterator __result, random_access_iterator_tag)
  242.     {
  243.       typedef typename iterator_traits<_RandomAccessIterator>::difference_type
  244.           _Distance;
  245.       for (_Distance __n = __last - __first; __n > 0; --__n)
  246.     {
  247.       *__result = *__first;
  248.       ++__first;
  249.       ++__result;
  250.     }
  251.       return __result;
  252.     }
  253.  
  254.   template<typename _Tp>
  255.     inline _Tp*
  256.     __copy_trivial(const _Tp* __first, const _Tp* __last, _Tp* __result)
  257.     {
  258.       std::memmove(__result, __first, sizeof(_Tp) * (__last - __first));
  259.       return __result + (__last - __first);
  260.     }
  261.  
  262.   template<typename _InputIterator, typename _OutputIterator>
  263.     inline _OutputIterator
  264.     __copy_aux2(_InputIterator __first, _InputIterator __last,
  265.         _OutputIterator __result, __false_type)
  266.     { return std::__copy(__first, __last, __result,
  267.              std::__iterator_category(__first)); }
  268.  
  269.   template<typename _InputIterator, typename _OutputIterator>
  270.     inline _OutputIterator
  271.     __copy_aux2(_InputIterator __first, _InputIterator __last,
  272.         _OutputIterator __result, __true_type)
  273.     { return std::__copy(__first, __last, __result,
  274.              std::__iterator_category(__first)); }
  275.  
  276.   template<typename _Tp>
  277.     inline _Tp*
  278.     __copy_aux2(_Tp* __first, _Tp* __last, _Tp* __result, __true_type)
  279.     { return std::__copy_trivial(__first, __last, __result); }
  280.  
  281.   template<typename _Tp>
  282.     inline _Tp*
  283.     __copy_aux2(const _Tp* __first, const _Tp* __last, _Tp* __result,
  284.         __true_type)
  285.     { return std::__copy_trivial(__first, __last, __result); }
  286.  
  287.   template<typename _InputIterator, typename _OutputIterator>
  288.     inline _OutputIterator
  289.     __copy_ni2(_InputIterator __first, _InputIterator __last,
  290.            _OutputIterator __result, __true_type)
  291.     {
  292.       typedef typename iterator_traits<_InputIterator>::value_type
  293.     _ValueType;
  294.       typedef typename __type_traits<
  295.     _ValueType>::has_trivial_assignment_operator _Trivial;
  296.       return _OutputIterator(std::__copy_aux2(__first, __last, __result.base(),
  297.                           _Trivial()));
  298.     }
  299.  
  300.   template<typename _InputIterator, typename _OutputIterator>
  301.     inline _OutputIterator
  302.     __copy_ni2(_InputIterator __first, _InputIterator __last,
  303.            _OutputIterator __result, __false_type)
  304.     {
  305.       typedef typename iterator_traits<_InputIterator>::value_type _ValueType;
  306.       typedef typename __type_traits<
  307.     _ValueType>::has_trivial_assignment_operator _Trivial;
  308.       return std::__copy_aux2(__first, __last, __result, _Trivial());
  309.     }
  310.  
  311.   template<typename _InputIterator, typename _OutputIterator>
  312.     inline _OutputIterator
  313.     __copy_ni1(_InputIterator __first, _InputIterator __last,
  314.            _OutputIterator __result, __true_type)
  315.     {
  316.       typedef typename _Is_normal_iterator<_OutputIterator>::_Normal __Normal;
  317.       return std::__copy_ni2(__first.base(), __last.base(),
  318.                  __result, __Normal());
  319.     }
  320.  
  321.   template<typename _InputIterator, typename _OutputIterator>
  322.     inline _OutputIterator
  323.     __copy_ni1(_InputIterator __first, _InputIterator __last,
  324.            _OutputIterator __result, __false_type)
  325.     {
  326.       typedef typename _Is_normal_iterator<_OutputIterator>::_Normal __Normal;
  327.       return std::__copy_ni2(__first, __last, __result, __Normal());
  328.     }
  329.  
  330.   /**
  331.    *  @brief Copies the range [first,last) into result.
  332.    *  @param  first  An input iterator.
  333.    *  @param  last   An input iterator.
  334.    *  @param  result An output iterator.
  335.    *  @return   result + (first - last)
  336.    *
  337.    *  This inline function will boil down to a call to @c memmove whenever
  338.    *  possible.  Failing that, if random access iterators are passed, then the
  339.    *  loop count will be known (and therefore a candidate for compiler
  340.    *  optimizations such as unrolling).  Result may not be contained within
  341.    *  [first,last); the copy_backward function should be used instead.
  342.    *
  343.    *  Note that the end of the output range is permitted to be contained
  344.    *  within [first,last).
  345.   */
  346.   template<typename _InputIterator, typename _OutputIterator>
  347.     inline _OutputIterator
  348.     copy(_InputIterator __first, _InputIterator __last,
  349.      _OutputIterator __result)
  350.     {
  351.       // concept requirements
  352.       __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
  353.       __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,
  354.         typename iterator_traits<_InputIterator>::value_type>)
  355.       __glibcxx_requires_valid_range(__first, __last);
  356.  
  357.        typedef typename _Is_normal_iterator<_InputIterator>::_Normal __Normal;
  358.        return std::__copy_ni1(__first, __last, __result, __Normal());
  359.     }
  360.  
  361.   template<typename _BidirectionalIterator1, typename _BidirectionalIterator2>
  362.     inline _BidirectionalIterator2
  363.     __copy_backward(_BidirectionalIterator1 __first,
  364.             _BidirectionalIterator1 __last,
  365.             _BidirectionalIterator2 __result,
  366.             bidirectional_iterator_tag)
  367.     {
  368.       while (__first != __last)
  369.         *--__result = *--__last;
  370.       return __result;
  371.     }
  372.  
  373.   template<typename _RandomAccessIterator, typename _BidirectionalIterator>
  374.     inline _BidirectionalIterator
  375.     __copy_backward(_RandomAccessIterator __first, _RandomAccessIterator __last,
  376.             _BidirectionalIterator __result, random_access_iterator_tag)
  377.     {
  378.       typename iterator_traits<_RandomAccessIterator>::difference_type __n;
  379.       for (__n = __last - __first; __n > 0; --__n)
  380.         *--__result = *--__last;
  381.       return __result;
  382.     }
  383.  
  384.  
  385.   // This dispatch class is a workaround for compilers that do not
  386.   // have partial ordering of function templates.  All we're doing is
  387.   // creating a specialization so that we can turn a call to copy_backward
  388.   // into a memmove whenever possible.
  389.   template<typename _BidirectionalIterator1, typename _BidirectionalIterator2,
  390.            typename _BoolType>
  391.     struct __copy_backward_dispatch
  392.     {
  393.       static _BidirectionalIterator2
  394.       copy(_BidirectionalIterator1 __first, _BidirectionalIterator1 __last,
  395.        _BidirectionalIterator2 __result)
  396.       { return std::__copy_backward(__first, __last, __result,
  397.                     std::__iterator_category(__first)); }
  398.     };
  399.  
  400.   template<typename _Tp>
  401.     struct __copy_backward_dispatch<_Tp*, _Tp*, __true_type>
  402.     {
  403.       static _Tp*
  404.       copy(const _Tp* __first, const _Tp* __last, _Tp* __result)
  405.       {
  406.     const ptrdiff_t _Num = __last - __first;
  407.     std::memmove(__result - _Num, __first, sizeof(_Tp) * _Num);
  408.     return __result - _Num;
  409.       }
  410.     };
  411.  
  412.   template<typename _Tp>
  413.     struct __copy_backward_dispatch<const _Tp*, _Tp*, __true_type>
  414.     {
  415.       static _Tp*
  416.       copy(const _Tp* __first, const _Tp* __last, _Tp* __result)
  417.       {
  418.     return  std::__copy_backward_dispatch<_Tp*, _Tp*, __true_type>
  419.       ::copy(__first, __last, __result);
  420.       }
  421.     };
  422.  
  423.   template<typename _BI1, typename _BI2>
  424.     inline _BI2
  425.     __copy_backward_aux(_BI1 __first, _BI1 __last, _BI2 __result)
  426.     {
  427.       typedef typename __type_traits<typename iterator_traits<_BI2>::value_type>
  428.                 ::has_trivial_assignment_operator _Trivial;
  429.       return
  430.     std::__copy_backward_dispatch<_BI1, _BI2, _Trivial>::copy(__first,
  431.                                   __last,
  432.                                   __result);
  433.     }
  434.  
  435.   template <typename _BI1, typename _BI2>
  436.     inline _BI2
  437.     __copy_backward_output_normal_iterator(_BI1 __first, _BI1 __last,
  438.                        _BI2 __result, __true_type)
  439.     { return _BI2(std::__copy_backward_aux(__first, __last, __result.base())); }
  440.  
  441.   template <typename _BI1, typename _BI2>
  442.     inline _BI2
  443.     __copy_backward_output_normal_iterator(_BI1 __first, _BI1 __last,
  444.                        _BI2 __result, __false_type)
  445.     { return std::__copy_backward_aux(__first, __last, __result); }
  446.  
  447.   template <typename _BI1, typename _BI2>
  448.     inline _BI2
  449.     __copy_backward_input_normal_iterator(_BI1 __first, _BI1 __last,
  450.                       _BI2 __result, __true_type)
  451.     {
  452.       typedef typename _Is_normal_iterator<_BI2>::_Normal __Normal;
  453.       return std::__copy_backward_output_normal_iterator(__first.base(),
  454.                              __last.base(),
  455.                              __result, __Normal());
  456.     }
  457.  
  458.   template <typename _BI1, typename _BI2>
  459.     inline _BI2
  460.     __copy_backward_input_normal_iterator(_BI1 __first, _BI1 __last,
  461.                       _BI2 __result, __false_type)
  462.     {
  463.       typedef typename _Is_normal_iterator<_BI2>::_Normal __Normal;
  464.       return std::__copy_backward_output_normal_iterator(__first, __last,
  465.                              __result, __Normal());
  466.     }
  467.  
  468.   /**
  469.    *  @brief Copies the range [first,last) into result.
  470.    *  @param  first  A bidirectional iterator.
  471.    *  @param  last   A bidirectional iterator.
  472.    *  @param  result A bidirectional iterator.
  473.    *  @return   result - (first - last)
  474.    *
  475.    *  The function has the same effect as copy, but starts at the end of the
  476.    *  range and works its way to the start, returning the start of the result.
  477.    *  This inline function will boil down to a call to @c memmove whenever
  478.    *  possible.  Failing that, if random access iterators are passed, then the
  479.    *  loop count will be known (and therefore a candidate for compiler
  480.    *  optimizations such as unrolling).
  481.    *
  482.    *  Result may not be in the range [first,last).  Use copy instead.  Note
  483.    *  that the start of the output range may overlap [first,last).
  484.   */
  485.   template <typename _BI1, typename _BI2>
  486.     inline _BI2
  487.     copy_backward(_BI1 __first, _BI1 __last, _BI2 __result)
  488.     {
  489.       // concept requirements
  490.       __glibcxx_function_requires(_BidirectionalIteratorConcept<_BI1>)
  491.       __glibcxx_function_requires(_Mutable_BidirectionalIteratorConcept<_BI2>)
  492.       __glibcxx_function_requires(_ConvertibleConcept<
  493.         typename iterator_traits<_BI1>::value_type,
  494.         typename iterator_traits<_BI2>::value_type>)
  495.       __glibcxx_requires_valid_range(__first, __last);
  496.  
  497.       typedef typename _Is_normal_iterator<_BI1>::_Normal __Normal;
  498.       return std::__copy_backward_input_normal_iterator(__first, __last,
  499.                             __result, __Normal());
  500.     }
  501.  
  502.  
  503.   /**
  504.    *  @brief Fills the range [first,last) with copies of value.
  505.    *  @param  first  A forward iterator.
  506.    *  @param  last   A forward iterator.
  507.    *  @param  value  A reference-to-const of arbitrary type.
  508.    *  @return   Nothing.
  509.    *
  510.    *  This function fills a range with copies of the same value.  For one-byte
  511.    *  types filling contiguous areas of memory, this becomes an inline call to
  512.    *  @c memset.
  513.   */
  514.   template<typename _ForwardIterator, typename _Tp>
  515.     void
  516.     fill(_ForwardIterator __first, _ForwardIterator __last, const _Tp& __value)
  517.     {
  518.       // concept requirements
  519.       __glibcxx_function_requires(_Mutable_ForwardIteratorConcept<
  520.                   _ForwardIterator>)
  521.       __glibcxx_requires_valid_range(__first, __last);
  522.  
  523.       for ( ; __first != __last; ++__first)
  524.     *__first = __value;
  525.     }
  526.  
  527.   /**
  528.    *  @brief Fills the range [first,first+n) with copies of value.
  529.    *  @param  first  An output iterator.
  530.    *  @param  n      The count of copies to perform.
  531.    *  @param  value  A reference-to-const of arbitrary type.
  532.    *  @return   The iterator at first+n.
  533.    *
  534.    *  This function fills a range with copies of the same value.  For one-byte
  535.    *  types filling contiguous areas of memory, this becomes an inline call to
  536.    *  @c memset.
  537.   */
  538.   template<typename _OutputIterator, typename _Size, typename _Tp>
  539.     _OutputIterator
  540.     fill_n(_OutputIterator __first, _Size __n, const _Tp& __value)
  541.     {
  542.       // concept requirements
  543.       __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,_Tp>)
  544.  
  545.       for ( ; __n > 0; --__n, ++__first)
  546.     *__first = __value;
  547.       return __first;
  548.     }
  549.  
  550.   // Specialization: for one-byte types we can use memset.
  551.   inline void
  552.   fill(unsigned char* __first, unsigned char* __last, const unsigned char& __c)
  553.   {
  554.     __glibcxx_requires_valid_range(__first, __last);
  555.     const unsigned char __tmp = __c;
  556.     std::memset(__first, __tmp, __last - __first);
  557.   }
  558.  
  559.   inline void
  560.   fill(signed char* __first, signed char* __last, const signed char& __c)
  561.   {
  562.     __glibcxx_requires_valid_range(__first, __last);
  563.     const signed char __tmp = __c;
  564.     std::memset(__first, static_cast<unsigned char>(__tmp), __last - __first);
  565.   }
  566.  
  567.   inline void
  568.   fill(char* __first, char* __last, const char& __c)
  569.   {
  570.     __glibcxx_requires_valid_range(__first, __last);
  571.     const char __tmp = __c;
  572.     std::memset(__first, static_cast<unsigned char>(__tmp), __last - __first);
  573.   }
  574.  
  575.   template<typename _Size>
  576.     inline unsigned char*
  577.     fill_n(unsigned char* __first, _Size __n, const unsigned char& __c)
  578.     {
  579.       std::fill(__first, __first + __n, __c);
  580.       return __first + __n;
  581.     }
  582.  
  583.   template<typename _Size>
  584.     inline signed char*
  585.     fill_n(char* __first, _Size __n, const signed char& __c)
  586.     {
  587.       std::fill(__first, __first + __n, __c);
  588.       return __first + __n;
  589.     }
  590.  
  591.   template<typename _Size>
  592.     inline char*
  593.     fill_n(char* __first, _Size __n, const char& __c)
  594.     {
  595.       std::fill(__first, __first + __n, __c);
  596.       return __first + __n;
  597.     }
  598.  
  599.  
  600.   /**
  601.    *  @brief Finds the places in ranges which don't match.
  602.    *  @param  first1  An input iterator.
  603.    *  @param  last1   An input iterator.
  604.    *  @param  first2  An input iterator.
  605.    *  @return   A pair of iterators pointing to the first mismatch.
  606.    *
  607.    *  This compares the elements of two ranges using @c == and returns a pair
  608.    *  of iterators.  The first iterator points into the first range, the
  609.    *  second iterator points into the second range, and the elements pointed
  610.    *  to by the iterators are not equal.
  611.   */
  612.   template<typename _InputIterator1, typename _InputIterator2>
  613.     pair<_InputIterator1, _InputIterator2>
  614.     mismatch(_InputIterator1 __first1, _InputIterator1 __last1,
  615.          _InputIterator2 __first2)
  616.     {
  617.       // concept requirements
  618.       __glibcxx_function_requires(_InputIteratorConcept<_InputIterator1>)
  619.       __glibcxx_function_requires(_InputIteratorConcept<_InputIterator2>)
  620.       __glibcxx_function_requires(_EqualityComparableConcept<
  621.         typename iterator_traits<_InputIterator1>::value_type>)
  622.       __glibcxx_function_requires(_EqualityComparableConcept<
  623.         typename iterator_traits<_InputIterator2>::value_type>)
  624.       __glibcxx_requires_valid_range(__first1, __last1);
  625.  
  626.       while (__first1 != __last1 && *__first1 == *__first2)
  627.         {
  628.       ++__first1;
  629.       ++__first2;
  630.         }
  631.       return pair<_InputIterator1, _InputIterator2>(__first1, __first2);
  632.     }
  633.  
  634.   /**
  635.    *  @brief Finds the places in ranges which don't match.
  636.    *  @param  first1  An input iterator.
  637.    *  @param  last1   An input iterator.
  638.    *  @param  first2  An input iterator.
  639.    *  @param  binary_pred  A binary predicate @link s20_3_1_base functor@endlink.
  640.    *  @return   A pair of iterators pointing to the first mismatch.
  641.    *
  642.    *  This compares the elements of two ranges using the binary_pred
  643.    *  parameter, and returns a pair
  644.    *  of iterators.  The first iterator points into the first range, the
  645.    *  second iterator points into the second range, and the elements pointed
  646.    *  to by the iterators are not equal.
  647.   */
  648.   template<typename _InputIterator1, typename _InputIterator2,
  649.        typename _BinaryPredicate>
  650.     pair<_InputIterator1, _InputIterator2>
  651.     mismatch(_InputIterator1 __first1, _InputIterator1 __last1,
  652.          _InputIterator2 __first2, _BinaryPredicate __binary_pred)
  653.     {
  654.       // concept requirements
  655.       __glibcxx_function_requires(_InputIteratorConcept<_InputIterator1>)
  656.       __glibcxx_function_requires(_InputIteratorConcept<_InputIterator2>)
  657.       __glibcxx_requires_valid_range(__first1, __last1);
  658.  
  659.       while (__first1 != __last1 && __binary_pred(*__first1, *__first2))
  660.         {
  661.       ++__first1;
  662.       ++__first2;
  663.         }
  664.       return pair<_InputIterator1, _InputIterator2>(__first1, __first2);
  665.     }
  666.  
  667.   /**
  668.    *  @brief Tests a range for element-wise equality.
  669.    *  @param  first1  An input iterator.
  670.    *  @param  last1   An input iterator.
  671.    *  @param  first2  An input iterator.
  672.    *  @return   A boolean true or false.
  673.    *
  674.    *  This compares the elements of two ranges using @c == and returns true or
  675.    *  false depending on whether all of the corresponding elements of the
  676.    *  ranges are equal.
  677.   */
  678.   template<typename _InputIterator1, typename _InputIterator2>
  679.     inline bool
  680.     equal(_InputIterator1 __first1, _InputIterator1 __last1,
  681.       _InputIterator2 __first2)
  682.     {
  683.       // concept requirements
  684.       __glibcxx_function_requires(_InputIteratorConcept<_InputIterator1>)
  685.       __glibcxx_function_requires(_InputIteratorConcept<_InputIterator2>)
  686.       __glibcxx_function_requires(_EqualOpConcept<
  687.         typename iterator_traits<_InputIterator1>::value_type,
  688.         typename iterator_traits<_InputIterator2>::value_type>)
  689.       __glibcxx_requires_valid_range(__first1, __last1);
  690.  
  691.       for ( ; __first1 != __last1; ++__first1, ++__first2)
  692.     if (!(*__first1 == *__first2))
  693.       return false;
  694.       return true;
  695.     }
  696.  
  697.   /**
  698.    *  @brief Tests a range for element-wise equality.
  699.    *  @param  first1  An input iterator.
  700.    *  @param  last1   An input iterator.
  701.    *  @param  first2  An input iterator.
  702.    *  @param  binary_pred  A binary predicate @link s20_3_1_base functor@endlink.
  703.    *  @return   A boolean true or false.
  704.    *
  705.    *  This compares the elements of two ranges using the binary_pred
  706.    *  parameter, and returns true or
  707.    *  false depending on whether all of the corresponding elements of the
  708.    *  ranges are equal.
  709.   */
  710.   template<typename _InputIterator1, typename _InputIterator2,
  711.        typename _BinaryPredicate>
  712.     inline bool
  713.     equal(_InputIterator1 __first1, _InputIterator1 __last1,
  714.       _InputIterator2 __first2,
  715.       _BinaryPredicate __binary_pred)
  716.     {
  717.       // concept requirements
  718.       __glibcxx_function_requires(_InputIteratorConcept<_InputIterator1>)
  719.       __glibcxx_function_requires(_InputIteratorConcept<_InputIterator2>)
  720.       __glibcxx_requires_valid_range(__first1, __last1);
  721.  
  722.       for ( ; __first1 != __last1; ++__first1, ++__first2)
  723.     if (!__binary_pred(*__first1, *__first2))
  724.       return false;
  725.       return true;
  726.     }
  727.  
  728.   /**
  729.    *  @brief Performs "dictionary" comparison on ranges.
  730.    *  @param  first1  An input iterator.
  731.    *  @param  last1   An input iterator.
  732.    *  @param  first2  An input iterator.
  733.    *  @param  last2   An input iterator.
  734.    *  @return   A boolean true or false.
  735.    *
  736.    *  "Returns true if the sequence of elements defined by the range
  737.    *  [first1,last1) is lexicographically less than the sequence of elements
  738.    *  defined by the range [first2,last2).  Returns false otherwise."
  739.    *  (Quoted from [25.3.8]/1.)  If the iterators are all character pointers,
  740.    *  then this is an inline call to @c memcmp.
  741.   */
  742.   template<typename _InputIterator1, typename _InputIterator2>
  743.     bool
  744.     lexicographical_compare(_InputIterator1 __first1, _InputIterator1 __last1,
  745.                 _InputIterator2 __first2, _InputIterator2 __last2)
  746.     {
  747.       // concept requirements
  748.       __glibcxx_function_requires(_InputIteratorConcept<_InputIterator1>)
  749.       __glibcxx_function_requires(_InputIteratorConcept<_InputIterator2>)
  750.       __glibcxx_function_requires(_LessThanComparableConcept<
  751.         typename iterator_traits<_InputIterator1>::value_type>)
  752.       __glibcxx_function_requires(_LessThanComparableConcept<
  753.         typename iterator_traits<_InputIterator2>::value_type>)
  754.       __glibcxx_requires_valid_range(__first1, __last1);
  755.       __glibcxx_requires_valid_range(__first2, __last2);
  756.  
  757.       for (;__first1 != __last1 && __first2 != __last2; ++__first1, ++__first2)
  758.     {
  759.       if (*__first1 < *__first2)
  760.         return true;
  761.       if (*__first2 < *__first1)
  762.         return false;
  763.     }
  764.       return __first1 == __last1 && __first2 != __last2;
  765.     }
  766.  
  767.   /**
  768.    *  @brief Performs "dictionary" comparison on ranges.
  769.    *  @param  first1  An input iterator.
  770.    *  @param  last1   An input iterator.
  771.    *  @param  first2  An input iterator.
  772.    *  @param  last2   An input iterator.
  773.    *  @param  comp  A @link s20_3_3_comparisons comparison functor@endlink.
  774.    *  @return   A boolean true or false.
  775.    *
  776.    *  The same as the four-parameter @c lexigraphical_compare, but uses the
  777.    *  comp parameter instead of @c <.
  778.   */
  779.   template<typename _InputIterator1, typename _InputIterator2,
  780.        typename _Compare>
  781.     bool
  782.     lexicographical_compare(_InputIterator1 __first1, _InputIterator1 __last1,
  783.                 _InputIterator2 __first2, _InputIterator2 __last2,
  784.                 _Compare __comp)
  785.     {
  786.       // concept requirements
  787.       __glibcxx_function_requires(_InputIteratorConcept<_InputIterator1>)
  788.       __glibcxx_function_requires(_InputIteratorConcept<_InputIterator2>)
  789.       __glibcxx_requires_valid_range(__first1, __last1);
  790.       __glibcxx_requires_valid_range(__first2, __last2);
  791.  
  792.       for ( ; __first1 != __last1 && __first2 != __last2
  793.         ; ++__first1, ++__first2)
  794.     {
  795.       if (__comp(*__first1, *__first2))
  796.         return true;
  797.       if (__comp(*__first2, *__first1))
  798.         return false;
  799.     }
  800.       return __first1 == __last1 && __first2 != __last2;
  801.     }
  802.  
  803.   inline bool
  804.   lexicographical_compare(const unsigned char* __first1,
  805.               const unsigned char* __last1,
  806.               const unsigned char* __first2,
  807.               const unsigned char* __last2)
  808.   {
  809.     __glibcxx_requires_valid_range(__first1, __last1);
  810.     __glibcxx_requires_valid_range(__first2, __last2);
  811.  
  812.     const size_t __len1 = __last1 - __first1;
  813.     const size_t __len2 = __last2 - __first2;
  814.     const int __result = std::memcmp(__first1, __first2,
  815.                      std::min(__len1, __len2));
  816.     return __result != 0 ? __result < 0 : __len1 < __len2;
  817.   }
  818.  
  819.   inline bool
  820.   lexicographical_compare(const char* __first1, const char* __last1,
  821.               const char* __first2, const char* __last2)
  822.   {
  823.     __glibcxx_requires_valid_range(__first1, __last1);
  824.     __glibcxx_requires_valid_range(__first2, __last2);
  825.  
  826. #if CHAR_MAX == SCHAR_MAX
  827.     return std::lexicographical_compare((const signed char*) __first1,
  828.                     (const signed char*) __last1,
  829.                     (const signed char*) __first2,
  830.                     (const signed char*) __last2);
  831. #else /* CHAR_MAX == SCHAR_MAX */
  832.     return std::lexicographical_compare((const unsigned char*) __first1,
  833.                     (const unsigned char*) __last1,
  834.                     (const unsigned char*) __first2,
  835.                     (const unsigned char*) __last2);
  836. #endif /* CHAR_MAX == SCHAR_MAX */
  837.   }
  838.  
  839. } // namespace std
  840.  
  841. #endif
  842.