配接器、萃取器、分配器、迭代器--STL的精髓

天人雨 — Tue, 01 Nov 2011 02:04:00 GMT

今天重读《STL源码分析》，一目十行，看的很爽，想起当年看这本书，看着脑袋就大。说明这些年，功力还是有所增长的。
STL的精髓，总结起来，就四点：配接器（包括仿函数），萃取器、分配器、迭代器。其中分配器和迭代器是常人能想出的产物，萃取器是高手想出的产物，配接器是大师想出的产物。

分配器需要记住的是，一般的内存分配器没有启用次级分配能力，只启用了一级分配器，即直接使用malloc和free来分配释放内存，STL为了提高效率，将分配内存和调用构造函数分开，为的是节省某些不需要调用构造函数的开销。次级分配能力在启用后，会根据分配内存的大小来决定是否使用内存池。

迭代器需要注意的地方，只有在其中使用的萃取器，这个萃取器的设计还是比较神妙的，迭代器作为一个类，在泛型算法中，怎样让编译器推导出返回值？普通的做法是使用typedef，但直接将迭代器传入的类型做typedef并不能解决泛型算法对裸指针的兼容。于是，萃取器出现了。

template <class T>
struct iterator_trait
{
typedef T value_type;
}

template <class I*>
struct iterator_trait
{
typedef I value_type;
}

这样无论是真正的Iterator还是int*，获取的value_type都是真正的对象类型。（还需要对const int*进行萃取）。
萃取器在迭代器中的神妙使用，使其在其他地方也被使用，打个比方，有的类需要调用构造函数，有的类不需要调用。如果让我等菜鸟去设计，肯定逃不过if-else或者虚函数。但是STL使用了一种更为高效、优雅的解决方案。
首先，定义两个空类，true_type,false_type;
然后，定义萃取器：
template
struct __type_trait
{
typedef true_type need_construct;//默认时所有类都需要调用构造函数
}
假设int不需要调用构造函数，则对模板进行特化：
template
struct __type_trait
{
typedef false_type need_construct;
}
然后，定义两个重载的函数：
void func( true_type ); //这个函数里面会调用构造函数
void func( false_type ); //这个函数里面不会调用构造函数
最后，调用func时这么调用：
func( __type_trait::need_construct );
OK，这里没有分支，没有虚函数，最高效。这就是元编程的威力，实际上，编译器就为我们提供了重载的能力！

对迭代器来说，其中有五种型别，是需要萃取实现的，他们分别是：
1，value_type：表示该迭代器指向的是什么类型
2，different_type：表示迭代器之间的距离是什么型别的，一般是int
3，pointer_type：指针类型，表示value_type的指针类型是啥
4，reference_type：引用类型，表示value_type的引用类型是啥。
5，iterator_category：表示该iterator是一个什么类型，是双向的？还是单向的？还是随机的？
这些类型都是要通过萃取得来的，否则无法兼容裸指针
此外，还有size_type之类的型别。反向的迭代器，其实是一个配接器，怎么配结的呢，反向迭代器也是一个模板类，这个模板类在获得T之后，就获得了真正对象的控制权，于是做出如何的行为就都可以实现了。

分配器是最神妙的东西，如果不去仔细阅读代码，分配器简直可以用巧夺天工来形容，但读了代码之后，才发现其中奥妙。
说到分配器，就不能不谈仿函数，仿函数就是利用对象的（）重载，来实现函数的功能，STL只支持一元仿函数和二元仿函数。注意，这点很重要，多元的仿函数，会让制作配接器的人很烦。配接器是怎么做的呢？配接器的原理就是，配接器也是一个类，这个类在构造的时候，传入仿函数的对象，这样，配接器内部就可以将仿函数对象作为成员记载下来，等（）去执行的时候，再去使用成员去调用仿函数。由于类里面可以有多个成员，这样，就可以将多个仿函数进行组合后一起调用，实现一些很神奇的功能。
为什么STL里面的泛型算法全部是仿函数？就是因为只有仿函数，才能让配接器实现，如果使用函数，配接器是无法实现的，因为配接器是类，类里面即使保存函数的指针，可以实现一次配接，但配接之后就不能再配接了。而使用仿函数的话，由于配接器也是对象，配接之后还可以再配接，形成自由组合，循环，神妙得多。如果配接器不使用类，那么配接时要存储的仿函数或者函数指针就没地方放，全局变量是没有域限制的。
仿函数如果要支持被配接，就必须继承unary_function类（一元）或者binary_function类（二元），这里面定义了返回值和参数的性别，这使得构造配接器时，就可以直接使用这些性别来进行配结。
构建完配接器这么强大的体系之后，STL再提供了将普通函数配接为仿函数的配接器，提供了将成员函数配接为仿函数的配接器，这样，普通函数和成员函数也可被配接器配成仿函数之后再进行配结，从而实现了程序过程的完全自由组合。

天人雨 2011-11-01 10:04 发表评论

智能指针

天人雨 — Fri, 30 Sep 2011 04:16:00 GMT

摘要: Code highlighting produced by Actipro CodeHighlighter (freeware)http://www.CodeHighlighter.com/-->#include using namespace std;template class&nb... 阅读全文

天人雨 2011-09-30 12:16 发表评论

C++博客-Amazing110

配接器、萃取器、分配器、迭代器--STL的精髓

智能指针