STL源码剖析<四> 回到空间配置器及traits技术的应用

之前我们研究了STL中的空间配置器,提到STL将内存分配和对象构造分开来,当时只讲了空间分配,现在来分析STL空间配置器的对象构造

在SGISTL的 <stl_construct.h> 文件便是用来构造和析构对象

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
#include <new.h> //欲使用 placement new,需先包含此文件
//construct()
template <class _T1, class _T2>
inline void construct(_T1* __p, const _T2& __value)
{
new ((void*)__p) _T1(__value); //placementnew;调用_T1::_T1(__value),构造新对象到预分配的内存上
}
template <class _T1>
inline void construct(_T1* __p) {
new ((void*)__p) _T1();
}
//destroy()
template <class _Tp>
inline void destroy(_Tp* __pointer) {
__pointer->~_Tp(); //调用~_Tp()
}

placement new 允许你在一个已经分配好的内存中(栈或堆)构造一个新的对象。

原型中(void*)__p实际上就是指向一个已经分配好的内存缓冲区的首地址。STL借助C++中的placement new来提高效率,因为使用new操作符分配内存需要在堆中查找足够大的剩余空间,这个操作速度是很慢的,而且有可能出现无法分配内存的异常。借助 placement new就可以解决这个问题,我们构造对象都是在一个预先准备好了的内存缓冲区中进行,不需要查找内存,内存分配的时间是常数,而且不会出现在程序运行中途出现内存不足的异常。

上面的析构函数是接受一个指针,STL 另外提供一个版本用来析构两个迭代器所指范围内的所有对象。
此函数设法萃取(traits)出元素的数值型别,利用__type_traits<>求最适当的措施

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
/*这里对比源码调整了顺序*/
template <class _ForwardIterator>
inline void destroy(_ForwardIterator __first, _ForwardIterator __last) {
_Destroy(__first, __last); //调用_Destroy()
}
//函数内部调用的函数__destroy()多了个参数,__VALUE_TYPE(__first),用于找出元素的数值型别
template <class _ForwardIterator>
inline void _Destroy(_ForwardIterator __first, _ForwardIterator __last) {
__destroy(__first, __last, __VALUE_TYPE(__first)); //调用__destroy()
}
//判断元素的数值型别是否有无用的析构函数(trivial_destructor)
template <class _ForwardIterator, class _Tp>
inline void
__destroy(_ForwardIterator __first, _ForwardIterator __last, _Tp*)
{
typedef typename __type_traits<_Tp>::has_trivial_destructor
_Trivial_destructor;
__destroy_aux(__first, __last, _Trivial_destructor()); //调用__destroy_aux()
}
//如果元素的数值型别具备的是有用的析构函数,那么函数内部调用destroy()
template <class _ForwardIterator>
void
__destroy_aux(_ForwardIterator __first, _ForwardIterator __last, __false_type)
{
for (; __first != __last; ++__first)
destroy(&*__first); //调用destroy()
}
//如果元素的数值型别有无用的析构函数,函数体无操作
template <class _ForwardIterator>
inline void __destroy_aux(_ForwardIterator, _ForwardIterator, __true_type) {}
//迭代器版本destroy() -> _Destroy() -> __destroy() -> __destroy_aux() -> destroy() 指针版本
//所以实际上是逐个析构,只是中间为了效率,引入了判断元素的数值型别,来确定对象是否具备有用的析构函数

对于迭代器版本的destroy() 实际最后都落脚到了单一对象指针版本的 destroy()。那么为什么要绕一大圈呢?因为这里接受的参数是两个迭代器,目的就是将这两个迭代器范围内的所有对象都析构掉,如果范围很大,并且对象的析构函数都是无关紧要的,那么一次次的调用这些个无用的析构函数,势必会对效率产生大的影响,所以先利用VALUE(first) 获得迭代器所指对象的型别,再利用 __type_traits<_Tp> 判断该型别的析构函数是否无关痛痒,如果是则什么也不做,如果不是则循环逐个析构范围内的对象。

所以对象的构造实际是通过 placement new 完成的(缓存提前分配然后进行对象的分配);对象的析构则通过调用外在的析构函数(~_Tp())。注意的是,这里的析构只是析构对象,分配好的缓存并没有释放,所以可以反复利用缓存并给它分配对象。不打算再次使用这个缓存时,你可以delete 将其释放掉。

另外destroy() 第二版本还针对迭代器类型为 char 和 wchar_t 定义了特化版本

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

大致流程可以见下图
构造

tarits技法在空间配置器中的uninitialized_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
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
G++ 2.91.57,cygnus\cygwin-b20\include\g++\stl_uninitialized.h 完整列表
/*
*
* Copyright (c) 1994
* Hewlett-Packard Company
*
* Permission to use, copy, modify, distribute and sell this software
* and its documentation for any purpose is hereby granted without fee,
* provided that the above copyright notice appear in all copies and
* that both that copyright notice and this permission notice appear
* in supporting documentation. Hewlett-Packard Company makes no
* representations about the suitability of this software for any
* purpose. It is provided "as is" without express or implied warranty.
*
*
* Copyright (c) 1996,1997
* Silicon Graphics Computer Systems, Inc.
*
* Permission to use, copy, modify, distribute and sell this software
* and its documentation for any purpose is hereby granted without fee,
* provided that the above copyright notice appear in all copies and
* that both that copyright notice and this permission notice appear
* in supporting documentation. Silicon Graphics makes no
* representations about the suitability of this software for any
* purpose. It is provided "as is" without express or implied warranty.
*/
/* NOTE: This is an internal header file, included by other STL headers.
* You should not attempt to use it directly.
*/
#ifndef __SGI_STL_INTERNAL_UNINITIALIZED_H
#define __SGI_STL_INTERNAL_UNINITIALIZED_H
__STL_BEGIN_NAMESPACE
// Valid if copy construction is equivalent to assignment, and if the
// destructor is trivial.
template <class InputIterator, class ForwardIterator>
inline ForwardIterator
__uninitialized_copy_aux(InputIterator first, InputIterator last,
ForwardIterator result,
__true_type) {//_true_type说明是POD类型
return copy(first, last, result);//调用STL算法copy()
}
template <class InputIterator, class ForwardIterator>
ForwardIterator
__uninitialized_copy_aux(InputIterator first, InputIterator last,
ForwardIterator result,
__false_type) {//_false_type说明是non-POD类型,要一个一个的构建,无法批量进行
ForwardIterator cur = result;
__STL_TRY {
for ( ; first != last; ++first, ++cur)//一个一个的构建
construct(&*cur, *first);
return cur;
}
__STL_UNWIND(destroy(result, cur));
}
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;//用来判断是不是POD类型
return __uninitialized_copy_aux(first, last, result, is_POD());
}
/*
调用copy constructor,复制[first, last)范围内每一个对象,放到目的地[result, result+(last-first) )。
对于char*和wchar_t*提供特殊版本,获得更好效率
具有像数据库事物特性的commit和rollback特性,要么构造出所有必要元素,要么不够造任何东西。
copy() for(; first!=last) construct()
| |
| _true_type | _false_type
<__特化____________特化__>
|
_uninitialized_copy()
<InputIterator, Inputterator, ForwardIterator>
|
|泛化
|
uninitialized _____|_____特化___>(const char*, const char*,char*) memmove()
_copy() |
|
|____特化___>(const wchar_t*, const wchar_t*, wchar_t*) memmove()
*/
template <class InputIterator, class ForwardIterator>
inline ForwardIterator
uninitialized_copy(InputIterator first, InputIterator last,
ForwardIterator result) {
return __uninitialized_copy(first, last, result, value_type(result));
}
//char*版本
inline char* uninitialized_copy(const char* first, const char* last,
char* result) {
memmove(result, first, last - first);
return result + (last - first);
}
//wchar_t*版本
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);
}
//input_iterator_tag只读迭代器类型
template <class InputIterator, class Size, class ForwardIterator>
pair<InputIterator, ForwardIterator>
__uninitialized_copy_n(InputIterator first, Size count,
ForwardIterator result,
input_iterator_tag) {
ForwardIterator cur = result;
__STL_TRY {
for ( ; count > 0 ; --count, ++first, ++cur)
construct(&*cur, *first);
return pair<InputIterator, ForwardIterator>(first, cur);
}
__STL_UNWIND(destroy(result, cur));
}
//RandomAccessIterator迭代器类型
template <class RandomAccessIterator, class Size, class ForwardIterator>
inline pair<RandomAccessIterator, ForwardIterator>
__uninitialized_copy_n(RandomAccessIterator first, Size count,
ForwardIterator result,
random_access_iterator_tag) {
RandomAccessIterator last = first + count;
return make_pair(last, uninitialized_copy(first, last, result));
}
//用[result, result+count)初始化[first, first+cout)
/*
这个根据迭代器类型跳转
_____input_iterator_tag,调用construct(……)
|
|
uninitialized_copy_n----> iterator_category(first)?判断迭代器类型
|
|_____random_access_iterator_tag,调用uninitialized_copy(……)
*/
template <class InputIterator, class Size, class ForwardIterator>
inline pair<InputIterator, ForwardIterator>
uninitialized_copy_n(InputIterator first, Size count,
ForwardIterator result) {
return __uninitialized_copy_n(first, count, result,
iterator_category(first));//判断迭代器类型
}
// Valid if copy construction is equivalent to assignment, and if the
// destructor is trivial.
//如果复制构造函数和赋值操作符效果相同,且析构函数时trivial的
template <class ForwardIterator, class T>
inline void
__uninitialized_fill_aux(ForwardIterator first, ForwardIterator last,
const T& x, __true_type)//POD类型
{
fill(first, last, x);
}
template <class ForwardIterator, class T>
void
__uninitialized_fill_aux(ForwardIterator first, ForwardIterator last,
const T& x, __false_type)//non-POD类型
{
ForwardIterator cur = first;
__STL_TRY {
for ( ; cur != last; ++cur)//一个一个构建
construct(&*cur, x);
}
__STL_UNWIND(destroy(first, cur));
}
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;
__uninitialized_fill_aux(first, last, x, is_POD());
}
/*
用x初始化空间[first, last)
___> construct(……)
| __false_type
|
uninitialized_fill------> is POD?
| __true_type
|___> fill(……)
*/
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是不是POD类型
}
// Valid if copy construction is equivalent to assignment, and if the
// destructor is trivial.
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);
}
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));
}
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;
return __uninitialized_fill_n_aux(first, n, x, is_POD());
}
/*
用x初始化[first, first+n)。也要判断是不是POD类型,看懂前面两个的话,这个自然就懂了,不再赘述。
*/
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));
}
// Copies [first1, last1) into [result, result + (last1 - first1)), and
// copies [first2, last2) into
// [result, result + (last1 - first1) + (last2 - first2)).
template <class InputIterator1, class InputIterator2, class ForwardIterator>
inline ForwardIterator
__uninitialized_copy_copy(InputIterator1 first1, InputIterator1 last1,
InputIterator2 first2, InputIterator2 last2,
ForwardIterator result) {
ForwardIterator mid = uninitialized_copy(first1, last1, result);
__STL_TRY {
return uninitialized_copy(first2, last2, mid);
}
__STL_UNWIND(destroy(result, mid));
}
// Fills [result, mid) with x, and copies [first, last) into
// [mid, mid + (last - first)).
template <class ForwardIterator, class T, class InputIterator>
inline ForwardIterator
__uninitialized_fill_copy(ForwardIterator result, ForwardIterator mid,
const T& x,
InputIterator first, InputIterator last) {
uninitialized_fill(result, mid, x);
__STL_TRY {
return uninitialized_copy(first, last, mid);
}
__STL_UNWIND(destroy(result, mid));
}
// Copies [first1, last1) into [first2, first2 + (last1 - first1)), and
// fills [first2 + (last1 - first1), last2) with x.
template <class InputIterator, class ForwardIterator, class T>
inline void
__uninitialized_copy_fill(InputIterator first1, InputIterator last1,
ForwardIterator first2, ForwardIterator last2,
const T& x) {
ForwardIterator mid2 = uninitialized_copy(first1, last1, first2);
__STL_TRY {
uninitialized_fill(mid2, last2, x);
}
__STL_UNWIND(destroy(first2, mid2));
}
__STL_END_NAMESPACE
#endif /* __SGI_STL_INTERNAL_UNINITIALIZED_H */
// Local Variables:
// mode:C++
// End: