一步步看懂STL源码（1）
-
大纲
一直以来就想好好把STL源码通读一遍，限于水平，每每想扎进去，又被高深的模板，前后复杂的调用给震飞，不得窥其全貌，最近鼓起勇气，用超慢速度，边看边写，冒死整理出一个比较easy的进军路线，供大家参考。本篇内容如下：
对象的构造与析构
对象的拷贝和移动
一些辅助的栗子
第一部分介绍编译器如何给你找对象的（构造），又是如何劝你们分手的（析构），需要理解构造和析构的两个步骤和四个关键函数。第二部分需要精读，细致讲述了如何将对象拷贝和腾挪，STL为了提高效率，极尽其能，手段横飞，是STL中十分精彩的一部分，需细品。第一篇比较简单，但是也很关键，是后续篇章的基础，开始来吧！
对象的构造与析构
class Foo {...}
Foo *pf = new Foo;
delete pf;
上述代码究竟帮你做了什么，在内存中发生了什么变化？
new是C++的一个操作符，分为了两个阶段：(1)调用::operator new配置内存，让对象有安身之所。(2)在安身之所的起始地址调用Foo::Foo()进行基建工作，形成Foo对象的结构。更为通俗说法是：先买一块地皮，然后开始盖房子。
delete自然也需要分为两个阶段，不过是反着来的：(1)调用Foo::~Foo()将对象析构。(2)调用::operator delete归还内存。也用一句通俗的话来讲：先将用不上的房子拆除，再把地皮交还给国家。
上面这四个阶段引出了下面这四个函数
alloc::allocate()
alloc::deallocate()
::construct()
::destroy()
其中分配空间(allocate)和回收空间(deallocate)是由编译器做的，我们不要去深究，先把精力放在construct和destroy上，集中精神，下面是一剂猛药。
template
inline void construct(T1 *p, const T2& value)
{
// 这句语法可能从没见过，无所谓
// 意思就是在p所指地址的后续空间，构造出一个T2类型的对象，其值value
new (p) T(value);
}
template
inline void destroy(T *pointer)
{
pointer->~T();
}
// 下面要开始脑壳痛了，坚持一下，参照我指定的路标123走
template
inline void destroy(ForwardIterator first, ForwardIterator last)
{
// step 2
// 这一步主要的困惑在于value_type(first)
// 这个使用的是STL中的萃取机(文末链接[STL萃取机])，后面会讲述
// value_type(first)是first所指对象的类型的指针，这么做仅为了把这个类型保留下去
__destroy(first, last, value_type(first));
}
template
inline void __destroy(ForwardIterator first, ForwardIterator last, T*)
{
// step 1
// td这个对象有且仅有两个选项：__false_type __true_type
// 这个参数用来在编译期进行分支判断，在编译期决定调用哪个函数
// 所以这个td是什么意思呢，它是用来在编译期告诉编译期类型T里面的has_trivial_destructor是__false_type还是__true_type
// 用来决定如何析构，例子：如果一个类的has_trivial_destructor是__true_type
// 那么在析构的时候可以完全不做任何事情，见步骤3 4
typedef typename __type_traits
::has_trivial_destructor td; __destroy_aux(first, last, td());
}
// STL中后缀是_aux的函数才是真正干事的函数，其余的都是转发
template
inline void __destroy_aux(ForwardIterator first, ForwardIterator last, __false_type)
{
// step 3
// 如果该对象的析构函数很特别(比如包含指针)，那么需要自己做析构
// 因为他析构对象本身内存的同时，还需要析构对象中的指针指向的内容
for (; first < last; ++first)
destroy(&*first);
}
// step 4
// 如果该对象的析构函数没什么特别(比如成员都是普通的内置类型，那么只需要归还内存就可以了嘛，至于留下点痕迹在内存上，等下个来用这块内存的人来收拾吧)
template
inline void __destroy_aux(ForwardIterator first, ForwardIterator last, __true_type)
{
// 啥也不用干，等着调用alloc::deallocate()归还空间就好了
}
inline void destroy(char*, char*){}
inline void destroy(wchar_t*, wchar_t*){}
通俗易懂时刻：好比你租了一间房子，房子到期的时候，该交房了，如果你还有水电没交(内部指针指向的空间没有归还)，那自然要你来做扫尾工作，否则你就可以不用管了，留下你的家具啥的，等下个租房的人来收拾吧。
对象的拷贝和移动
这部分由三个函数带头搞事，引发效率优化后，带来的复杂局面，这三个函数分别是uninitialized_copy()，uninitialized_fill，uninitialized_fill_n。下面分别介绍
函数uninitialized_copy系列
// uninitialized_copy(first, last, result),后面的函数省略模板头声明
template
ForwardIterator
uninitialized_copy(InputIterator first,InputIterator last,ForwardIterator result)
{
// step 1
return __uninitialized_copy(first, last, result, value_type(first));
}
// step 2
ForwardIterator
__uninitialized_copy(InputIterator first, InputIterator last, ForwardIterator result, T*)
{
// 关于什么是POD类型见文末链接[通俗易懂POD]
typedef typename __type_traits
::is_POD_type is_POD; return __uninitialized_copy_aux(first, last, result, is_POD());
}
// step 3.1
ForwardIterator
__uninitialized_copy_aux(InputIterator first, InputIterator last, ForwardIterator result, __true_type)
{
// 现在还不敢用memmove，因为可能不是连续的空间
// 还要交付一层进行分发
return copy(first, last, result);
}
// step 3.2
ForwardIterator
__uninitialized_copy_aux(InputIterator first, InputIterator last, ForwardIterator result, __false_type)
{
// 必须一个个亲自构造
ForwardIterator cur = result;
for (; first != last; ++first, ++cur)
construct(&*cur, *first);
return cur;
}
// step 1.1
// 如果是char*版本那么直接无需多废话，直接上最快的memmove
// wchar_t*版本也一样，代码省略
char* uninitialized_copy(const char* first, const char* last, char* result)
{
memmove(result, first, last - first);
return result + (last - first);
}
函数uninitialized_fill_n系列
template
ForwardIterator
uninitialized_fill_n(ForwardIterator first, Size n, const T& x)
{
// step 1
return __uninitialized_fill_n(first, n, x, value_type(first));
}
ForwardIterator
__uninitialized_fill_n(ForwardIterator first, Size n, const T&x, T1*)
{
// step 2
typedef typename __type_traits
::is_POD_type is_POD; return __uninitialized_fill_n_aux(first, n, x, is_POD());
}
// step 2.1
ForwardIterator
__uninitialized_fill_n_aux(ForwardIterator first, Size n, const T& x, __true_type)
{
/*
template
OutputIterator fill_n(OutputIterator first, Size n, const T& x)
{
for (; n > 0; --n, ++first)
*first = value;
return first;
}
*/
return fill_n(first, n, x);
}
// step 2.2
ForwardIterator
__uninitialized_fill_n_aux(ForwardIterator first, Size n, const T& x, __false_type)
{
ForwardIterator cur = first;
for (; n > 0; --n, ++cur)
construct(&*cur, x);
return cur;
}
函数uninitialized_fill系列
template
inline void
uninitialized_fill(ForwardIterator first, ForwardIterator last, const T& x)
{
// step 1
// __uninitialized_fill(first, last, x, value_type(first));
}
// step 2
inline void
__uninitialized_fill(ForwardIterator first, ForwardIterator last, const T&x, T1*)
{
typedef typename __type_traits
::is_POD_type is_POD; __uninitialized_fill_aux(first, last, x, is_POD());
}
// step 2.1
inline void
__uninitialized_fill_aux(ForwardIterator first,ForwardIterator last,const T& x, __true_type)
{
fill(first, last, x);
}
// step 2.2
inline void
__uninitialized_fill_aux(ForwardIterator first,ForwardIterator last,const T& x, __false_type)
{
ForwardIterator cur = first;
for (; cur != last; ++cur)
construct(&*cur, x);
}
最终调用的copy()
// 唯一入口函数copy()
// 如果只原生指针类型的copy，wchar_t*版本代码一致
inline char*
copy(const char* first, const char* last, char* result)
{
// 直接内存拷贝，速度超快
memmove(result, first, last - first);
return result + (last - first);
}
template
inline OutputIterator
copy(InputIterator first, InputIterator last, OutputIterator result)
{
// step 1
// [first, last)迭代器区间，需要进一步考察
// 这里是个对象，会调用__copy_dispatch的operator()
return __copy_dispatch(InputIterator,OutIterator>()(first,last,result);
}
template
struct __copy_dispatch
{
OutputIterator operator()(InputIterator first, InputIterator last, OutputIterator result)
{
// step 2.1
// 转发到哪，视迭代器类型(文末链接[迭代器类型])而定
return __copy(first,last,result,iterator_category(first));
}
};
// 如果从step 1调用时，发现迭代器竟然是指针类型
// 所以这里是step 2.2
template
struct __copy_dispatch
{
T* operator()(T* first, T* last, T* result)
{
typedef typename __type_traits
::has_trivial_assignment_operator t; return __copy_t(first, last, result, t());
}
};
// step 2.2.1
template
inline T* __copy_t(const T* first, const T* last, T* result, __true_type)
{
memmove(result, first, sizeof(T) * (last - first));
return result + (last - first);
}
// step 2.2.2
template
inline T* __copy_t(const T* first, const T* last, T* result, __false_type)
{
return __copy_d(first,last,result,(ptrdiff_t*)0);
}
// step 2.1.1
// 普通输入迭代器如list
::iterator // 只能用迭代器++进行遍历操作，一个个移动，慢速
inline OutputIterator __copy(InputIterator first, InputIterator last, OutputIterator result, input_iterator_tag)
{
for (; first != last; ++result, ++first)
*result = *first;
return result;
}
// step 2.1.2
// 随机访问迭代器如vector
::iterator // 用数字++进行遍历操作，也是一个个移动，速度较快
inline OutputIterator __copy(RandomAccessIterator first, RandomAccessIterator last, OutputIterator result, random_access_iterator_tag)
{
return __copy_d(first, last, result, distance_type(first));
}
inline OutputIterator
__copy_d(RandomAccessIterator first, RandomAccessIterator last, OutputIterator result, Distance*)
{
for (Distance n = last - first; n > 0; --n, ++result, ++first)
*result = *first;
return result;
}
// 另外两个简单的函数
template
void fill(ForwardIterator first, ForwardIterator last, const T& value)
{
for (; first != last; ++first)
*first = value;
}
template
OutputIterator fill_n(OutputIterator first, Size n, const T& value)
{
for(; n > 0; --n, ++first)
*first = value;
return first;
}
通俗易懂时刻：在内存的拷贝时，我们想尽可能的快，这是我们最主要的目标。由于整数加减法运算要比迭代器移动要快，所以对于随机访问迭代器(包括原生指针)，我们采用整数加减法来控制遍历，这是其一。对于对象，如果该对象有简单的赋值操作符运算(has_trivial_assignment_operator=__true_type)，我们直接使用memmove这种超快速的拷贝，否则这种对象的拷贝只能交由对象本身的赋值操作符(operator=)来进行了。在后面的栗子中我们能看的很清楚。
一些辅助的栗子
如果你能看到这里，那算是我的成功了，说明前面的内容没有把你震飞，下面将进入比较舒适的区域，放松放松发烫的脑壳吧。
class C
{
public:
C() : _data(3){}
int _data;
};
int main()
{
// example 1
const char ccs[5] = {'a','b','c','d','e'};
char ccd[5];
copy(ccs, ccs+5,ccd);
// 调用copy(const char*, const char*, char*);
// example 2
int ia[5] = {1,2,3,4,5};
copy(ia, ia+5, ia);
// 调用step 1:copy()
// step 2.2:__copy_dispatch(T*, T*)
// step 2.2.1:__copy_t(T*, T*, T*, __true_type)
// example 3
list
ilists(ia, ia+5); list
ilistd(5); copy(ilists.begin(), ilists.end(), ilistd.begin();
// step 1:copy()
// step 2.1 __copy_dispatch(InputIterator, InputIterator, OutputIterator)
// step 2.1.1 __copy(InputIterator,InputIterator,OutputIterator,input_iterator_tag)
// example 4
vector
ivecs(ia, ia+5); vector
ivesd(5); copy(ivecs.begin(), ivecs.end(), ivecd.begin());
// step 1:copy()
// step 2.2:__copy_dispatch(T*,T*)
// step 2.2.1:__copy_t(T*,T*,T*,__true_type)
// 并不是以下调用方式
// copy()->__copy_dispatch(InputIterator)->__copy(random_access_iterator_tag)->__copy_d(Distance)
// example 5
C c[5];
vector
cvs(c, c+5); vector
cvd(5); copy(cvs.begin(), cvs.end(), cvd.begin());
// 用户自定义类型，默认拥有non-trivial ctor/dtor/operator=
// 调用过程如下
// step 1:copy()
// step 2.2:__copy_dispatch(T*,T*)
// step 2.2.2:__copy_t(T*,T*,T*,__false_type)
// __copy_d(Distance)
// example 6
deque
cds(c, c+5); deque
cdd(5); copy(cds.begin(),cds.end(),cdd.begin());
// step 1:copy()
// step 2.1 __copy_dispatch(InputIterator, InputIterator, OutputIterator)
// step 2.1.1 __copy(RandomAccessIterator,RandomAccessIterator,OutputIterator,random_access_iterator_tag)
// __copy_d(Distance)
// example 7
vector
strvs(5); vector
strvd(5); copy(strvs.begin(), strvs.end(), strvd.begin());
// step 1:copy()
// step 2.2:__copy_dispatch(T*,T*)
// step 2.2.2:__copy_t(T*,T*,T*,__false_type)
// __copy_d(Distance)
}
以上就是copy()的全部故事，一个无所不用其极强化效率的故事。
参考链接
STL萃取机
通俗易懂POD
迭代器类型