轻轻松松学
爱华
一个新标准的出现，对于熟习旧环境的工程师而言，总是有近乡情怯之感。明知新标准一定比旧标准来的好，但对于旧标准总是有那么一点依依不舍，对新标准也总是有些许隔阂，虽然几个月后就不这么想了。
C++ STL程式库的出现，对于习惯使用Borland C++等等程式库的工程师而言，也有类似的感觉。有人说：C++就是把C语言那些令人既爱又恨的程式技巧，予以标准化，成为语言的一部份；STL则是把C++那些令人期待盼望的功能，予以公开化，让大家不用花大钱买程式库就可使用！而且使用STL，不必担心日后程式码会有大更动，因为毕竟这是ANSI C++的标准。所以本文将从STL概念上的基本原则出发，带您在复杂的STL程式库中找寻自己的认知天地
如果您对STL起源与基本结构有兴趣，可以参考上期STL的简介，或是到下面这个WWW站参考一下最新资讯，里面有ANSI C++通过的最新STL版本等等资料。
http://www.cs.rpi.edu/~musser/stl.html
STL对编译器要求
每当我们学习一个新的程式库，通常第一个会问的，就是如何在我的编译器上，写一个简单的程式，证明它可以跑。STL对编译器的要求很严格，以最普遍的Borland C++ 4.5为例，Borland C++必须在程式码前加一段：
#define __MINMAX_DEFINED
#pragma option -vi-
才可以跑程式，并且include的路径也要设对。而微软的Visual C++ 4.0因为不支援DOS模式下的程式，如果要简化GUI的处理来使用STL，最简单的方式便是在Console Application模式下写程式，而且include的路径也要设对，如此才可以跑。至于Visual C++2.x版本的编译器，因为template机制做的不好，并不能编译STL程式库。值得注意的是，这里所说的「可以跑程式」，并不代表所有STL的功能都可以使用，因为C++ template机制过于复杂，可以有很多种变化，现今的编译器技术无法正确的实作，所以现在用STL所写的程式，日后或多或少还是需要修改，但已经比以往使用专属程式库改版时，需要做的修改来得少很多。
STL的基本概念：Container,Iterator,Algorithm
在学习STL之前，让我们介绍STL最基本的概念，如图一：演算法物件透过Iterator操作各种容器物件，完成运算。而除了基本的演算法由STL内建提供外，工程师可以自己定义一些新的辅助演算法（help function，或称辅助函数），来完成新的计算。这些新的辅助演算法，通常是利用C++的template function的方式设计。您可能会问，依照OO理论对于物件的定义，为什么称STL的演算法物件为「物件」，它其实只是函数而已？答案是：因为C++中的函数名称事实上也是一种型别，利用typedef可将之宣告成指向函数指标的型别，所以当我们以C++中的型别为准，enum、union、struct、typedef等等关键字都可看做是一种类别的变形宣告，也因此可以把单一函数看做是物件（没有资料成员的物件）。
图一左边的容器物件，STL则定义三个最基本也最常用到的的容器物件：vector,deque,list。而其他各种资料结构教科书上定义的特定资料结构，如stack, heap, binary tree等等，都可以再利用这三个基本的容器，加以变化，实作之。基本上，图一左边的物件，STL利用C++的template class制作。
图一、STL的根本概念
所以有些人（如[Nel95]书）就把STL的功能分成五大部份，掌管图一从左至右大大小小的事情，如图二：
图二、STL的五个部份[Nel95]
演算法物件，Iterator物件，容器物件仍在，STL的Adaptor物件包装了由基本容器物件所产生的变形资料结构，如stack,queue,priority_queue等；Function物件则辅助演算法物件完成一些更为基本的运算，如比较大小等。以下，我们将以图一的原则审视STL的各组成部份。
Container
Container顾名思义，就是一种容器，里头可以装各式各样的物件。如下，
template <class T>
class container {
T d;
};
透过template<class T>，T可表示任意物件所属的类别，于是在容器类别内产生一个T类别的物件d。由于T可以表示各种资料型别，不管是C++内建的基本资料型别或是利用class定义的类别，都可以存入STL的容器物件中。
STL将容器物件分为两种，循序式容器(Sequence Container)与关系式容器(Associate Container)。循序式容器内的每一个元素，只能包含一种物件，且各元素的排列顺序完全依照元素插入时的顺序。关系式容器内的每一个元素，则包含两种物件，一个为键物件(key object)；一个为值物件(value object)，且各元素的排列顺序完全依照键物件决定。
循序式容器
循序式容器又可分成四种基本的容器类别，C语言指标中的记忆体（您可想象其为一个巨大的阵列）、vector（向量）、deque（双向伫列）、list（串列），一个简单的vector容器使用如下：
// test program for vector container
#include <iostream.h>
#include <vector.h>
void main() {
vector<char*> v;
v.push_back("me");
v.push_back("you");
v.push_back("he");
v.push_back("she");
for(int i=0;i<4;i++)
cout<<v[i]<<"\n";
}
//end程式输出
me
you
he
she
vector<data_type>表示我们可以放入各种资料型别到<...>之中，vector物件便会正确的产生空间存放此型的物件。v.push_back(object)函数则把属于该型别的物件存入容器物件的记忆空间中。
一个vector容器好比一个传统C语言中的阵列，只是传统C语言中的阵列必须明确地指出阵列大小，如果注标值超过边界值，则系统将得到一个未知的错误。然而，STL的vector容器却不然，vector容器自己视需要，自动加大阵列的大小，所以应用程式就不需担心注标值超过阵列范围。图示如三。
start表示阵列起始处，finish表示阵列结束处，end_of_storage表示实际阵列结束的地方，如果阵列仍持续成长，超过end_of_storage，则vector容器会自动在配置一块记忆体，维持注标值不超过边界值。
其他STL的基本容器简介如下：
1.deque容器如同资料结构中的双向伫列，单向伫列具有FIFO的性质，双向伫列则更进一步可以由两边存入资料。
图三、vector容器的记忆体结构
2.list容器为一个双向串列，可以实作树等资料结构。
3.C语言中的记忆体则为最传统的容器物件，因为记忆体也可以储存各种型态的物件，只要透过适当的C语言指标指向之即可。
关系式容器
关系式容器，STL共定义了set<Key>、multiset<Key>、map<Key,T>、multimap<Key,T>四种容器物件，其主要特色为：「物件带有关键值」。每种容器的特色如下：
Key可重复吗？
容器有资料成员吗
set<Key>
否
否
multiset<Key>
是
否
map<Key,T>
否
是
multiset<Key,T>
是
是
关系式容器让C++程式可以处理关系式资料。关系式资料是指一组资料由键值与资料成员所组成。如同资料库对资料表格的定义，STL的关系式容器中的键值可以选择是否重复，不可重复的关系式容器好比数学中的集合概念，集合内的资料皆是唯一性的。由于这些容器在存入资料成员时都会把新的资料成员依键值做排序，所以您可想象成好比一个有序的表或集合，甚至关系式容器也容许资料成员是空的，容器只储存键值，并做排序而已。
一个简单使用map容器的程式如下：
//work for Borland C++ only
#include <iostream.h>
#include <iomanip.h>
#include <cstring.h>
#include <map.h>
void main() {
map<string,int,less<string>> m;
m["me"]=1;
m["you"]=2;
m["he"]=3;
m["she"]=4;
cout<<setw(3)<<m["she"]<<setw(3)<<m["he"]<<setw(3)
<<setw(3)<<m["you"]<<setw(3)<<m["me"];
}
//程式输出
4 3 2 1
less<string>为一个比较类别，目的在于如何在众多物件中(string物件)，知道哪一个物件优先权高、哪一个低。而键物件是指“me”、“you”等字串，资料成员物件是指1、2、3、4等整数物件。
由上表，我们知道关系式容器的每个元素最多可含两种物件。只含有键物件的统称set类物件；含有键物件与值物件的统称map类物件。而每类物件又可依其是否可含重复键，分成single物件与multi物件。这些物件事实上都是资料结构中的树状结构。每个容器在存入物件时，便依键物件的大小决定它在树中的位置。而less<string>是后段提到的Function物件，在此先略过不谈。
关系式容器的功用还可加以扩大，如同资料库程式对于关连式表格的应用，STL关系式容器可以很直觉地对应的关连式资料库中的表格，再搭配下期将介绍的「扩充STL的Allocator物件」，便可使您的C++程式拥有简单的永存机制(persistence)，成为物件导向资料库系统(OODB)。
Iterator
Iterator物件之于容器物件，好比指标之于记忆体。外部程式透过Iterator，可以在不知容器物件内部情况之下，操作容器物件，进而控制容器内装的物件，参考图一。STL很多地方均倚赖Iterator才能实现「效率」与「泛型」两个主要目标。使用Iterator后，演算法可以实作于各种物件、各种容器之上，只要该容器提供相对应的Iterator物件即可。
整个STL Iterator物件可以分为五类，如图四：各种Iterator物件简介如下：
Input
输入Iterator。负责从指定串列流读入资料，如同档案I/O般。
图四、Iterator的种类
Output
输出Iterator。负责输出物件于指定的串列
流，如同档案I/O。
以上两个Iterator只是单纯地负责物件输入与输出的工作，在整个Iterator阶层中显得较不重要。
Forward
如同C的指标，具有operator*()的功能，并限制Iterator进行的方向永远往前（就是提供operator++()的功能），不能跳格。为最有用的Iterator。
Bidirectional
同Forward Iterator，并提供operator--()的功能。STL循序式容器物件皆支援此Iterator，可以说Bidirectional Iterator可操作的容器物件最多。但是，就是因为支援的容器物件较多，所以执行速度比Random Access Iterator慢。
Random Access
最强大的Iterator，几乎与真实的指标一样，也提供operator[]()的功能，但支援的容器物件只有vector容器物件与deque容器物件而已，list容器物件只支援Bidirectional Iterator。
图三所以成金字塔型，因为支援最上层Random_Access_Iterator的容器物件与演算法物件最少；最下层的Input or Output Iterator，则几乎所有的STL容器演算法物件都支援，应用范围最为广大。
举个程式如下：
// test program for iterator
#include <iostream.h>
#include <deque.h>
void main() {
deque<int> q;
q.push_back(1);
q.push_back(2);
q.push_back(3);
q.push_back(4);
for(deque<int>::iterator i=q.begin();
i != q.end(); i++)
cout<<*i<<endl;
}
deque<int>容器在定义时给定其储存int型别的物件，存入一些int物件后，我们想要浏览之。宣告deque<int>::iterator i，表示i为deque定义的Iterator，想象i为一个指标，游走于deque容器之中，如要取得容器内int物件值时，使用*i便可。q.begin()、q.end()为传回deque容器的开始与结束的指标。
到此，体会一下演算法物件如何透过Iterator操作容器物件。您可想象这里的for回圈为演算法物件，只要输入q.begin()、q.end()便可完成将容器内之值输出的工作。以下，我们正式介绍演算法物件。
Algorithm与Function Object
STL提供的演算法均是最基本的演算，如排序、收寻演算法等。演算法操作Iterator物件，再透过Iterator物件操作容器物件，便达到演算法与容器物件无关化。
整个STL定义的演算法大致可分为七类，简介如下：
Non-mutating sequence algorithms
此类演算法只适用于循序式容器，并且执行完后不会改变容器内的值。如find()、count()函数等。
Mutating sequence algorithms
此类演算法只适用于循序式容器，并且执行完后会改变容器内的值。如copy()、swap()、fill()函数等。
Sorting and searching algorithms
就如同其名字一样，此类演算法执行排序与收寻的工作，只适用于循序式容器，因为关系式容器必定是排序好的，因此不需要此类函数。
Set operations
此类演算法适用于所有STL定义的容器物件，执行集合的运算，如set_union()、set_intersection()、set_difference()函数等。
Heap operations
此类演算法很像堆积资料结构中的运算，如push_heap()、pop_heap()函数等，与Adaptor容器物件很像，只是一个为资料结构定义其资料(Adaptor)；一个为资料结构定义其操作函数（如xx_heap()函数等）。
Numeric algorithms
此类演算法执行一般简单的数值计算功能，如accumulate()、partial_sum()函数等。
Other functions
不属于上面分类的其他演算法，如min()、max()函数等。
以下我们以排序与收寻类的演算法为例，说明STL中的演算法物件如何与Iterator和容器物件互相工作。
// test program for sort algorithm
#include <stdlib.h>
#include <iostream.h>
#include <algo.h>
#include <vector.h>
class INT {
public:
INT() {}
INT(int a) { d=a; }
INT(const INT& a) { d=a.d; }
INT& operator=(const INT& a) { d=a.d;return *this; }
int operator<(const INT& a) { return d<a.d; }
operator int() const { return d; }
int d; };
int my_comp(const INT& a,const INT& b) {
return a< b; }
void main() {
int i;
vector<INT> v;
cout<<"The original vector...\n";
for(i=0;i<10;i++) {
v.push_back(rand());
cout<<v[i]<<" ";
}
sort(v.begin(),v.end(),my_comp);
cout<<"\nAfter sorting ...\n";
for(i=0;i<10;i++)
cout<<v[i]<<" ";
cout<<endl;
}
宣告一个vector<INT>表示容器物件，10个元素值，而sort函数的原型如下：
tenplate <class RandomAccessIterator,class Compare> void sort(RandomAccessIterator first,RandomAccessIterator last,Compare comp);传进两个RandomAccessIterator类的Iterator后，与一个函数指标型别，sort函数自动帮您做排序，所用的演算法为qsort，平均排序时间为NlogN。
您可发现，STL所定义的演算法物件几乎都以template function出现，输入的参数则是Iterator类的物件，从函数原型上更可看出「泛型化程式库」的精神，演算法以抽象概念操作各种型态的物件。
不过，对于int my_comp(INT&,INT&)函数，在sort演算法物件中对应的宣告为template <class Compare comp>，sort内的定义则使用comp(*first,*last)来执行此函数的功能。可以想见，今天我们定义一个INT型态的物件，需要一个比较INT物件大小的函数（如本例中的my_comp），如果以后定义一个X型别的物件，也必须为其定义一个比较大小的函数，而这个函数竟然只是执行一道指令：
return a<b;
它依靠X物件对于操作元<的过荷定义，呼叫X物件的operator<(X& x)函数完成实际功能，从这牵扯到三个步骤：
1.X物件必须为operator<()函数做定义，
2.如此一来，my_comp函数才可以单纯地执行return a<b;就可，
3.在sort演算法物件内，才可以简单地呼叫comp(*first,*last)，知道谁大谁小。
上述三步骤，如果以执行效率来看，第一步骤与第三步骤由于可以采用C++的inline机制，做巨集展开，几乎不会花执行时间。可是第二步骤虽然最单纯，只有一道指令，但由于是以函数指标的方式传进sort的函数内，透过函数指标执行此函数，执行时间自然比较慢；而且，我们必须为每一个型别（包括C++内建型别与自行定义的类别）做这个「小函数」，尽管它的功能如此简单。
STL针对这个问题，再次应用了template的技巧，来帮忙演算法物件执行低阶的工作。如下：
// test program for Function Object
#include <stdio.h>
#include <stdlib.h>
#include <iostream.h>
#include <vector.h>
#include <algo.h>
#include <function.h>
class INT {
public:
INT() {}
INT(int a) { d=a; }
INT(const INT& a) { d=a.d; }
INT& operator=(const INT& a) { d=a.d;return *this; }
int operator<(const INT& a) { return d<a.d; }
operator int() const { return d; }
int d;
};
template<class T>
struct comp_less {
int operator()(const T& a,const T& b) { return a<b; }
};
void main() {
int i;
vector<INT> v;
cout<<"The original vector...\n";
for(i=0;i<10;i++) {
v.push_back(rand());
cout<<v[i]<<" ";
}
sort(v.begin(),v.end(),comp_less<INT>());
// sort(v.begin(),v.end(),less<INT>());
cout<<"\nAfter sorting ...\n";
for(i=0;i<10;i++)
cout<<v[i]<<" ";
cout<<endl;
}
我们宣告一个comp_less的类别（或称结构）来完成功能。在sort演算法物件中，使用comp(*first,*last)执行功能，如果comp是某个class的instance，则comp(*first,*last)便是呼叫comp物件里的operator()()操作元，因此将comp_less宣告成一个类别，里头只有一个operator()()的函数，执行上述小函数之功能，再利用inline机制，在执行时间，便一点也不会浪费执行效率；同时，也不必为每一个类别做comp_less小函数的撰写了。
而STL对于上述解决方式命名为Function物件，程式中sort指令下一行的//sort....便是同样问题STL Function物件的正式解决办法。
Adaptor与其他
接下来我们看看STL如何再次应用template达到Adaptor Container的功能。
// test program for stack container
#include <stdio.h>
#include <string.h>
#include <iostream.h>
#include <vector.h>
#include <stack.h>
class big {
public:
big() {} // required
big(char *cc,int ii,float ff) {
strcpy(c,cc);
i=ii; f=ff;
}
big(const big &a) {
strcpy(c,a.c);
i=a.i;f=a.f;
}
big& operator=(const big& a) {
strcpy(c,a.c);
i=a.i;f=a.f;
return *this;
}
char c[60]; int i; float f;
};
ostream& operator<<(ostream& a,big& b) {
return a<<b.i<<" "<<b.f<<" "<<b.c<<endl;
}
void main() {
stack< vector<big> > s;
s.push(big("me",1,1.11));
s.push(big("you",2,2.22));
s.push(big("he",3,3.33));
s.push(big("she",4,4.44));
while(!s.empty()) {
cout<<s.top();
s.pop();
}
}
平常传统OO式的思维方式，对于这种（模拟stack，利用变形的vector来改造），一定会使用继承的方式，让stack容器继承vector容器，然后修改一些操作元。然而号称物件导向化的C++的STL程式库却不采取这种作法，而以template class的方式让stack容器内包含vector<big>容器，这样做的好处当然还是为了那句老话「执行效率」，STL以执行效率出发，任何程式码，能在编译阶段就决定好的事情尽量在编译阶段做好。从STL我们可以学到：
C++工程师最好不要随便使用继承机制，如果可以的话，用template机制去代替。而template机制使用情形有两种，
1.template class：使用在改造STL现有的容器物件上，或者是一些想要继承的资料结构。
2.template function：使用在帮助加强STL现有的演算法物件上，或者是一些想要继承的物件行为。
当然，如果您想要改造或加强的是一整个物件（包括资料与函数），非单纯的资料结构或演算法，最好还是使用继承机制。
乍看之下，上述原则似乎没有问题，然而template机制果真这么好吗？
在此我们提出写作STL程式重要的遵守规则：
在使用每个容器物件供不同演算法物件操作的时候，必须非常小心该演算法物件是否要求自己定的类别T，必须提供某些操作元函式，供其使用。
这是一个相当不协调的限制，对于一个处处讲究写作优美的C++语言而言。C++创始人Bjarne，针对这个问题，想过一些解决方式，不过都没有定案，等待日后的C++标准会议讨论。Bjarne的基本观念，便是将这些自订型别必须提供的操作元写在template<class T>的容器物件类别的定义之中。大致如下：
template<class T>
constraints {
T& operator=(const T&);
int operator==(const T&,const T&);
}
class Conatiner {
......
};
所以，在标准尚未定案之前，建议您写自订型别class T，多定义预设建构元、拷贝建构元，设值操作元，与解构元等，才能确保您所使用的演算法物件可以正确地透过Iterator物件操作容器物件。如上面程式中，我们为big类别所做的事一样。如果基本容器类别换成list容器，则甚是要定义operator==()与operator<()操作元才行。
到此，我们大致介绍了整个STL的主要特色，STL的各部份的详细细节，可以参考下面的资料：
参考资料
[Mus95]Musser, David R. and Saini, Atul.(1995) STL Tutorial and Reference Guide. Addison Wesley.
[Nel95]Nelson, Mark. (1995) C++ Programmer‘s Guide to the Standard Template Library. IDG Books.■
