当前位置：文档库 › C++标准模板库STL介绍

C++标准模板库STL介绍

标准模板库STL(Standard Template Library)指南

刘振飞liuzf@p https://www.wendangku.net/doc/3211831071.html, 1999-10-20

/ **

* 这一程序是自由软件，你可以遵照自由软件基金会出版的GNU通用公共许可证条款来修* 改和重新发布这一程序。或者用许可证的第二版，或者(根据你的选择)用任何更新的

* 版本。

* 发布这一程序的目的是希望它有用，但没有任何担保。甚至没有适合特定目的的隐含的

* 担保。更详细的情况请参阅GNU通用公共许可证。

* 你应该已经和程序一起收到一份GNU通用公共许可证的副本。如果还没有，写信给：

* The Free Software Foundation，Inc.，

* 675 Mass Ave，

* Cambridge，MAO2139，USA

* 还应加上如何和你保持联系的信息。

1介绍 (3)

1.1 动机 (3)

1.2 STL历史 (3)

1.3 STL和ANSI/ISO C++草案标准 (3)

1.4 内容安排 (3)

2 C++基础 (4)

2.1 类 (4)

2.2 函数对象(Function Objects) (5)

2.3 模板(Template) (5)

2.3.1 函数模板 (5)

2.3.2 类模板 (6)

2.3.3 模板特化 (7)

3 STL概貌 (7)

3.1 STL网上信息 (8)

3.2 STL文档 (8)

3.3 编译STL程序 (9)

4 学习STL (9)

4.1 容器(Container) (9)

4.1.1 向量(V ector) (10)

4.2 迭代器(Iterator) (12)

4.2.1 输入和输出迭代器 (12)

4.2.2 向前迭代器 (13)

4.2.3 双向迭代器 (14)

4.2.4 任意存取迭代器 (14)

4.3 算法和函数对象 (15)

4.3.1 如何创建基本算法 (15)

4.3.2 STL算法 (17)

4.4 适应器(Adaptor) (19)

4.4.1 容器适应器 (19)

4.4.2 迭代适应器 (20)

4.4.3 函数适应器 (20)

4.5 分配算符和内存处理 (20)

5 其余的STL部件 (21)

5.1 各部件如何协同工作 (21)

5.2 向量(V ector) (21)

5.3 线性表(List) (22)

5.4 双向队列(Deque) (22)

5.5 迭代标签(Iterator Tag) (22)

5.6 关联容器(Container) (22)

6 版权信息 (24)

7 文献 (24)

8 后话 (25)

1介绍

1.1 动机

在七十年代末，Alexander Stepanov第一个发现一些算法不依赖于数据结构的特定实现，而仅仅和结构的一些基本语义属性相关。这些属性表达了一种能力，比如可以从数据结构的一个成员取得下一个成员，从头到尾“走过”结构中的元素〔就象排序算法不关心元素是存放在数组中或是线性表中）。Stepanov研究过一些算法可以用一种抽象的方式实现，而且不会影响效率。

1.2 STL历史

1985年，Stepanov开发了基本Ada库，有人要求他在C++中也这样做。但直到1987年，模板(Template)在C++中还未实现，所以他的工作推迟了。1988年，Stepanov到HP实验室工作，并在1992年被任命为一个算法项目的经理。在此项目中，Alexander Stepanov和Meng Lee写了一个巨大的库---标准模板库(STL：Standard Template Library)，意图定义一些通用算法而不影响效率。现在STL在国外已经成了新的编程手段。

1.3 STL和ANSI/ISO C++草案标准

1994年7月14日，ANSI/ISO C++标准化委员会将STL采纳为草案标准。现在Microsoft Visual C++ 5.0以上及Borland C++ 4.0以上都支持STL。STL已经并将继续影响软件开发的方法，有了STL，程序员可以写更少且更快的代码，把精力集中在问题解决上，而不必关心低层的算法和数据结构了。

1.4 内容安排

第2部分介绍STL需要的C++基础，主要是类、函数对象和模板。

第3部分是概貌，介绍了关键的思想。

第4部分step-by-step的教STL。

第5部分介绍剩余的STL部分。

第6部分是版权信息。

第7部分是参考文献。

2 C++基础

2.1 类

请读下面一段代码:

class shape

{

private:

int x_pos;

int y_pos;

int color;

public:

shape() : x_pos(0), y_pos(0), color(1) {}

shape(int x, int y, int c = 1) : x_pos(x), y_pos(y), color(c) {}

shape(const shape& s) : x_pos(s.x_pos), y_pos(s.y_pos), color(s.color) {} ~shape() {}

shape& operator=(const shape& s)

{

x_pos = s.x_pos;

y_pos = s.y_pos;

color = s.color;

return *this;

}

int get_x_pos() { return x_pos; }

int get_y_pos() { return y_pos; }

int get_color() { return color; }

void set_x_pos(int x) { x_pos = x; }

void set_y_pos(int y) { y_pos = y; }

void set_color(int c) { color = c; }

virtual void DrawShape() {}

friend ostream& operator<<(ostream& os, const shape& s);

};

ostream& operator<<(ostream& os, const shape& s)

{

os << “shape: (“ << s.x_pos << “,” << s.y_pos << “,” << s.color << “)”;

return os;

}

如果你不能轻松的读懂上面的代码，或者对以下概念：

·缺省构造函数(default constructor)、拷贝构造函数(copy constructor)、析构函数(destructor) ·操作符重载(operator overloading)

·虚函数(virtual function)

·put-to操作符(operator <<)

·友元(friend)、inline函数

不是很熟悉的话，说明你还需要看看C++的基础书籍。

2.2 函数对象(Function Objects)

所谓函数对象(function object)是定义了函数调用操作符(funiton-call operator，即operator())的对象。请看下面的例子：

class less

{

public:

less(int v) : val(v) {}

int operator()(int v)

{

return v < val;

}

private:

int val;

};

声明一个less对象：

less less_than_five(5);

当调用function-call operator时，看判断出传入的参数是否小于val：

cout << “2 is less than 5: “ << (less_than_five(2) ? “yes” : “no”);

输出是：

2 is less than 5: yes

函数对象在使用STL时非常重要，你需要熟悉这样的编码形式。在使用STL时，经常需要把函数对象作为算法的输入参数，或着实例化一个容器(container)时的输入参数。

2.3 模板(Template)

2.3.1 函数模板

请看下面的代码：

void swap(int& a, int& b)

{

int tmp = a;

b = tmp;

}

这个函数swap很简单：把两个整数的值交换一下。但当你写一个大程序时，经常需要交换float、long、char等变量，甚至如上面定义的shape变量，这时候你就需要把上面的代码修改一下，适应各自的参数类型，然后拷贝到很多处各自需要的地方。一旦需要对这块代码做些改动的时候，就必须把所有用到这块代码的地方一一做相应的修改，其烦无比！

解决这个问题的方法就是用模板(template)：

template

void swap(T& a, T& b)

{

T tmp = a;

a = b;

b = tmp

}

注意这里T是任意的类型名字。看例子：

int a = 3, b =5;

shape MyShape, Y ourShape;

float fa = 3.01, fb = 5.02;

swap(a , b); //交换整数

swap(MyShape, Y ourShape); //交换自定义类的两个对象的值

swap(fa, fb); //交换浮点数

还可以看看两个函数模板例子：

template

T& min(T& a, T& b) // 取两个元素中的最小者

{

return a < b ? a : b;

}

template

void pritn_to_cout(char* msg, T& obj) // 把一个元素输出到cout上

{

cout << msg << “: “ << obj << endl;

}

使用后者时，要求类型T中定义了put-to操作符(operator <<)。

2.3.2 类模板

创建类模板的动机和容器类的使用是密切相关的。比如一个容器类栈(stack)，定义者并不关心栈中对象的类型，而使用stack者自己指定到底包含什么对象类型。

下面看一个向量(vector)例子：

template

class vector

{

int sz;

public:

vector(int s) { v = new T[sz = s]; }

~vector() { delete [] v; }

T& operator[] (int i) { return v[i]; }

int get_size() { return sz; }

};

现在你可以实例化不同类型的vector容器了：

vector int_vector(10);

vector char_vector(10);

vector shape_vector(10);

2.3.3 模板特化

也许在某些情况下，编译器对某种类型产生的模板代码不另你满意，你也可以为这种类型给出一个特定的实现，此之谓“模板特化(template specialization)”。比如，你想让shape 类型的vector只包含一个对象，则可以特化vector模板如下：

class vector

{

shape v;

public:

vector(shape& s) : v(s) {}

shape& operator[] (int i) { return v; }

int get_size() { return 1; }

};

使用时：

shape MyShape;

vector single_shape_vector(MyShape);

STL中有时会需要定义特定类型的算法或容器实现。

3 STL概貌

STL是个部件库(component library)，其中的部件包括有容器(container，储存任意类型对象的对象)和算法。只要用户对自己定义的部件做点小小的要求，STL中的算法就可以工

后

我们可以把软件部件想象成一个三位空间。第一维表示数据类型(int, double, char, …)，第二维表示容器(array, linked-list, …)，第三维表示算法(sort, merge, search, …)。

根据这个图示，需要设计i*j*k个不同的代码版本，比如整数数组的排序算法、double 数组的排序算法，double linked-list的搜索算法…。通过使用数据类型作为参数的模板函数，第一维(i轴)就可取消，而仅需要设计j*k个不同的代码。下一步是让算法可以工作在不同的容器上，这就意味着排序算法既可以用在array上，也可用在linked-list上。最后，只需要设计j+k个不同的代码版本了。

STL具体化了上述思想，期望通过减少开发时间以简化软件开发，简化调试、维护并增加代码的可移植性。

STL包含5个主要的部分，以后会有较详细的陈述：

·算法(Algorithm)：能运行在不同容器(container)上的计算过程

·容器(Container)：能够保留并管理对象的对象

·迭代器(Iterator)：算法存取容器(algorithm-access to containers)的抽象，以便算法可以应用在不同的容器上

·函数对象(Function Object)：定义了函数调用操作符(operator())的类

·适应器(Adaptor)：封装一个部件以提供另外的接口(例如用list实现stack)

3.1 STL网上信息

STL的FTP站点

HP实验室(Alexander Stepanov和Meng Lee) ---

ftp://https://www.wendangku.net/doc/3211831071.html,/stl/

STL的WWW站点

David Mussers的STL主页---

https://www.wendangku.net/doc/3211831071.html,/~musser/stl.html

Link2go上有关C++编程的主页：

https://www.wendangku.net/doc/3211831071.html,/topic/C_and_C++_Programming_Languages

这三个地方我都去访问过。尤其第3个网址，其内容及其丰富，不仅仅有关STL。

3.2 STL文档

参考文献之

[6] 附件二

The Standard Template Libray以及源代码, Alexander Stepanov & Meng Lee, 1995-10-31

是个ZIP文件，其中包含Alexander Stepanov和Meng Lee写的<>(1995-10-31版)，这是STL鼻祖写的STL正式文档，定义严格、没有例子，很难懂(一些地方我还没理解)；但是ZIP文件中的STL源码却比较好懂，看起来不算太费劲--- VC++中STL的实现源代码读起来可是极其痛苦的。

3.3 编译STL程序

Borland C++4.0及以上的版本支持STL。Microsoft V isual C++ 5.0及以上的版本支持STL。(VC++4.2号称支持STL，但支持的很差，极难用。现在有VC++6.0，我们还是用最新的编译器吧!)

STL使用时很简单：

//MyFile.cpp

#include “stdafx.h”

…

#include //include你想用的STL头文件

using namespace std; //一定要写上这句话，因为STL都是在std名字空间中定义的

void F1()

{

…

vector v(10); //现在你就可以放心大胆的使用STL了

…

}

4 学习STL

4.1 容器(Container)

容器(Container)是能够保存其他类型的对象的类。容器形成了STL的关键部件。当书写任何类型软件的时候，把特定类型的元素集聚起来都是很至关重要的任务。

STL中有顺序容器(Sequence Container)和关联容器(Associative Container)。

顺序容器组织成对象的有限线性集合，所有对象都是同一类型。STL中三种基本顺序容器是：向量(V ector)、线性表(List)、双向队列(Deque)。

关联容器提供了基于KEY的数据的快速检索能力。元素被排好序，检索数据时可以二分搜索。STL有四种关联容器。当一个KEY对应一个V alue时，可以使用集合(Set)和映射(Map)；若对应同一KEY有多个元素被存储时，可以使用多集合(MultiSet)和多映射(MultiMap)。

4.1.1 向量(Vector)

如果你要将所有shape对象保存在一个容器中，用C++代码可以这样写：

shape my_shapes[max_size];

这里max_size是可以保存在my_shapes数组中的最大数量。

当你使用STL时，则可以这样写：

#include

using namespace std;

int main()

{

vector my_shapes;

// …使用my_shapes…

return 0;

}

【此后的代码不再写#inlucde行、using namespace std，以及main()函数，直接写示例代码】现在想得到容器中能保存的最大元素数量就可以用vector类的成员函数max_size()：vector::size_type max_size = my_shapes.max_size();

当前容器的实际尺寸--- 已有的元素个数用size()：

vector::size_type size = my_shapes.size();

就像size_type描述了vector尺寸的类型，value_type说明了其中保存的对象的类型：cout << “value type: “ << typeid(vector::value_type).name();

输出：

value type: float

可以用capacity()来取得vector中已分配内存的元素个数：

vector v;

vector::size_type capacity = v.capacity();

vector类似于数组，可以使用下标[]访问：

vector v(10);

v[0] = 101;

注意到这里预先给10个元素分配了空间。你也可以使用vector提供的插入函数来动态的扩展容器。成员函数push_back()就在vector的尾部添加了一个元素：

v.push_back(3);

也可以用insert()函数完成同样的工作：

v.insert(v.end(), 3);

这里insert()成员函数需要两个参数：一个指向容器中指定位置的迭代器(iterator)，一个待插入的元素。insert()将元素插入到迭代器指定元素之前。

现在对迭代器(Iterator)做点解释。Iterator是指针(pointer)的泛化，iterator要求定义operator*，它返回指定类型的值。Iterator常常和容器联系在一起。例子：vector v(3);

v[0] = 5;

v[1] = 2;

v[2] = 7;

vector::iterator first = v.begin();

vector::iterator last = v.end();

while (first != last)

cout << *first++ << “ “;

上面代码的输出是：

5 2 7

begin()返回的是vector中第一个元素的iterator，而end()返回的并不是最后一个元素的iterator，而是past the last element。在STL中叫past-the-end iterator。

begin()返回的iterator

两个迭代器给定的区间在STL中非常重要，因为STL算法中大量的使用区间。比如排序算法：

sort(begin_iterator, past_the_end_iterator);

第一个参数指向区间的第一个元素，而第二个参数指向区间的path-the-end元素。

有了迭代器作为媒介，我们就可以把算法(algorithm)和容器(container)分开实现了：

下面继续vector的内容。

你可以用以下的几种方法声明一个vector对象：

vector v(5, 3.25); //初始化有5个元素，其值都是3.25

vector v_new1(v);

vector v_new2 = v;

vector v_new3(v.begin(), v.end());

这四个vector对象是相等的，可以用operator==来判断。

其余常用的vector成员函数有：

empty()：判断vector是否为空

front()：取得vector的第一个元素

back()：取得vector的最后一个元素

pop_back()：去掉最后一个元素

erase()：去掉某个iterator或者iterator区间指定的元素

到现在我们已经可以把一些对象存储在容器(container)中，并有几种手段来进行管理和维护。为了将算法应用到容器中的元素上，下面要对迭代器(Iterator)做进一步的解释。

4.2 迭代器(Iterator)

迭代器(Iterator)是指针(pointer)的泛化，它允许程序员以相同的方式处理不同的数据结构(容器)。STL中有5中类型的迭代器，它们分别满足一定的要求。不同的迭代器要求定义

箭头表示左边的迭代器一定满足右边迭代器需要的条件。比如某个算法需要一个双向迭代器(Bidirctional Iterator)，你可以把一个任意存取迭代器(Random Access Iterator)作为参数；但反之不行。

4.2.1 输入和输出迭代器

输入迭代器(Input Iterator)需要满足的条件：

·constructor

·assignment operator

·equality/inequality operator

·dereferenc operator

·pre/post increment operator

输入迭代器表示要从其中取出一个值，即从输入迭代器X中取值只可有以下三种形式：V = *X++

V = *X, ++X

V = *X, X++

输出迭代器(Output Iterator)需要满足的条件：

·constructor

·assignment operator

·dereferenc operator

·pre/post increment operator

一个输出迭代器X只能有一个值V存储其中，在下一个存储之前，必须将X加一。即只可有以下三种形式之一：

*X++ = V

*X = V, ++X

*X = V, X++

注意，对输入和输出迭代器，一旦取出或放入值后，就只能前进(increment)，不可多次取出或放入。

4.2.2 向前迭代器

向前迭代器(Forward Iterator)需要满足的条件：

·constructor

·assignment operator

·equality/inequality operator

·dereferenc operator

·pre/post increment operator

和输入和输出迭代器比较而言，两个向前迭代器r和s，若r == s则++r == ++s。而且既可取值，也可赋值：*X = V, V = *X。看一个例子：

template

ForwardIterator find_linear(ForwardIterator first, ForwardIterator last, T& value)

{

while (first != last)

if (*first++ == value)

return first;

return last;

}

函数find_linear()在一个容器中循环，如果找到指定的值，则返回该值的迭代器位置；否则返回past-the-end迭代器。下面用这个函数：

vector v(3, 1);

v.push_back(7); // vector v: 1 1 1 7

vector::iterator i = find_linear(v.begin(), v.end(), 7);

if (i != v.end())

cout << *i;

else

cout << “NOT FOUND”;

输出结果：7

4.2.3 双向迭代器

在向前迭代器的基础上，双向迭代器(Bidirectional Iterator)还满足以下需求：

·pre/post decrement operator

即双向迭代器不仅允许++，而且允许--。它允许一个算法走过(pass through)容器中的元素时，即可想前走，也可向后走。

我们看一个使用双向迭代器的多遍走过(multi-pass)算法--- 气泡排序(Bubble Sort)：template

void bubble_sort(BidirectionalIterator first, BidirectionalIterator last, Compare comp)

{

BidirectionalIterator left_el = first, right_el = first;

right_el++;

while (first != last)

{

while (right_el != last)

{

if (comp(*right_el, *left_el))

iter_swap(left_el, right_el);

right_el++;

left_el++;

}

last--;

left_el = first;

right_el = first;

right_el++;

}

二元函数对象Compare由用户提供，得出两个参数的断言结果(true/false)。用法：

list l; // list类似于vector，但不支持下标[]存取

// 填充list

bubble_sort(l.begin(), l.end(), less()); // 递增排序

bubble_sort(l.begin(), l.end(), greater()); //递减排序

4.2.4 任意存取迭代器

在双向迭代器的基础上，任意存取迭代器(Random Access Iterator)还满足以下需求：·opetrator+(int)

·opetrator+=(int)

·opetrator-(int)

·opetrator-=(int)

·opetrator-(random access iterator)

·opetrator[](int)

·opetrator>(random access iterator)

·opetrator<(random access iterator)

·opetrator>=(random access iterator)

·opetrator<=(random access iterator)

也就是说，任意存取迭代器可以“任意的”前进和后退。

4.3 算法和函数对象

STL库中的算法都以迭代器类型为参数，这就和数据结果的具体实现分离开了。基于此，这些算法被称作基本算法(generic algorithm)。

4.3.1 如何创建基本算法

这里给出一个二分搜索的基本算法(generic bianry search algorithm)，可以看看基本算法的实现思路。

给定一个排好序的整数数组，要求二分搜索某个值的位置：

const int* binary_search(const int* array, int n, int x)

{

const int* lo = array, *hi = array+n, *mid;

while (lo != hi)

{

mid = lo+(hi-lo)/2;

if (x == *mid)

return mid;

if (x < *mid)

hi = mid;

else

lo = mid+1;

}

return 0;

}

为了让上述算法对任意类型的整数数组起作用，下面将之定义成模板函数：

template

const T* binary_search(const T* array, int n, const T& x)

{

const T* lo = array, *hi = array+n, *mid;

while (lo != hi)

{

mid = lo+(hi-lo)/2;

if (x == *mid)

return mid;

if (x < *mid)

hi = mid;

else

lo = mid+1;

}

return 0;

}

在上面的算法中，如果没有找到指定的值，则一个特殊的指针NULL (0)被返回了，这就要求这个值存在。我们不想做这样的假定这样的值，可以不成功的搜索返回指针array+n (就是past-the-end)来代替：

template

const T* binary_search(const T* array, int n, const T& x)

{

const T* lo = array, *hi = array+n, *mid;

while (lo != hi)

{

mid = lo+(hi-lo)/2;

if (x == *mid)

return mid;

if (x < *mid)

hi = mid;

else

lo = mid+1;

}

return array+n;

}

为了代替给定数组及尺寸，我们可以给定第一个及past-the-end元素的指针：

template

const T* binary_search(T* first, T* last, const T& value)

{

const T* lo = first, *hi = last, *mid;

while (lo != hi)

{

mid = lo+(hi-lo)/2;

if (value == *mid)

return mid;

if (value < *mid)

hi = mid;

else

lo = mid+1;

}

return last;

}

现在可以看出，first和last两个指针是任意类型的指针，即它们和类型T是没有关系的。这时就用到了迭代器(Iterator)的概念，因为这里排序要对容器任意存取，我们把first和last的类型命名为“RandomAccessIterator”。代码改写如下：

template

RandomAccessIterator binary_search(RandomAccessIterator first, RandomAccessIterator last, const T& value)

{

RandomAccessIterator not_found = last, mid;

while (first != last)

{

mid = first+(last-first)/2;

if (value == *mid)

return mid;

if (value < *mid)

last = mid;

else

first = mid+1;

}

return not_found;

}

上面这个基本二分搜索算法即使对内部类型(build in types)功能也一样：

int x[10]; // 10个整数数组

int search_value; // 太搜索的值

// 初始化变量

int* i = binary_search(&x[0], &x[10], search_value);

if (i == &x[10])

cout << “value NOT FOUND”;

else

cout << “value found”;

所有STL中的算法都是用以上类似的办法定义的。

4.3.2 STL算法

也会改变元素的顺序，但把排序相关的操作独立于Group1列出来了。Group4中是些常用的数字操作。

先看个Group1中的一个算法“对每个(for_each)”，有三个参数，两个输入迭代器，一个函数对象。这个操作的意思是对[first, last)的每个元素都做一个Function操作：template

Function for_each(InputIterator first, InputIterator last, Function f) {

while (first != last) f(*first++);

return f;

}

下面给一个使用for_each的例子：

template

class sum_up

{

public:

void operator() (const T& value) { sum += value; }

const T& read_sum() { return sum; }

private:

static T sum;

};

int sum_up::sum = 0;

void main()

{

deque d(3, 2); // 两个元素：3 3

sum_up s;

for_each(d.begin(), d.end(), s);

cout << s.read_sum();

}

输出结果：6。注意到这里用到了函数对象sum_up，它定义了operator。所以函数对象是STL 中一个非常重要的概念，屡屡用到。

Group1中还有其他的操作，如“寻找(Find)”、“邻居寻找(Adjacent find)”、“计数(Count)”、“不匹配(Mismatch)”、“相等(Equal)”、“搜索(Search)”等。

说明，如果某个算法的后缀是_if，表示它自己提供断言(Predicate)函数，比如find算法有find_if的变种。

Group2中的有算法“拷贝(Copy)”、“交换(Swap)”、“变换(Transform)”、“替换(Replace)”、“填充(Fill)”、“产生(Generate)”、“迁移(Remove)”、“唯一(Unique)”、“翻转(Reverse)”、“旋转(Rotate)”、“任意洗牌(Random shuffle)”、“分区(Partitions)”。

说明，如果某个算法的后缀有_copy，表示它要把一个迭代器区间的内容拷贝到另一个迭代器中。比如replace有replace_copy的变种。

Group3中的排序算法都有两个版本，一个用函数对象做比较，一个用operator<做比较。比如算法“排序(sort)”有两个版本：

void sort(RandomAccessIterator first, RandomAccessIterator last);

void sort(RandomAccessIterator first, RandomAccessIterator last, Compare comp) ;

Group3中还有算法“第N个元素(Nth element)”、“二分搜索(Binary Search)”、“合并(Merge)”、“排好序的设置操作(Set operations on sorted structures)”、“堆操作(Heap Operations)”、“最大最小(Minimum and Maximum)”、“词典比较(Lexicographical

comparison)”、“置换产生器(Permutation generator)”。

Group4中包含些常用的数字算法，比如“聚集(Accumulate)”、“内部乘积(Inner product)”、“局部和(Partial sum)”、“邻近不同(Adjacent difference)”。

由于时间和篇幅的关系，这里不可能对所有的算法一一解释了。用的时候你可以再看具体算法的说明。如果你搞明白算法实现，建议你读读STL的源码，我认为写的很漂亮，读起来感觉不错。(目前我也只读了部分代码)

4.4 适应器(Adaptor)

适应器(Adaptor)是提供接口映射的模板类(Adaptors are template classes that provide interface mappings)。适应器基于其他类来实现新的功能，成员函数可以被添加、隐藏，也可合并以得到新的功能。

4.4.1 容器适应器

栈(S tack)

栈可以用向量(vector)、线性表(list)或双向队列(deque)来实现：

stack> s1;

stack >s2;

stack> s3;

其成员函数有“判空(empty)”、“尺寸(Size)”、“栈顶元素(top)”、“压栈(push)”、“弹栈(pop)”等。

队列(Queue)

队列可以用线性表(list)或双向队列(deque)来实现(注意vector container不能用来实现queue，因为vector没有成员函数pop_front!)：

queue> q1;

queue>q2;

其成员函数有“判空(empty)”、“尺寸(Size)”、“首元(front)”、“尾元(backt)”、“加入队列(push)”、“弹出队列(pop)”等操作。

优先级队列(Priority Queue)

优先级队列可以用向量(vector)或双向队列(deque)来实现(注意list container不能用来实现queue，因为list的迭代器不是任意存取iterator，而pop中用到堆排序时是要求random access iterator的!)：

priority_queue, less> pq1; // 使用递增less函数对象排序priority_queue, greater> pq2; // 使用递减greater函数对象排序

其成员函数有“判空(empty)”、“尺寸(Size)”、“栈顶元素(top)”、“压栈(push)”、“弹栈(pop)”等。

4.4.2 迭代适应器

逆向迭代器(Reverse Iterator)

顾名思义，逆向迭代器的递增是朝反方向前进的。对于顺序容器(vector, list和deque)，其成员函数rbegin()和rend()都返回了相应的逆向迭代器：

list l;

for (int i = 1; i < 5; i++)

l.push_back(i);

copy(l.rbegin(), l.rend(), ostream_iterator (cout, ““));

输出结果是：4 3 2 1

插入迭代器(Insert Iterator)

插入迭代器简化了向容器中插入元素的工作。插入迭代器指定了向容器中插入元素的位置。STL中有三种插入迭代器：

·向后插入(back_insert_iterator)，在容器尾部插入

·向前插入(front_insert_iterator)，在容器头部插入

·插入(insert_iterator)，在容器中任一位置

STL中提供了三个函数分别构造相应的插入迭代器：

·back_inserter

·front_inserter

·inserter

原始存储迭代器(Raw Storage Iterator)

该迭代器允许算法将其结果保存进没有初始化的内存中。

4.4.3 函数适应器

否认者(Negator)

有两个否认者not1和not2分别是一元和二元函数，它们分别使用一元和二元的谓词(Predicate)，返回的是谓词的结果的取反。

包扎者(Binder)

STL中有两个包扎者函数bind1st和bind2nd，可以将一些值限定在指定区间中。

函数指针的适应器(Adaptors for pointers to function)

STL中的算法和容器一般都需要函数对象(function object)作为参数。如果想用到常用的C++函数时，可以用ptr_fun把普通函数转换成函数对象。比如ptr_fun(strcmp)就把常用的串比较函数strcmp包装成一个函数对象，就可用在STL算法和容器中了。

4.5 分配算符和内存处理

可移植性的一个主要问题是能够把有关内存模型的信息封装起来。这些信息有：