Re: small improvement for fill and fill_n

[Paolo Carlini <pcarlini at suse dot de>]

Hi Dan and sorry for the delay...

> An obvious observation: if the standard was to require that the
> reference 'value' was to be used in each iteration then the
> specializations for "fill"  in stl_algobase.h that use memset for
> one-byte types are incorrect.
In the light of your compelling observation, barring clarifications to
the standard, I'm testing the attached patch, which uses your idea only
when it will certainly pay off.

If nobody objects to the general approach, I will also add testcases,
of course, long missing.

Paolo.

/////////////
diff -prN libstdc++-v3-orig/include/bits/stl_algobase.h libstdc++-v3/include/bits/stl_algobase.h
*** libstdc++-v3-orig/include/bits/stl_algobase.h	Sun Feb  8 05:46:41 2004
--- libstdc++-v3/include/bits/stl_algobase.h	Thu Jun 24 00:27:48 2004
*************** namespace std
*** 499,504 ****
--- 499,530 ----
  							__result, __Normal());
      }
  
+   template<typename>
+     struct __fill
+     {
+       template<typename _ForwardIterator, typename _Tp>
+         static void
+         fill(_ForwardIterator __first, _ForwardIterator __last,
+ 	     const _Tp& __value)
+         {
+ 	  for (; __first != __last; ++__first)
+ 	    *__first = __value;
+ 	}
+     };
+ 
+   template<>
+     struct __fill<__true_type>
+     {
+       template<typename _ForwardIterator, typename _Tp>
+         static void
+         fill(_ForwardIterator __first, _ForwardIterator __last,
+ 	     const _Tp& __value)
+         {
+ 	  const _Tp __tmp = __value;
+ 	  for (; __first != __last; ++__first)
+ 	    *__first = __tmp;
+ 	}
+     };
  
    /**
     *  @brief Fills the range [first,last) with copies of value.
*************** namespace std
*** 520,550 ****
  				  _ForwardIterator>)
        __glibcxx_requires_valid_range(__first, __last);
  
!       for ( ; __first != __last; ++__first)
! 	*__first = __value;
!     }
! 
!   /**
!    *  @brief Fills the range [first,first+n) with copies of value.
!    *  @param  first  An output iterator.
!    *  @param  n      The count of copies to perform.
!    *  @param  value  A reference-to-const of arbitrary type.
!    *  @return   The iterator at first+n.
!    *
!    *  This function fills a range with copies of the same value.  For one-byte
!    *  types filling contiguous areas of memory, this becomes an inline call to
!    *  @c memset.
!   */
!   template<typename _OutputIterator, typename _Size, typename _Tp>
!     _OutputIterator
!     fill_n(_OutputIterator __first, _Size __n, const _Tp& __value)
!     {
!       // concept requirements
!       __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator,_Tp>)
! 
!       for ( ; __n > 0; --__n, ++__first)
! 	*__first = __value;
!       return __first;
      }
  
    // Specialization: for one-byte types we can use memset.
--- 546,554 ----
  				  _ForwardIterator>)
        __glibcxx_requires_valid_range(__first, __last);
  
!       typedef typename __type_traits<_Tp>::has_trivial_copy_constructor
! 	_Trivial;
!       std::__fill<_Trivial>::fill(__first, __last, __value);
      }
  
    // Specialization: for one-byte types we can use memset.
*************** namespace std
*** 572,577 ****
--- 576,631 ----
      std::memset(__first, static_cast<unsigned char>(__tmp), __last - __first);
    }
  
+   template<typename>
+     struct __fill_n
+     {
+       template<typename _OutputIterator, typename _Size, typename _Tp>
+         static _OutputIterator
+         fill_n(_OutputIterator __first, _Size __n, const _Tp& __value)
+         {
+ 	  for (; __n > 0; --__n, ++__first)
+ 	    *__first = __value;
+ 	  return __first;
+ 	}
+     };
+ 
+   template<>
+     struct __fill_n<__true_type>
+     {
+       template<typename _OutputIterator, typename _Size, typename _Tp>
+         static _OutputIterator
+         fill_n(_OutputIterator __first, _Size __n, const _Tp& __value)
+         {
+ 	  const _Tp __tmp = __value;
+ 	  for (; __n > 0; --__n, ++__first)
+ 	    *__first = __tmp;
+ 	  return __first;	  
+ 	}
+     };
+ 
+   /**
+    *  @brief Fills the range [first,first+n) with copies of value.
+    *  @param  first  An output iterator.
+    *  @param  n      The count of copies to perform.
+    *  @param  value  A reference-to-const of arbitrary type.
+    *  @return   The iterator at first+n.
+    *
+    *  This function fills a range with copies of the same value.  For one-byte
+    *  types filling contiguous areas of memory, this becomes an inline call to
+    *  @c memset.
+   */
+   template<typename _OutputIterator, typename _Size, typename _Tp>
+     _OutputIterator
+     fill_n(_OutputIterator __first, _Size __n, const _Tp& __value)
+     {
+       // concept requirements
+       __glibcxx_function_requires(_OutputIteratorConcept<_OutputIterator, _Tp>)
+ 
+       typedef typename __type_traits<_Tp>::has_trivial_copy_constructor
+ 	_Trivial;
+       return std::__fill_n<_Trivial>::fill_n(__first, __n, __value);
+     }
+ 
    template<typename _Size>
      inline unsigned char*
      fill_n(unsigned char* __first, _Size __n, const unsigned char& __c)
*************** namespace std
*** 596,602 ****
        return __first + __n;
      }
  
- 
    /**
     *  @brief Finds the places in ranges which don't match.
     *  @param  first1  An input iterator.
--- 650,655 ----