STL — 源码剖析常见的内存处理工具(<stl_uninitialized.h>)

内存基本处理工具

STL定义有5个全局函数,作用于未初始化空间上，这样的功能对于容器的实现很有帮助，我们会在容器实现源码当中，看到他们肩负的责任. 现在我们

来 认识一下这5个全局函数并且对他们进行源码剖析认识他们的结构. 5个全局 函数分别为:用于构造的construct() 用于析构的destroy()，用于数 据拷

贝uninitialized_copy()，用于初始化 uninitialized_fill()和uninitialized_fill_n(). 首先这个5个函数都被定义在<memory>当中，并且几乎占了半

壁江山. 也就是说 他们和空间配置器平起平坐，然而我们以前已经了解过空间配置器了，所以今天的目标很明确，了解清楚<memory>里面的所有文件，

通读这5个全局函 数的源代码，理解他们的原理和应用场景.  我们后面对应的三个函数分别对应于高层次的函数 copy()， fill()，fill_n() --这些都是

STL的算法. 它们分别的意义如果 你不了解，我觉得你很有必要去了解，因为这些函数太重要了. 当然如果你想 使用本节的 三个低层次函数，应该包含

<memory>，不过呢SGI把它们定义 于<stl_uninitialized>  那我们开始理解这些函数, 并且下面这张图就是<memory>当中的结构图：

construct()和destroy()

#ifndef __SGI_STL_INTERNAL_CONSTRUCT_H
#define __SGI_STL_INTERNAL_CONSTRUCT_H

#include <new.h> //欲使用placement new 需先包含此文件

__STL_BEGIN_NAMESPACE


template <class T1, class T2>
inline void construct(T1* p, const T2& value) {  //想想上面说construct的功能
	new (p)T1(value); //在p的空间上面调用构造函数.
}

//最经典的版本
template <class T>
inline void destroy(T* pointer) {
	pointer->~T();
}

//这个版本的destroy只接受两个迭代器，此函数设法找到元素的数值类型.然后传给__dertroy.
template <class ForwardIterator>
inline void destroy(ForwardIterator first, ForwardIterator last) {
	__destroy(first, last, value_type(first));
}

//这里的__type_traits就是类型萃取，关于迭代器那篇博客有提到.
template <class ForwardIterator, class T>
inline void __destroy(ForwardIterator first, ForwardIterator last, T*) {
	typedef typename __type_traits<T>::has_trivial_destructor trivial_destructor;
	__destroy_aux(first, last, trivial_destructor());
}


//先来理解trivial destructor和non-trivial destructor的意义:

//如果用户不定义析构函数，而是用系统自带的，则说明，析构函数基本没有什么用？（但默认会被调用）我们称之为trivial destructor
//反之，如果特定定义了析构函数，则说明需要在释放空间之前做一些事情，则这个析构函数称为non-trivial destructor


//如果元素的数值型别(value type)是否有trivial destructor
template <class ForwardIterator>
inline void
__destroy_aux(ForwardIterator first, ForwardIterator last, __false_type) {
	for (; first < last; ++first)
		destroy(&*first);
}

//如果元素的数值型别(value type)与Non_trivial destructor.
template <class ForwardIterator>
inline void __destroy_aux(ForwardIterator, ForwardIterator, __true_type) {}

inline void destroy(char*, char*) {}
inline void destroy(wchar_t*, wchar_t*) {}

__STL_END_NAMESPACE

#endif /* __SGI_STL_INTERNAL_CONSTRUCT_H */

上面我的注释标注的还算详细吧,下面还会有一张图来分析construct()和destroy（）的函数结构,唯一有难度的就是triats类型萃取的部分，如果不明

白可以看这个博客:迭代器设计思维 

上述construct()接受一个指针p和一个初值value,该函数的用途就是将初值设定到指针所指的空间上，C++的placement new运算来完成任务.

destroy有两个版本，第一个版本接受一个指针，准备将指针所指之物析构掉. 这很简单，直接调用该对象的析构函数即可. 第二版本接受first和

last两个迭代器，准备将[first,last)范围内的所有对象析构掉，我们不知道这个范围有多大，万一很大，而每个对象的析构函数都是无关痛痒类型

也就是我们的trivial destructor，那么一次次调用这些无关痛痒的析构函数，对效率是一种伤害. 因此，这里首先利用value_type()获得迭代器

所指对象的型别，再利用类型萃取判断该型别的析构函数是否为无关痛痒类型，如果是就让他什么都不做，如果不是这才循环方式巡访整个范围，并

在循环中每经历一个对象就调用第一个版本的destroy().

uninitialized_copy()  uninitialized_fill()和uninitialized_fill_n()

->

template <class InputIterator, class ForwardIterator>
inline ForwardIterator uninitialized_copy(InputIterator first, InputIterator last,ForwardIterator result)

1.配置内存区块，足已包含范围内的所有元素.

2.使用 uninitialized_copy()，在该内存区块上构造元素.

该函数的作用就是将迭代器first和迭代器last这段区间的数据内容，拷贝到以迭代器result为起始位置的空间. 它的参数非常容易理解了吧. 

C++标准规格书上面讲该函数具有"commit or rollback"语意，意思是要么"构造出所有必要的元素",要么"不构造任何东西".

我们 直 接开始看uninitialized_copy()的源代码:

//摘自 SGI STL 3.0 <uninitialized.h>

//重载1
template <class InputIterator, class ForwardIterator, class T>
inline ForwardIterator
__uninitialized_copy(InputIterator first, InputIterator last,
ForwardIterator result, T*) {
	typedef typename __type_traits<T>::is_POD_type is_POD;
	return __uninitialized_copy_aux(first, last, result, is_POD());
}

//重载2 我们着重聊这个
template <class InputIterator, class ForwardIterator>
inline ForwardIterator
uninitialized_copy(InputIterator first, InputIterator last,
ForwardIterator result) {
	return __uninitialized_copy(first, last, result, value_type(result)); 
	//对这个函数进行类型萃取，萃取出迭代器result的value_type，然后判断该类型是否为POD型别:

	//POD意思为 Plain Old Data，也就是标量型别或传统的C struct型别. POD型别必然拥有trivial ctor/dtor/copy/assignment函数
	//因此，我们可以对POD型别的采用最优效率的填写收发就是合理的使用上面的函数，而对non-POD型别采用最保险的写法:
	//也就是如果是POD类型 就不需要我们劳神了，直接扔给STL的高阶算法，比如copy,assignment等待，如果是POD就得我们自己动手写代码了.
}

//这个函数就是当上层提取出来的value_type为POD类型，那么直接交给高阶算法处理
template <class InputIterator, class ForwardIterator>
inline ForwardIterator
__uninitialized_copy_aux(InputIterator first, InputIterator last,
ForwardIterator result,
__true_type) {
	return copy(first, last, result);
}

//这里很遗憾萃取出来的并不是POD类型，我们就得自己动手了，对他们的每一个数据元素进行construct(),然后一个一个的拷贝进result.
//construct() 调用构造函数初始化！
template <class InputIterator, class ForwardIterator>
ForwardIterator
__uninitialized_copy_aux(InputIterator first, InputIterator last,
ForwardIterator result,
__false_type) {
	ForwardIterator cur = result;
	__STL_TRY{
		for (; first != last; ++first, ++cur)
		construct(&*cur, *first);
		return cur;
	}
	__STL_UNWIND(destroy(result, cur));
}

//下面这两个是针对char* 和 wchar_t*两种型别的重载，因为它们可以使用更具效率的做法memmove(直接移动内存内容)来执行复制
//因此SGI对这两个型别进行了特化
inline char* uninitialized_copy(const char* first, const char* last,
	char* result) {
	memmove(result, first, last - first);
	return result + (last - first);
}


inline wchar_t* uninitialized_copy(const wchar_t* first, const wchar_t* last,
	wchar_t* result) {
	memmove(result, first, sizeof(wchar_t)* (last - first));
	return result + (last - first);
}

下面这张图可以更好地理解uninitialized_copy函数

->

template <class ForwardIterator, class T>
inline void uninitialized_fill(ForwardIterator first, ForwardIterator last,const T& x)

template <class ForwardIterator, class T>
inline void uninitialized_fill(ForwardIterator first, ForwardIterator last,
const T& x) {
__uninitialized_fill(first, last, x, value_type(first));
//对这个函数进行类型萃取，萃取出迭代器first的value_type.
}

template <class ForwardIterator, class T, class T1>
inline void __uninitialized_fill(ForwardIterator first, ForwardIterator last,
	const T& x, T1*) {
	typedef typename __type_traits<T1>::is_POD_type is_POD;
	//利用traits萃取编程思想，判断该T类型是否为POD型别:
	__uninitialized_fill_aux(first, last, x, is_POD());

	//POD意思为 Plain Old Data，也就是标量型别或传统的C struct型别.POD型别必然拥有trivial ctor / dtor / copy / assignment函数
	//因此，我们可以对POD型别的采用最优效率的填写收发就是合理的使用上面的函数，而对non-POD型别采用最保险的写法:
	//也就是如果是POD类型 就不需要我们劳神了，直接扔给STL的高阶算法，比如copy,assignment等待，如果是POD就得我们自己动手写代码了.
}


//如果为POD型别，直接交给高阶函数处理
template <class ForwardIterator, class T>
inline void
__uninitialized_fill_aux(ForwardIterator first, ForwardIterator last,
const T& x, __true_type)
{
	fill(first, last, x);
}

//这里很遗憾萃取出来的并不是POD类型，我们就得自己动手了，对他们的每一个数据元素进行construct(),然后一个一个的拷贝进result.
//construct() 调用构造函数初始化！
template <class ForwardIterator, class T>
void
__uninitialized_fill_aux(ForwardIterator first, ForwardIterator last,
const T& x, __false_type)
{
	ForwardIterator cur = first;
	__STL_TRY{
		for (; cur != last; ++cur)
		construct(&*cur, x);
	}
	__STL_UNWIND(destroy(first, cur));
}

template <class ForwardIterator, class Size, class T>
inline ForwardIterator uninitialized_fill_n(ForwardIterator first, Size n ,const T& x)

template <class ForwardIterator, class Size, class T>
inline ForwardIterator uninitialized_fill_n(ForwardIterator first, Size n,
	const T& x) {
	return __uninitialized_fill_n(first, n, x, value_type(first));
	//对这个函数进行类型萃取，萃取出迭代器first的value_type，然后判断该类型是否为POD型别:
}

template <class ForwardIterator, class Size, class T, class T1>
inline ForwardIterator __uninitialized_fill_n(ForwardIterator first, Size n,
	const T& x, T1*) {
	typedef typename __type_traits<T1>::is_POD_type is_POD;
	//利用traits编程思想，萃取出T1的is_POD_type类型.
	return __uninitialized_fill_n_aux(first, n, x, is_POD());

	//POD意思为 Plain Old Data，也就是标量型别或传统的C struct型别. POD型别必然拥有trivial ctor/dtor/copy/assignment函数
	//因此，我们可以对POD型别的采用最优效率的填写收发就是合理的使用上面的函数，而对non-POD型别采用最保险的写法:
	//也就是如果是POD类型 就不需要我们劳神了，直接扔给STL的高阶算法，比如copy,assignment等待，如果是POD就得我们自己动手写代码了.
}

//这个函数就是当上层提取出来的value_type为POD类型，那么直接交给高阶算法处理
template <class ForwardIterator, class Size, class T>
inline ForwardIterator
__uninitialized_fill_n_aux(ForwardIterator first, Size n,
const T& x, __true_type) {
	return fill_n(first, n, x);
}

//这里很遗憾萃取出来的并不是POD类型，我们就得自己动手了，对他们的每一个数据元素进行construct(),然后一个一个的拷贝进result.
//construct() 调用构造函数初始化！
template <class ForwardIterator, class Size, class T>
ForwardIterator
__uninitialized_fill_n_aux(ForwardIterator first, Size n,
const T& x, __false_type) {
	ForwardIterator cur = first;
	__STL_TRY{
		for (; n > 0; --n, ++cur)
		construct(&*cur, x);
		return cur;
	}
	__STL_UNWIND(destroy(first, cur));
}