Extra Cookie

Yet Another Programmer's Blog

STL 源码分析-A.万物起源-1

C++中,我们熟悉的对象的创建和释放过程如下:

1
2
3
4
5
6
7
8
9
class Thing
{
   ...
};

...

Thing *pt = new Thing;
delete pt;

代码中 new 完成两部分动作,1. 调用 ::operator new 分配对象所占内存空间,2. 调用 Thing 构造函数初始化对象内容。delete 也完成两部分动作,1. 调用析构函数清除对象内容,2. 调用 ::operator delete 释放内存空间。

STL 将这两部分动作分离了开来,内存分配由 alloc:allocate() 负责,释放由 alloc:deallocate() 负责,对象构造和析构依次由 ::contruct()::destroy() 负责。

具体实现位于 stl_alloc.h, stl_contruct.h, stl_uninitialized.h 中,stl_alloc.h 负责内存分配,stl_contruct.h 负责对象构建和析构,stl_uninitialized.h 提供一系列全局函数来进行内存填充 (fill) 和拷贝 (copy)。其实 alloc 并不符合标准规范,而应该是 allocator,位于 stl_defalloc.h 中。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
template <class T>
inline T* allocate(ptrdiff_t size, T*) {
    set_new_handler(0);
    T* tmp = (T*)(::operator new((size_t)(size * sizeof(T))));
    if (tmp == 0) {
        cerr << "out of memory" << endl;
        exit(1);
    }
    return tmp;
}

template <class T>
inline void deallocate(T* buffer) {
    ::operator delete(buffer);
}

首先定义两个全局函数,用来进行内存分配的操作,可以看出其只是对 ::operator new::operator delete 做了一层简单的封装。

1
2
3
4
5
6
7
8
9
10
template <class T>
class allocator {
public:
    ...
    pointer allocate(size_type n) {
        return ::allocate((difference_type)n, (pointer)0);
    }
    void deallocate(pointer p) { ::deallocate(p); }
    ...
};

这便是 allocator 的实现,因为效率不好,所以 SGI STL 从来没有使用过它,也并不建议我们使用。SGI STL 实现的 alloc 除了 allocator 的功能外,还考虑内存不足时的处理,分配过多小区域导致内存碎片的问题等。关于 alloc 后面再谈,先从对象构建和析构着手 (stl_contruct.h) 入手。

1
2
3
4
5
6
7
8
9
template <class _T1, class _T2>
inline void construct(_T1* __p, const _T2& __value) {
  new (__p) _T1(__value);
}

template <class _T1>
inline void construct(_T1* __p) {
  new (__p) _T1();
}

new (__p) _T1( … ) 采用的是 placement new 操作,不同于 ::operator new 从堆中直接分配内存用以对象构建,它是在一个已经分配好的内存区域中构建对象,正因为这样,我们才能分离对象构建析构和内存分配释放。

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
template <class _Tp>
inline void destroy(_Tp* __pointer) {
  __pointer->~_Tp();
}

template <class _ForwardIterator>
void
__destroy_aux(_ForwardIterator __first, _ForwardIterator __last, __false_type)
{
  for ( ; __first != __last; ++__first)
    destroy(&*__first);
}

template <class _ForwardIterator>
inline void __destroy_aux(_ForwardIterator, _ForwardIterator, __true_type) {}

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());
}

template <class _ForwardIterator>
inline void destroy(_ForwardIterator __first, _ForwardIterator __last) {
  __destroy(__first, __last, __VALUE_TYPE(__first));
}

对象的析构从 destroy(_ForwardIterator __first, _ForwardIterator __last) (L27) 开始,依次对 foward iterator 所指向的所有对象进行析构。首先将迭代器 (指向对象) 类型传入 __destroy (L28) 函数,该函数对传入类型进行 type_traits (L21) (迭代器和 traits 相关内容请阅读),然后跟据该对象有无 trivial destructor,分别由重载函数 (L15) (L8) 进行处理,为什么这样做呢?

因为我们不知道 L27 中迭代器的区间范围有多大,如果数量很多,调用那些 trivial destructor 在效率方面是一种浪费。如果是 trivial destructor (L15),则什么都不做,如果不是 (L8),便依次调用 destroy(_Tp* __pointer) (L2),而该函数则直接调用对象的析构函数,整个析构过程结束。

本文代码示例基于 SGI STL 3.2.

下一篇将分析 alloc 的实现。

Comments