KJHの博客

记录&回忆

0%

STL内存基本处理

发表于 更新于 分类于
本文字数： 7k 阅读时长 ≈ 6 分钟

这里继续学习基于配置器之上的一些内存基本处理工具。主要剖析 SGI STL 源码（http ://www.sgi.com/tech/stl/download.html v3.3）中的几个内存处理函数(由函数名可知，是对未初始化空间的初始化操作，即通过复制或赋值的方式初始化未初始化的空间)：
uninitialized_copy()，uninitialized_copy_n()，uninitialized_fill()，uninitialized_fill_n()。

先学习 uninitiated_copy()

1
2
3
4
5
6
7
8
9
10
11
12
//stl source code（v3.3）
//defined in <stl_uninitialized.h>
inline char* uninitialized_copy(const char* __first, const char* __last, char* __result) 
{
	memmove(__result, __first, __last - __first);
	return __result + (__last - __first);  //返回该连续区域的末尾
}
inline wchar_t*   // typedef unsigned short 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);

上面两个是对两种特化类型的处理，下面为泛化版本 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
template <class _InputIter, class _ForwardIter>
inline _ForwardIter
uninitialized_copy(_InputIter __first, _InputIter __last, _ForwardIter __result)
{  
	//根据数值型别决议出最佳效率的函数
	return __uninitialized_copy(__first, __last, __result, __VALUE_TYPE(__result));
}
template <class _InputIter, class _ForwardIter, class _Tp>
inline _ForwardIter
__uninitialized_copy(_InputIter __first, _InputIter __last, _ForwardIter __result, _Tp*)
{
	typedef typename __type_traits<_Tp>::is_POD_type _Is_POD;   //判断数值型别
	//在C++中，我们把传统的C风格的struct叫做POD（Plain Old Data）对象
	return __uninitialized_copy_aux(__first, __last, __result, _Is_POD());
}
//如果copy construction 和 operator = 等效(POD type)，并且 destructor is trivial 的情况 
template <class _InputIter, class _ForwardIter>
inline _ForwardIter
__uninitialized_copy_aux(_InputIter __first, _InputIter __last, _ForwardIter __result, __true_type)
{
	/*针对POD对象，其二进制内容是可以随便复制的*/
	return copy(__first, __last, __result);
	/*简化处理，详见<stl_algobase.h>
	inline _Tp* copy(const _Tp* __first, const _Tp* __last, _Tp* __result)
	{
	    memmove(__result, __first, sizeof(_Tp) * (__last - __first));
	    return __result + (__last - __first);
	}
	*/
}
/*如果copy construction 和 operator = 不等效，就需要调用 construct() 构造 */
template <class _InputIter, class _ForwardIter>
_ForwardIter
__uninitialized_copy_aux(_InputIter __first, _InputIter __last, _ForwardIter __result, __false_type)
{
	_ForwardIter __cur = __result;
	/*下面就是捕捉异常处理*/
	__STL_TRY{    //#define __STL_TRY  try
		for (; __first != __last; ++__first, ++__cur) //一个一个元素的构造，无法批量进行
		_Construct(&*__cur, *__first);   //每个对象都以其它对象为蓝本进行构造，使用的是 placement new
		return __cur;
	}
	/*commit or rollback：要么构造出所有必要元素，
	要么（当有任何一个 copy construct 失败时）不构造任何东西，保证所有对象都被析构*/
	__STL_UNWIND(_Destroy(__result, __cur));
	//#define __STL_UNMIND(action)  catch(...) { action; throw;}
}

POD就是标量型别或传统的C struct 型别，POD 型别必然拥有 trivial ctor / dtor / copy / assignment 函数，因此我们可以对POD型别进行判断，从而决议出最有效率的初值填写手法

不难发现上面 uninitiated_copy() 后，返回的是指向 copy 后的区块末端。

uninitiated_copy_n() 则是向指定欲初始化空间初始化(复制)指定大小已初始化空间的指定值(有点拗口)。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
template <class _InputIter, class _Size, class _ForwardIter>
inline pair<_InputIter, _ForwardIter>
uninitialized_copy_n(_InputIter __first, _Size __count, _ForwardIter __result)
{
	//最后一个形参判断迭代器 first 的类别
	return __uninitialized_copy_n(__first, __count, __result, __ITERATOR_CATEGORY(__first));
}
//函数返回两个值，采用 pair 对组
//迭代器型别为支持随机存取的迭代器，涵盖所有指针运算能力，可以直接使用uninitialized_copy()进行复制
template <class _RandomAccessIter, class _Size, class _ForwardIter>
inline pair<_RandomAccessIter, _ForwardIter>
__uninitialized_copy_n(_RandomAccessIter __first, _Size __count, _ForwardIter __result, random_access_iterator_tag)
{
	_RandomAccessIter __last = __first + __count;
	return pair<_RandomAccessIter, _ForwardIter>(__last, uninitialized_copy(__first, __last, __result));
}
//迭代器为只读型别，所指的对象不允许外界改变
template <class _InputIter, class _Size, class _ForwardIter>
pair<_InputIter, _ForwardIter>
__uninitialized_copy_n(_InputIter __first, _Size __count, _ForwardIter __result, input_iterator_tag)
{
	/*针对输入范围内的每一个迭代器，函数会调用construct()函数产生迭代器所指对象的复制品，
	放置于输出范围的相应位置上*/
	_ForwardIter __cur = __result;
	__STL_TRY{        
		for (; __count > 0; --__count, ++__first, ++__cur)
		_Construct(&*__cur, *__first);
		return pair<_InputIter, _ForwardIter>(__first, __cur);
	}
	__STL_UNWIND(_Destroy(__result, __cur));
}

上面函数都是返回 pair 对组类型。其实就是返回两个值，一个是 “只读” 型别的迭代器（_InputIter），一个是允许 “写入型” 的迭代器（_ForwardIter）。
下面这个函数 uninitiated_fill() 和 uninitiated_copy() 操作很像，只不过前者是赋值，后者是复制。 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
//迭代器类型为“写入型”。该函数的功能就是给迭代器指定范围内赋值
//具体实现过程参考函数 uninitialized_copy()
template <class _ForwardIter, class _Tp>
inline void uninitialized_fill(_ForwardIter __first, _ForwardIter __last, const _Tp& __x)
{
	__uninitialized_fill(__first, __last, __x, __VALUE_TYPE(__first));
}

//判断数值型别，同 uninitialized_copy()
template <class _ForwardIter, class _Tp, class _Tp1>
inline void __uninitialized_fill(_ForwardIter __first, _ForwardIter __last, const _Tp& __x, _Tp1*)
{
	typedef typename __type_traits<_Tp1>::is_POD_type _Is_POD;
	__uninitialized_fill_aux(__first, __last, __x, _Is_POD());
}

template <class _ForwardIter, class _Tp>
inline void
__uninitialized_fill_aux(_ForwardIter __first, _ForwardIter __last, const _Tp& __x, __true_type)
{
	fill(__first, __last, __x);
	/*简化处理，参见<stl_algobase.h>
	template <class _ForwardIter, class _Tp>
	void fill(_ForwardIter __first, _ForwardIter __last, const _Tp& __value) 
	{
		for ( ; __first != __last; ++__first)
			*__first = __value;
	}
	*/
}
template <class _ForwardIter, class _Tp>
void
__uninitialized_fill_aux(_ForwardIter __first, _ForwardIter __last, const _Tp& __x, __false_type)
{
	_ForwardIter __cur = __first;
	__STL_TRY{
		for (; __cur != __last; ++__cur)
		_Construct(&*__cur, __x);
	}	
    __STL_UNWIND(_Destroy(__first, __cur));
}

下面的函数 uninitiated_fill_n() 则是向指定欲初始化空间初始化(赋值)指定大小空间的指定值。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
template <class _ForwardIter, class _Size, class _Tp>
inline _ForwardIter
uninitialized_fill_n(_ForwardIter __first, _Size __n, const _Tp& __x)
{
	return __uninitialized_fill_n(__first, __n, __x, __VALUE_TYPE(__first));
}
template <class _ForwardIter, class _Size, class _Tp, class _Tp1>
inline _ForwardIter
__uninitialized_fill_n(_ForwardIter __first, _Size __n, const _Tp& __x, _Tp1*)
{
	typedef typename __type_traits<_Tp1>::is_POD_type _Is_POD;
	return __uninitialized_fill_n_aux(__first, __n, __x, _Is_POD());
}

template <class _ForwardIter, class _Size, class _Tp>
_ForwardIter
__uninitialized_fill_n_aux(_ForwardIter __first, _Size __n, const _Tp& __x, __false_type)
{
	_ForwardIter __cur = __first;
	__STL_TRY{
		for (; __n > 0; --__n, ++__cur)
		_Construct(&*__cur, __x);
		return __cur;
	}
	__STL_UNWIND(_Destroy(__first, __cur));
}
template <class _ForwardIter, class _Size, class _Tp>
inline _ForwardIter
__uninitialized_fill_n_aux(_ForwardIter __first, _Size __n, const _Tp& __x, __true_type)
{
	return fill_n(__first, __n, __x);
	/*简化处理，参见<stl_algobase.h>
	template <class _OutputIter, class _Size, class _Tp>
    _OutputIter fill_n(_OutputIter __first, _Size __n, const _Tp& __value)
	{
		for ( ; __n > 0; --__n, ++__first)
			*__first = __value;
		return __first;
	}
	*/
}

STL 定义的这几个全局函数（包括前面介绍的用于构造的 construct() 和 用于析构的 destroy()），作用于未初始化空间上，这样的功能对于容器的实现很有帮助。