|
- UID
- 1029342
- 性别
- 男
|
前段日子读了STL的源码，大师级的作品真是精致到让人喟叹。当然，有时候你在网上还是可以看到很多对STL的批评，例如，对编译器要求很高，很多时候出错了的话，打印出来的错误信息总是让人摸不着头脑的。这确实是比较头疼的一个问题，因为模板编程，编译的过程总是分为两个部分的，是先要找到相应的模板，然后才对模板进行具现化，有时候单纯从模板来看，似乎很完整，没有什么问题呀，可是一旦投入使用了，才发现找不到合适的具现化版本，于是又要搞特化了。某日在路上行走，突然想起爱情这个难题，突然想起具现化，突然觉得爱情就像是一个模板类，是想象，没有实现的时候，它看起来很完美，很丰富，可是爱情一旦具现化，它便成了独此一家的一个类，想象的空间本就狭窄了，倘若需求比较复杂，还须得有偏特化版本，不然就要出错。每个女人心目中的恋爱对象都是完美的，是那种选择性的完美，她爱的并不是那个实体，而是加诸于该实体上的想象。好了，不管你看没看懂，还是言归正传了。
STL的设计非常巧妙，组件间互取短长，形成了一个世界，这是这个世界里的组件：
1. containers（容器）：所谓容器，是指存放数据的地方，将数据以一定的方法组织存放。根据不同的组织方式，可以把容器分为顺序容器，如vector、deque、list，关联容器，如set、map。Container是一种class template。
2. algorithm（算法）：各种常用不常用的算法如sort、copy、search等等。algorithm是一种function template。
3. iterator（迭代器）：迭代器是算法和容器之前的胶合剂，算法作用于容器之上，但算法以迭代器作为形参。从实现上看，迭代器是一种将operator*，operator++，operator--，operator->等指针相关操作予以重载的class template。所以容器都带有自己的迭代器，因为只有容器设计者才知道如何遍历自己的元素。
4. functors（仿函数）：行为类似函数，可作为算法的某种策略。从实现的角度来看，仿函数是一种重载了operator()的class或class template，它常常是算法的一个输入，类似于一种策略。
5. adapters（适配器）：用来形容容器、迭代器或仿函数接口的东西，有时候上面那些组件的行为可能跟我们想要的约束不大一样，于是给它们包装一下，使它们遵守一定的行为。
6. allocator（配置器）：负责空间配置与管理。从实现的角度来看，配置器是一种实现了动态空间配置、管理、空间释放的class template。
STL中的空间配置器，使用了两层架构，一层用于分类大块内存，一层用于管理小块内存。大块内存基本上是用完了就返回给操作系统，而小块内存则由内存池管理。另外，我们知道当我们new一个对象的时候，不仅仅是给了它内存，同时还可能调用了构造函数对这块内存进行了初始化（假如它是用户自定义类型），当我们delete一个对象的时候，同样，也可能是先调用了析构函数，然后再把内存还回去。调用构造、析构函数是要付出代价的，可是对于基本类型如int、long这种Plain-Old-Data，根本就不存在这样的构造/析构函数，便没有必要为它花费这种心思了。因此，为了便于分开处理这两种情况，STL把new/delete的执行过程分开成了两部分，一部分放在<stl_construct>里，用于在必要的时候调用构造、析构函数，一部分放在<stl_alloc>里，用于策略性地分配内存，跟内存分配管理相关的，还有一个<stl_uninitialized>，针对多个对象的初始化、复制做了一定的优化（当然也是以是否为POD来区分）。
<stl_construct>里定义了一个construct和两个destroy，construct基本上就是一个placement new，在指定内存上调用构造函数，而destroy有两个版本，一个是只析构单独一个对象的，直接调用了对应的~T()版本，另一个版本用于析构一段范围内的对象，这样的话如果对象是POD类型的，还for[i,j)地去执行，就是一种无谓的浪费了，因此，这个destroy将根据数据类型，决定调用特定版本的__destroy，如果是POD类型，则什么都不做，如果不是POD类型，则for[i,j)地去调用~T()。这些类型判断都是在编译时就确定的（通过__type_traits<T>::has_trivial_destructor），因此并不影响运行时效率。另外你肯定会想，为什么针对destroy这番考虑，针对construct却没有呢？反正当时我就是这么想的，后来发现原来这些事情交给uninitialized_fill、uninitialized_copy和unintialized_fill_n去做了，因为对象的初始化可能是经由constructor，也可能是经由copy constructor去执行呀。这里面，**_copy可能在必要的时候直接使用memmove来执行。
然后就是那个大头，空间分配器了。<stl_alloc.h>内定义了两个template，一个是__malloc_alloc_template，这是sgi stl的一级配置器，它的allocate()直接使用malloc()而deallocate()直接使用free()，同时，它模拟C++的set_new_handler()处理内存不足的状况。第二个是__default_alloc_template，它维护了16个free list，每个list上集合着大小分别为8，16，24，...128大小的内存块。内存池以malloc()配置而得，如果内存不足，转调用第一级配置器，因为那里设置了内存不足的处理程序。如果请求的内存块大小大于128bytes，就转调用第一级配置器。另外定义了两个alloc，一个是debug_alloc，每次配置一块内存时，都会配置比需求多8byte的空间以存储空间大小，通过assert语句来检查会不会内存溢出。另一个是simple_alloc，定义了两个版本的allocate和deallocate，它们都只是单纯的转调用。sgi stl容器全都使用simple_alloc接口。free-list的节点巧妙地使用了一个union结构来管理链表：
Cpp代码 [url=] [/url]
- union obj{
- union obj* free_list_link; //当作为自由链表的一个结点时，存储其下一个节点的地址
- char client_date[1]; //当其作为返回值时，返回的正好是分配内存的首地址
- }
每次配置器需要向系统要内存的时候，都不是按客户需求向系统申请的，而是一次性向系统要了比需求更多的内存，放在内存池里，有一个free_start和free_end指示剩余的空间（也就是说内存池剩余的空间都是连续的，因此每次重新向system heap要空间的时候，都会把原先内存池里没用完的空间分配给合适的free list。）当free-list中没有可用区块了的时候，会首先从内存池里要内存，同样，也不是以按客户需求要多少块的，而是一次可能会要上20块，如果内存池内空间允许的话，可能会得到20个特定大小的内存，如果内存池给不了那么多，那么就只好尽力给出；如果连一个都给不出，那么就要开始向系统即system heap要空间了。换算的标准是bytes_to_get=2*total_bytes+ROUND_UP(heap_size>>4)。这个时候使用的是malloc，如果没成功，就尝试着从大块一点的freelist那里要一个来还给内存池，如果还是不行，那么会调用第一级空间配置器的malloc::allocate，看看out-of-memory机制能做点什么不。 |
|
