CONTENTS
备注：
本读书笔记基于侯捷先生的《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
发表评论