好记性不如铅笔头

C && C++, C++ STL, 编程

C++ STL 读书笔记:stl_uninitialized.h

备注:

本读书笔记基于侯捷先生的《STL源码剖析》,截图和注释版权均属于原作者所有。
本读书笔记中的源码部分直接拷贝自SGI-STL,部分代码删除了头部的版权注释,但代码版权属于原作者
小弟初看stl,很多代码都不是太懂,注释可能有很多错误,还请路过的各位大牛多多给予指导。

stl_uninitialized.h

stl_uninitialized.h中提供了一些内存工具,用来快速初始化或者拷贝实例。这里注释下源码。

#ifndef _STL_UNINITIALIZED_H
#define _STL_UNINITIALIZED_H 1

_GLIBCXX_BEGIN_NAMESPACE(std)//以下均在std命名空间中

  template<bool>
    struct __uninitialized_copy
    {
    	//静态函数,便于调用
    	//此版本的拷贝函数通过__first和__last间的iterator,调用std::_Construct方法初始化
    	//以__result为起始指针的内存区域。
      template<typename _InputIterator, typename _ForwardIterator>
        static _ForwardIterator
        uninitialized_copy(_InputIterator __first, _InputIterator __last,
			   _ForwardIterator __result)
        {
	  _ForwardIterator __cur = __result;
	  __try
	    {//__cur起始指向__result,后在循环中不断递增,配合__first不断递增,可以将__result为
	    //起始指针的内存区域进行初始化
	      for (; __first != __last; ++__first, ++__cur)
		std::_Construct(&*__cur, *__first);
	      return __cur;
	    }
	  __catch(...)
	    {//commit or rollback
	    //如果循环中有任何异常,直接全部_Destroy
	    //(该函数的第一个参数为__result,为待初始化内存的起始位置,第二个参数为当前已经初始化的位置)
	      std::_Destroy(__result, __cur);
	      __throw_exception_again;
	    }
	}
    };
	
	//同上,为特化版本。
	//当实例的内容比较简单(POD类型),可以直接进行memcpy时,
	//直接调用std::copy(memcpy)方式高效的进行拷贝。
  template<>
    struct __uninitialized_copy<true>
    {
      template<typename _InputIterator, typename _ForwardIterator>
        static _ForwardIterator
        uninitialized_copy(_InputIterator __first, _InputIterator __last,
			   _ForwardIterator __result)
        { return std::copy(__first, __last, __result); }
    };

  /**
   *  @brief Copies the range [first,last) into result.
   *  @param  first  An input iterator.
   *  @param  last   An input iterator.
   *  @param  result An output iterator.
   *  @return   result + (first - last)
   *
   *  Like copy(), but does not require an initialized output range.
  */
  //拷贝函数,根据拷贝实例的复杂程度(是否POD),来决定调用上面的哪个版本的拷贝函数
  template<typename _InputIterator, typename _ForwardIterator>
    inline _ForwardIterator
    uninitialized_copy(_InputIterator __first, _InputIterator __last,
		       _ForwardIterator __result)
    {
      typedef typename iterator_traits<_InputIterator>::value_type
	_ValueType1;
      typedef typename iterator_traits<_ForwardIterator>::value_type
	_ValueType2;

//根据是否是POD类型,来确认调用的结构体的函数(是模板,还是特化版本的)
      return std::__uninitialized_copy<(__is_pod(_ValueType1)
					&& __is_pod(_ValueType2))>::
	uninitialized_copy(__first, __last, __result);
    }

//__uninitialized_fill和上述__uninitialized_copy类似,也是一个模板,一个特化。

//此版本的fill函数通过调用std::_Construct来完成数据的复制。
  template<bool>
    struct __uninitialized_fill
    {
      template<typename _ForwardIterator, typename _Tp>
        static void
        uninitialized_fill(_ForwardIterator __first,
			   _ForwardIterator __last, const _Tp& __x)
        {
	  _ForwardIterator __cur = __first;
	  __try
	    {
	      for (; __cur != __last; ++__cur)
		std::_Construct(&*__cur, __x);//这里的循环中,第二个参数都是__x,即【__first,__last)
						//间的内存全部初始化为__x。
	    }
	  __catch(...)
	    {
	    	//commit or rollback
	    	//如果失败,回滚所有操作,将所有初始化过的内存全部_Destroy。
	      std::_Destroy(__first, __cur);
	      __throw_exception_again;
	    }
	}
    };

//特化的fill版本
//当实例的内容比较简单(POD类型),可以直接进行memset时,
//直接调用std::fill(memset)方式高效的进行拷贝。
  template<>
    struct __uninitialized_fill<true>
    {
      template<typename _ForwardIterator, typename _Tp>
        static void
        uninitialized_fill(_ForwardIterator __first,
			   _ForwardIterator __last, const _Tp& __x)
        { std::fill(__first, __last, __x); }
    };

  /**
   *  @brief Copies the value x into the range [first,last).
   *  @param  first  An input iterator.
   *  @param  last   An input iterator.
   *  @param  x      The source value.
   *  @return   Nothing.
   *
   *  Like fill(), but does not require an initialized output range.
  */
  //fill函数,根据实例是否是POD类型选择不同版本的fill函数
  template<typename _ForwardIterator, typename _Tp>
    inline void
    uninitialized_fill(_ForwardIterator __first, _ForwardIterator __last,
		       const _Tp& __x)
    {
      typedef typename iterator_traits<_ForwardIterator>::value_type
	_ValueType;

      std::__uninitialized_fill<__is_pod(_ValueType)>::
	uninitialized_fill(__first, __last, __x);
    }


	//和copy,fill的实现类似,不过这里是根据构造函数的复杂度来决定调用哪个函数
  template<bool>
    struct __uninitialized_construct_range_dispatch
    {
      template<typename _ForwardIterator, typename _Tp>
        static void
        __ucr(_ForwardIterator __first, _ForwardIterator __last,
	      _Tp& __value)
        {
	  if(__first == __last)
	    return;

	  _ForwardIterator __cur = __first;
	  __try
	    {
	      std::_Construct(&*__first, _GLIBCXX_MOVE(__value));
	      _ForwardIterator __prev = __cur;
	      ++__cur;
	      for(; __cur != __last; ++__cur, ++__prev)
		std::_Construct(&*__cur, _GLIBCXX_MOVE(*__prev));
	      __value = _GLIBCXX_MOVE(*__prev);
	    }
	  __catch(...)
	    {
	      std::_Destroy(__first, __cur);
	      __throw_exception_again;
	    }
	}
    };

  template<>
    struct __uninitialized_construct_range_dispatch<true>
    {
      template<typename _ForwardIterator, typename _Tp>
        static void
        __ucr(_ForwardIterator, _ForwardIterator, _Tp&) { }
    };

  // Constructs objects in the range [first, last).
  // Note that while these new objects will take valid values,
  // their exact value is not defined. In particular they may
  // be 'moved from'.
  //
  // While __value may altered during this algorithm, it will have
  // the same value when the algorithm finishes, unless one of the
  // constructions throws.
  //
  // Requirements: _ForwardIterator::value_type(_Tp&&) is valid.
  template<typename _ForwardIterator, typename _Tp>
    inline void
    __uninitialized_construct_range(_ForwardIterator __first,
				    _ForwardIterator __last,
				    _Tp& __value)
    {
      typedef typename std::iterator_traits<_ForwardIterator>::value_type
	_ValueType;

      std::__uninitialized_construct_range_dispatch<
        __has_trivial_constructor(_ValueType)>::
	  __ucr(__first, __last, __value);
    }

//fill函数的第二个版本,该版本没有last,而是提供了待初始化内存的数目n,通过
//计算n,来控制循环的结束。
  template<bool>
    struct __uninitialized_fill_n
    {
      template<typename _ForwardIterator, typename _Size, typename _Tp>
        static void
        uninitialized_fill_n(_ForwardIterator __first, _Size __n,
			     const _Tp& __x)
        {
	  _ForwardIterator __cur = __first;
	  __try
	    {
	      for (; __n > 0; --__n, ++__cur)
		std::_Construct(&*__cur, __x);
	    }
	  __catch(...)
	    {
	      std::_Destroy(__first, __cur);
	      __throw_exception_again;
	    }
	}
    };

  template<>
    struct __uninitialized_fill_n<true>
    {
      template<typename _ForwardIterator, typename _Size, typename _Tp>
        static void
        uninitialized_fill_n(_ForwardIterator __first, _Size __n,
			     const _Tp& __x)
        { std::fill_n(__first, __n, __x); }
    };

  /**
   *  @brief Copies the value x into the range [first,first+n).
   *  @param  first  An input iterator.
   *  @param  n      The number of copies to make.
   *  @param  x      The source value.
   *  @return   Nothing.
   *
   *  Like fill_n(), but does not require an initialized output range.
  */
  template<typename _ForwardIterator, typename _Size, typename _Tp>
    inline void
    uninitialized_fill_n(_ForwardIterator __first, _Size __n, const _Tp& __x)
    {
      typedef typename iterator_traits<_ForwardIterator>::value_type
	_ValueType;

      std::__uninitialized_fill_n<__is_pod(_ValueType)>::
	uninitialized_fill_n(__first, __n, __x);
    }

  // Extensions: versions of uninitialized_copy, uninitialized_fill,
  //  and uninitialized_fill_n that take an allocator parameter.
  //  We dispatch back to the standard versions when we're given the
  //  default allocator.  For nondefault allocators we do not use 
  //  any of the POD optimizations.

//copy函数的扩展版本,提供了自定义allocator的入参。在调用构造函数时,不在调用std::_Construct
//而是调用__alloc.construct。
  template<typename _InputIterator, typename _ForwardIterator,
	   typename _Allocator>
    _ForwardIterator
    __uninitialized_copy_a(_InputIterator __first, _InputIterator __last,
			   _ForwardIterator __result, _Allocator& __alloc)
    {
      _ForwardIterator __cur = __result;
      __try
	{
	  for (; __first != __last; ++__first, ++__cur)
	    __alloc.construct(&*__cur, *__first);
	  return __cur;
	}
      __catch(...)
	{
	  std::_Destroy(__result, __cur, __alloc);
	  __throw_exception_again;
	}
    }

//同上,特化版本,如果指定的allocator是默认版本的allocator,那么直接调用
//上面的std版本的copy方法。
  template<typename _InputIterator, typename _ForwardIterator, typename _Tp>
    inline _ForwardIterator
    __uninitialized_copy_a(_InputIterator __first, _InputIterator __last,
			   _ForwardIterator __result, allocator<_Tp>&)
    { return std::uninitialized_copy(__first, __last, __result); }

//含自定义allocator入参版本的move函数,直接调用上面的copy实现。
  template<typename _InputIterator, typename _ForwardIterator,
	   typename _Allocator>
    inline _ForwardIterator
    __uninitialized_move_a(_InputIterator __first, _InputIterator __last,
			   _ForwardIterator __result, _Allocator& __alloc)
    {
      return std::__uninitialized_copy_a(_GLIBCXX_MAKE_MOVE_ITERATOR(__first),
					 _GLIBCXX_MAKE_MOVE_ITERATOR(__last),
					 __result, __alloc);
    }

//fill函数的扩展版本,提供了自定义allocator的入参。在调用构造函数时,不在调用std::_Construct
//而是调用__alloc.construct。
  template<typename _ForwardIterator, typename _Tp, typename _Allocator>
    void
    __uninitialized_fill_a(_ForwardIterator __first, _ForwardIterator __last,
			   const _Tp& __x, _Allocator& __alloc)
    {
      _ForwardIterator __cur = __first;
      __try
	{
	  for (; __cur != __last; ++__cur)
	    __alloc.construct(&*__cur, __x);
	}
      __catch(...)
	{
	  std::_Destroy(__first, __cur, __alloc);
	  __throw_exception_again;
	}
    }
//同上,特化版本,如果指定的allocator是默认版本的allocator,那么直接调用
//上面的std版本的fill方法。
  template<typename _ForwardIterator, typename _Tp, typename _Tp2>
    inline void
    __uninitialized_fill_a(_ForwardIterator __first, _ForwardIterator __last,
			   const _Tp& __x, allocator<_Tp2>&)
    { std::uninitialized_fill(__first, __last, __x); }

//fill函数的扩展版本,提供了自定义allocator的入参。且不在提供last,而是提供要初始化的数目n,
//来控制初始化循环的结束。
  template<typename _ForwardIterator, typename _Size, typename _Tp,
	   typename _Allocator>
    void
    __uninitialized_fill_n_a(_ForwardIterator __first, _Size __n, 
			     const _Tp& __x, _Allocator& __alloc)
    {
      _ForwardIterator __cur = __first;
      __try
	{
	  for (; __n > 0; --__n, ++__cur)
	    __alloc.construct(&*__cur, __x);
	}
      __catch(...)
	{
	  std::_Destroy(__first, __cur, __alloc);
	  __throw_exception_again;
	}
    }

  template<typename _ForwardIterator, typename _Size, typename _Tp,
	   typename _Tp2>
    inline void
    __uninitialized_fill_n_a(_ForwardIterator __first, _Size __n, 
			     const _Tp& __x, allocator<_Tp2>&)
    { std::uninitialized_fill_n(__first, __n, __x); }


  // Extensions: __uninitialized_copy_move, __uninitialized_move_copy,
  // __uninitialized_fill_move, __uninitialized_move_fill.
  // All of these algorithms take a user-supplied allocator, which is used
  // for construction and destruction.

  // __uninitialized_copy_move
  // Copies [first1, last1) into [result, result + (last1 - first1)), and
  //  move [first2, last2) into
  //  [result, result + (last1 - first1) + (last2 - first2)).
  template<typename _InputIterator1, typename _InputIterator2,
	   typename _ForwardIterator, typename _Allocator>
    inline _ForwardIterator
    __uninitialized_copy_move(_InputIterator1 __first1,
			      _InputIterator1 __last1,
			      _InputIterator2 __first2,
			      _InputIterator2 __last2,
			      _ForwardIterator __result,
			      _Allocator& __alloc)
    {
      _ForwardIterator __mid = std::__uninitialized_copy_a(__first1, __last1,
							   __result,
							   __alloc);
      __try
	{
	  return std::__uninitialized_move_a(__first2, __last2, __mid, __alloc);
	}
      __catch(...)
	{
	  std::_Destroy(__result, __mid, __alloc);
	  __throw_exception_again;
	}
    }

  // __uninitialized_move_copy
  // Moves [first1, last1) into [result, result + (last1 - first1)), and
  //  copies [first2, last2) into
  //  [result, result + (last1 - first1) + (last2 - first2)).
  template<typename _InputIterator1, typename _InputIterator2,
	   typename _ForwardIterator, typename _Allocator>
    inline _ForwardIterator
    __uninitialized_move_copy(_InputIterator1 __first1,
			      _InputIterator1 __last1,
			      _InputIterator2 __first2,
			      _InputIterator2 __last2,
			      _ForwardIterator __result,
			      _Allocator& __alloc)
    {
      _ForwardIterator __mid = std::__uninitialized_move_a(__first1, __last1,
							   __result,
							   __alloc);
      __try
	{
	  return std::__uninitialized_copy_a(__first2, __last2, __mid, __alloc);
	}
      __catch(...)
	{
	  std::_Destroy(__result, __mid, __alloc);
	  __throw_exception_again;
	}
    }
  
  // __uninitialized_fill_move
  // Fills [result, mid) with x, and moves [first, last) into
  //  [mid, mid + (last - first)).
  template<typename _ForwardIterator, typename _Tp, typename _InputIterator,
	   typename _Allocator>
    inline _ForwardIterator
    __uninitialized_fill_move(_ForwardIterator __result, _ForwardIterator __mid,
			      const _Tp& __x, _InputIterator __first,
			      _InputIterator __last, _Allocator& __alloc)
    {
      std::__uninitialized_fill_a(__result, __mid, __x, __alloc);
      __try
	{
	  return std::__uninitialized_move_a(__first, __last, __mid, __alloc);
	}
      __catch(...)
	{
	  std::_Destroy(__result, __mid, __alloc);
	  __throw_exception_again;
	}
    }

  // __uninitialized_move_fill
  // Moves [first1, last1) into [first2, first2 + (last1 - first1)), and
  //  fills [first2 + (last1 - first1), last2) with x.
  template<typename _InputIterator, typename _ForwardIterator, typename _Tp,
	   typename _Allocator>
    inline void
    __uninitialized_move_fill(_InputIterator __first1, _InputIterator __last1,
			      _ForwardIterator __first2,
			      _ForwardIterator __last2, const _Tp& __x,
			      _Allocator& __alloc)
    {
      _ForwardIterator __mid2 = std::__uninitialized_move_a(__first1, __last1,
							    __first2,
							    __alloc);
      __try
	{
	  std::__uninitialized_fill_a(__mid2, __last2, __x, __alloc);
	}
      __catch(...)
	{
	  std::_Destroy(__first2, __mid2, __alloc);
	  __throw_exception_again;
	}
    }

#ifdef __GXX_EXPERIMENTAL_CXX0X__
  template<typename _InputIterator, typename _Size,
	   typename _ForwardIterator>
    _ForwardIterator
    __uninitialized_copy_n(_InputIterator __first, _Size __n,
			   _ForwardIterator __result, input_iterator_tag)
    {
      _ForwardIterator __cur = __result;
      __try
	{
	  for (; __n > 0; --__n, ++__first, ++__cur)
	    ::new(static_cast<void*>(&*__cur)) typename
		iterator_traits<_ForwardIterator>::value_type(*__first);
	  return __cur;
	}
      __catch(...)
	{
	  std::_Destroy(__result, __cur);
	  __throw_exception_again;
	}
    }

  template<typename _RandomAccessIterator, typename _Size,
	   typename _ForwardIterator>
    inline _ForwardIterator
    __uninitialized_copy_n(_RandomAccessIterator __first, _Size __n,
			   _ForwardIterator __result,
			   random_access_iterator_tag)
    { return std::uninitialized_copy(__first, __first + __n, __result); }

  /**
   *  @brief Copies the range [first,first+n) into result.
   *  @param  first  An input iterator.
   *  @param  n      The number of elements to copy.
   *  @param  result An output iterator.
   *  @return  result + n
   *
   *  Like copy_n(), but does not require an initialized output range.
  */
  template<typename _InputIterator, typename _Size, typename _ForwardIterator>
    inline _ForwardIterator
    uninitialized_copy_n(_InputIterator __first, _Size __n,
			 _ForwardIterator __result)
    { return std::__uninitialized_copy_n(__first, __n, __result,
					 std::__iterator_category(__first)); }
#endif

_GLIBCXX_END_NAMESPACE

#endif /* _STL_UNINITIALIZED_H */

memory:

在memory文件中,也有一部分内存工具,这里简单的注释下代码:

//在__gun_cxx命名空间中
_GLIBCXX_BEGIN_NAMESPACE(__gnu_cxx)

  using std::ptrdiff_t;
  using std::pair;
  using std::__iterator_category;
  using std::_Temporary_buffer;

  template<typename _InputIter, typename _Size, typename _ForwardIter>
    pair<_InputIter, _ForwardIter>//注意这里的返回值,和stl_uninitialized的不同
    __uninitialized_copy_n(_InputIter __first, _Size __count,
			   _ForwardIter __result, std::input_iterator_tag)
    {//最后一个参数为std::input_iterator_tag的特化版本
      _ForwardIter __cur = __result;
      __try
	{
	  for (; __count > 0 ; --__count, ++__first, ++__cur)
	    std::_Construct(&*__cur, *__first);
	  return pair<_InputIter, _ForwardIter>(__first, _cur);//构造返回值
	}
      __catch(...)
	{//commit or rollback
	  std::_Destroy(__result, __cur);
	  __throw_exception_again;
	}
    }

  template<typename _RandomAccessIter, typename _Size, typename _ForwardIter>
    inline pair<_RandomAccessIter, _ForwardIter>
    __uninitialized_copy_n(_RandomAccessIter __first, _Size __count,
			   _ForwardIter __result,
			   std::random_access_iterator_tag)
    {//最后一个参数为std::random_access_iterator_tag的特化版本,直接调用
     //stl_uninitialized中的版本。
     //这里可以这么做的原因为iterator的类型为随机访问类型,因此可以通过相加的方式获取到
     //最后一个iterator(类似于数组,可以通过数据头指针+整数,定位到某一个数组元素的指针)
      _RandomAccessIter __last = __first + __count;
      return (pair<_RandomAccessIter, _ForwardIter>
	      (__last, std::uninitialized_copy(__first, __last, __result)));
    }

//copy函数,返回pair实例,根据__first的类型来确定调用上述两个函数中的哪一个。
  template<typename _InputIter, typename _Size, typename _ForwardIter>
    inline pair<_InputIter, _ForwardIter>
    __uninitialized_copy_n(_InputIter __first, _Size __count,
			   _ForwardIter __result)
    { return __gnu_cxx::__uninitialized_copy_n(__first, __count, __result,
					       __iterator_category(__first)); }

  /**
   *  @brief Copies the range [first,last) into result.
   *  @param  first  An input iterator.
   *  @param  last   An input iterator.
   *  @param  result An output iterator.
   *  @return   result + (first - last)
   *  @ingroup SGIextensions
   *
   *  Like copy(), but does not require an initialized output range.
  */
  //对上面的函数又封装了一次,感觉比较奇怪。
  template<typename _InputIter, typename _Size, typename _ForwardIter>
    inline pair<_InputIter, _ForwardIter>
    uninitialized_copy_n(_InputIter __first, _Size __count,
			 _ForwardIter __result)
    { return __gnu_cxx::__uninitialized_copy_n(__first, __count, __result,
					       __iterator_category(__first)); }


  // An alternative version of uninitialized_copy_n that constructs
  // and destroys objects with a user-provided allocator.
  template<typename _InputIter, typename _Size, typename _ForwardIter,
           typename _Allocator>
    pair<_InputIter, _ForwardIter>//注意这里的返回值
    __uninitialized_copy_n_a(_InputIter __first, _Size __count,
			     _ForwardIter __result,
			     _Allocator __alloc)
    {
      _ForwardIter __cur = __result;
      __try
	{
	  for (; __count > 0 ; --__count, ++__first, ++__cur)
	    __alloc.construct(&*__cur, *__first);
	  return pair<_InputIter, _ForwardIter>(__first, __cur);
	}
      __catch(...)
	{
	  std::_Destroy(__result, __cur, __alloc);
	  __throw_exception_again;
	}
    }

  template<typename _InputIter, typename _Size, typename _ForwardIter,
           typename _Tp>
    inline pair<_InputIter, _ForwardIter>
    __uninitialized_copy_n_a(_InputIter __first, _Size __count,
			     _ForwardIter __result,
			     std::allocator<_Tp>)
    {//如果是默认的allocator,那么可以直接调用__gnu_cxx::uninitialized_copy_n
      return __gnu_cxx::uninitialized_copy_n(__first, __count, __result);
    }

  /**
   *  This class provides similar behavior and semantics of the standard
   *  functions get_temporary_buffer() and return_temporary_buffer(), but
   *  encapsulated in a type vaguely resembling a standard container.
   *
   *  By default, a temporary_buffer<Iter> stores space for objects of
   *  whatever type the Iter iterator points to.  It is constructed from a
   *  typical [first,last) range, and provides the begin(), end(), size()
   *  functions, as well as requested_size().  For non-trivial types, copies
   *  of *first will be used to initialize the storage.
   *
   *  @c malloc is used to obtain underlying storage.
   *
   *  Like get_temporary_buffer(), not all the requested memory may be
   *  available.  Ideally, the created buffer will be large enough to hold a
   *  copy of [first,last), but if size() is less than requested_size(),
   *  then this didn't happen.
   *
   *  @ingroup SGIextensions
  */
  template <class _ForwardIterator, class _Tp
	    = typename std::iterator_traits<_ForwardIterator>::value_type >
    struct temporary_buffer : public _Temporary_buffer<_ForwardIterator, _Tp>
    {
      /// Requests storage large enough to hold a copy of [first,last).
      temporary_buffer(_ForwardIterator __first, _ForwardIterator __last)
      : _Temporary_buffer<_ForwardIterator, _Tp>(__first, __last) { }
      
      /// Destroys objects and frees storage.
      ~temporary_buffer() { }
    };

_GLIBCXX_END_NAMESPACE

 

发表评论

2 × 5 =

此站点使用Akismet来减少垃圾评论。了解我们如何处理您的评论数据