STL的总结

STL的尾声

STL的提出过程：从具体的证明步骤或算法步骤中，提炼出公理性条件，然后再从这个公理条件出发，参考具体情形下的证明或算法步骤，给出一般性步骤。如数学中的群环等结构的推断，是矩阵和四元数等计算结构的进一步推广，C++ STL的迭代器是C/C++指针的一个推广。

具现：将C++ STL中模板用调用时传入的C++ 类型替换。

屏蔽警告：#pragma warning(disable:4786)

一、概念

1、容器：C++ STL所提供的泛型数据结构用模板类给出，统称为容器。

2、迭代器：指针的泛化，在容器和算法之间起桥粱作用，使算法不依赖于具体的数据结构。但是，迭代器却是依赖于数据结构的。

3、算法：架构在迭代器之上，把迭代器值作为它的参数。容器向外界提供迭代器，以访问它的结构数据。

在数学的抽象群论中，用一套四则运算概念，给出一个集合(如实数集)成为个群的条件。利用群所定义的运算性质进行演绎，推断出的结论结论必然适合于群定义的所有具体集合。体现了数学命题的可重用性。

4、函数对象：为了不依赖硬件系统。常用结构体来定义，在其内部实现一个operator()操作函数，以支持f()函数调用形式。如下所示：

template<class InIt, class Fun>

Fun for_each(InIt first, InIt last, Fun f){

...

f(*first)//调用f对象的函数operator().对每个元素进行处理

...

}

template <typename T>

struct negate{

T operator()(const T& x)const {return -x;}

}

如此，既解决了函数类型的问题，又可继续使用f()

函数对象解决了在算法中调用外部函数的问题。应当注意："T*"中的通配符"*"不能用作模板类型的标志符。

STL定义了一些常用的函数对象，都是相应的二元关系函数的一个封装，从结构体binary_function继承过来。结构体binary_function的作用是提供参数类型和返回值类型信息。定义在stl_function中。

5、适配器相当于类型转换。

迭代器适配器

为了解决"T*"无法作为模板类型的问题，在类的内部添加相关的类型信息。以后，就可利用iterator_traits来获取这些类型信息。

template<class It>

struct iterator_traits {

typedef It::iterator_category iterator_category;

typedef It::value_type value_type;

typedef It::distance_type distance_type;

};

函数对象适配器

一个返回bool值的函数对象，称为谓词判断(Predicate)。函数对象适配器的作用在于将双参数的函数对象转换为单参数的函数对象，以适用算法的要求。

传递某个值给二元函数对象，也叫绑定，以将二元函数转为一元函数对象。常用binder1st和binder2nd，分别将数值绑定二元函数的第1个参数和第2个参数。

template<class Pred>

class binder1st

: public unary_function<Pred::second_argument_type,

Pred::result_type> {

public:

binder1st(const Pred& pr, const Pred::first_argument_type x);

result_type operator()(const argument_type& y) const;

protected:

Pred op;

Pred::first_argument_type value;

};

设二元对象是f(T1&,T2&)。binder1st封装的是binder1st(T2 x),T2是第二个参数。只要定义binder1st(T2,x)为f(value,x)的调用，就把f的第1个参数绑定为value。

#include <vector>

#include <iostream>

#include <algorithm> //find_if算法

#include <functional>

int main(void){

using namespace std;

vector<int> v;

v.push_back(20);

v.push_back(13);

v.push_back(6);

v.push_back(3);

v.push_back(29);

vector<int>::iterator less7_iter=

find_if(v.begin(),v.end(),bind1st(greater<int>(),7));

cout << *less7_iter << endl; //将打印数字

return 0;

}

一般可直接在算法中使用函数，编译器将函数自动转换为函数对象。

6、内存分配器

C++ STL的内存分配器是一些用于内存管理的模板类。

提供有两种内存分配器，一种是一次性划出大块内存，然后分成若干小块，以产生最小碎片为原则。另一种是内存分配器malloc_alloc。malloc_alloc调用allocate函数调用malloc函数进行内存分配，失败时用allocate不断尝试进行分配，deallocate用free函数进行内存释放,reallocate用realoc函数重新调整内存块的大小，失败时不断尝试。

SGI使用双层配置器，如果分配的空间大于128bytes则采用第一级配置器，直接调用malloc(),free()；如果分配的空间小于128bytes则采用复杂一点的memory pool方式。在SGI中一级配置器的实现依靠的是模板类__malloc_alloc_template，二级配置器依靠模板类__default_alloc_template

7、C++ STL 通过模板来传递类型参数。为泛型算法函数的所有模板类型，从算法的实现步骤中归纳出相应的一个概念，用概念来指出用于具现的类型必须满足的运算条件，而满足某个概念所定义条件的类型则称为该概念的一个模型。

如InputIterator概念指出输入迭代器必须具有!=,==,*,++运算，int*就是这样一个模型。再如vector是containor的一个模型。

将概念所定义的运算性质，作为构造通用库的代码演绎的起点，是STL之父的革命性思想。算法模型中的参数模型类型可提示迭代器所要满足的概念条件。

算法原型中的参数模板类型可提示迭代器所要满足的概念条件。算法通过迭代器存取数据，容器则向外界提供迭代器，以访问它的结构数据。

8、概念

容器，迭代器和函数对象的实现规范，定义他们必须具备的操作性质。

1）基础性概念