1.什么是STL？
标准模板库(Standard Template Library)。虚函数和模板（包括函数模板和类模板）是C++语言的两个重要特性，MFC利用大量地运用了虚函数，而STL则是利用模板实现的。
2.为什么要使用类属算法？
软件模块的可重用性考虑，使得不必为每一种数据类型编写算法，在抽象数据类型上定义算法，当算法作用于具体数据类型时，只要用特定的数据类型具体化便可。
例如：
template <typename T>
T max(T x,T y)
{
if(x<y) ruturn y;
else return x;
}
调用如下：
int u=3,v=4;
double d=4.7;
cout<<max(u,v)<<endl;
cout<<max(d,9.3)<<endl;
函数模板在使用时不必告诉编译器所使用的实际类型，编译器可以从参数中直接判断出来，如上例。
注意：编译器不会进行自动类型转换。所以如下调用时不正确的：
cout<<max(u,d)<<endl; //incorrect
这里使用的是内置数据类型，也可以传递用户定义数据类型，但必须定义<比较运算符 。
另一方面，STL使用的类属算法，与容器（STL的重要基本概念之一，通俗地理解，就是封装过的数组，队列，集合等
放置数据的一种结构，从字面意思即可理解，也可以理解为一种模板类）是相对独立的，即一种类属算法可以应用于多种容器之上，甚至有些类属算法可以应用于所
有的容器。OOP编程一般把作用于类的操作，即使算法实现为特定类的成员函数，使得数据和算法紧密的联系在一起，但是STL把各种容器的公共操作提取出
来，作为一个独立的组件（算法集合），而把某些特殊的算法实现为容器的成员函数（出于容器的特殊性考虑，有些类属算法虽然可以实现同样的功能，但适当考虑
某些容器的特殊性之后，可以有不同的实现方式，使得这种操作作用于特殊的类时效率更高，于是一部分某些容器也提供实现相同功能的成员函数），例如对于类属
算法find，其时间复杂度是线性的，而有序关联容器（set,multiset,map,multiset）就提供了成员函数，其实见复杂度为log
(N)。
总的来说，使用类属算法，提高了通用性，降低了程序员工作的复杂度，可以通过标准的统一接口来编程，也易于维护。
3.类属算法如何工作？
容器(container)<——>迭代器(iterator)<——>类属算法(algorithm)
迭代器是类似于指针的一种STL组件，在STL中，迭代器的用法跟指针类似，目前就暂且把它理解为指针。
可以这样理解，类属算法不是对容器直接操作，而是通过对指向容器某个位置的迭代器（类似指针）来实现对该地址的数据的操作。
4.基本概念
类模板
template<typename T1,typename T2>
class pair{
public:
T1 first;
T2 second;
pair():first(T1()),sencond(T2()){} //默认构造函数
pair(const T1& x,const T2&
y):first(x),second(y){} //自定义构造函数
} ;
实际调用时:
pair<int,char> pair1(13,'a');
pair<bool,double> pair2(true,0.1);
函数模板：上面的max（）函数就是一个简单的函数模板。
成员函数模板
不管类属否使用模板定义，其成员函数都可以有模板参数，例如：
template <typename T>
class vector{
//.....
public:
template <typename InputIterator>
void insert(iterator position,InputIterator first,InputIterator last);
//.....
};
容器
在STL中，容器指存储其他对象的集合的对象，主要有两种类型的STL容器：序列容器和顺序关联容器。
序列容器
序列容器将一组具有相同类型的对象以严格线性的形式组织在一起。包括如下几种：
vector<T> 提供对变长序列的随机访问，对序列末尾的插入和删除操作时间是分摊常量的，对序列开头的插入和删除是线性的。可以理解为封装后的数组。
depue<T>提供对变长序列的随机访问，对序列开头和末尾的插入和删除操作是分摊常量的。存储空间是连续的（这一点尚未在书上说明，只是个人推测）。
list<T>提供对变长序列的线性时间访问，但是对序列中任意位置的插入和删除操作均为常量时间的。可以理解为封装后的链表。
对向量使用STL类属算法reverse:
#include<iostream>
#include<vector>
#include<cassert>
#include<string>
#include<algorithm> //for reverse
using namespace std;
template<typename Container>
Container make(const char s[])
{
return Container(&s[0],&s[strlen(s)]);
}
int main()
{
cout<<"Using reverse algorithm with a vector"<<endl;
string string1="mark twain";
vector<char> vector1(string1.begin(),string1.end()); //begin()和end()是访问器，返回迭代器
reverse(vector1.begin(),vector1.end());
assert(vector1==make< vector<char> >("niawt kram"));
cout<<" --OK."<<endl;
return 0;
}
有序关联容器
有序关联容器具有从基于键的集合种快速提取对象的能力。集合的大小可以在运行时改变。STL中有4种类型的有序关联容器：
set<Key>支持唯一的键（每个键值只能有一个）并提供对见本身的快速检索。
multiset<Key>支持客重复的键（同一个键值可以有多个副本）并提供对键本身的快速检索。
map<Key,T>支持唯一的（Key类型的）键并提供对另一个基于键的类型T的快速检索 。
multimap<Key,T>支持可重复的（Key类型的）键并提供对另一个基于键的类型T的快速检索。
演示STL映射（map）:
#include<iostream>
#include<map>
#include<string>
using namespace std;
int main()
{
map<string,long> directory;
directory["Bogart"]=123;
directory["Bacall"]=456;
directory["Cagney"]=789;
string name;
while(cin>>name)
{
if(directory.find(name)!=directory.end())
cout<<"The phone number for "<<name
<<" is "<<directory[name]<<"\n";
else
cout<<"Sorry,no listing for "<<name<<endl;
}
return 0;
}
上例中，find()为所有有序关联容器的成员函数，查找时间复杂度为logN，该函数首先检查name是否为保存在directory中的一个键，假如directory确实存在以name作为键值的数据项，则其返回该数据项的迭代器，否则find函数返回“序列末尾最后一个元素之后的一个位置”迭代器，该迭代器与end成员函数返回的迭代器相同。
STL容器和其他C++容器类库中的容器的一个重要区别：STL容易并没有为其所包含的容器提供过多的操作（成员函数），相反，STL提供的是类属算法。
类属算法
最简单的类属算法：find和merge
类属查找算法find
用表演示find类属算法
#include<iostream>
#include<cassert>
#include<list>
#include<algorithm>
using namespace std;
template<typename Container>
Container make(const char s[])
{
return Container(&s[0],&s[strlen(s)]);
}
int main()
{
list<char> list1=make< list<char> >("C++ is a better C.");
list<char>::iterator
where=find(list1.begin(),list1.end(),'e');
list<char>::iterator next=where;
++next;
assert(*where=='e' && *next=='t');
cout<<" ---OK."<<endl;
return 0;
}
注意：与表对应的迭代器不支持表达式*(where+1)中的+运算符，而向量(vector)和双端队列支持这样的表达式。但所有的STL迭代器都要求支持++。
类属合并算法merge
merge算法的功能是将两个序列的元素合并到一个序列中，调用形式为
merge(first1,last1,first2,last2,result);
则包含如下假定：
*迭代器first1和last1表示一个输入序列的起始和终止位置，其元素类型为T;
*迭代器first2和last2表示另一个输入序列的起始和终止位置，其元素类型也为T;
*按照类型T上的<运算符的定义，两个输入序列均为升序排列。
*result表示合并后序列存放的起始位置。
merge函数返回的结果是合并两个序列后的一个升序序列。
示例：merge类属算法合并数组和向量，把结果保存在表中
#include<iostream>
#include<string>
#include<cassert>
#include<vector>
#include<list>
#include<algorithm>
using namespace std;
template<typename Container>
Container make(const char s[])
{
return Container(&s[0],&s[strlen(s)]);
}
int main()
{
char s[]="acegikm";
vector<char> vector1(
make< vector<char> >("bdfhjlnopqrstuvwxyz"));
list<char> list1(26,'x'); //将list1初始化为26个'x'
//merge first 5 letters in array s with first 10 in
//vector1,putting result in list1
merge(&s[0],&s[5],vector1.begin(),vector1.begin()+10,list1.begin());
assert(list1==
make< list<char> >("abcdefghijlnopqxxxxxxxxxxx"));
cout<<" --OK."<<endl;
return 0;
}
疑问：vc6.0下如果把上述程序中的vector换作deque，则无法通过编译，不知道是否是编译器不支持
deque<char> deque1(
make< deque<char> >("bdfhjlnopqrstuvwxyz"));
这种初始化方式？
迭代器
普通的C++指针就是一种迭代器，但除了指针以外，还有其他种类的迭代器。STL要求这些迭代器具有和指针类似的特性，既可以对迭代器做++和*等操作，而且这些操作与定义在指针上的相同操作具有相同的功能。
各个迭代器（不包括分配器）之间的层次关系及其要求定义的运算：
1. == != *
2. ++
3. --
4.+= -= + - < > <= >=
前向（输入，输出）：1，2
双向：1，2，3
随机：所有
前向也是双向迭代器，双向也是随机迭代器。
对于输入迭代器，只能读取数据，不能写入；对于输出迭代器，只能写入数据，不能读取。
演示类属算法accumulate,该算法在初始值基础上累加指定容器区间的值。
#include<iostream>
#include<vector>
#include<cassert>
#include<numeric> //for accumulate
using namespace std;
int main()
{
int x[5]={2,3,5,7,11};
vector<int> vector1(&x[0],&x[5]);
int sum=accumulate(vector1.begin(),vector1.end(),0); //最后一个参数是累加的初始值
assert(sum==28);
cout<<"--OK."<<endl;
return 0;
}
向量和双端队列迭代器是随机迭代器，而表迭代器仅仅是双向的，并非随机，固有些要求随机迭代器的类属算法不能用于表容器，例如sort算法，一次表容器有排序成员函数。
函数对象
先看一例。STL提供了accumulate函数的一个更为通用的版本。其定义如下：
template <typename InputIterator,typename T,typename BinaryOperation>
T accumulate(InputIterator first,InputIterator last,
T init,BinaryOperation binary_op)
{
while (first!=last)
{
init=binary_op(init,*first);
++first;
}
return init;
}
上面的定义没有定义+运算符，而是引入了另一个参数binary_op，作为定义在序列质类型上的二元操作符。
示例：使用增强版的accumulate计算连乘积
#include<iostream>
#include<vector>
#include<cassert>
#include<numeric> //for accumulate
using namespace std;
int mult(int x,int y){return x*y;}
int main()
{
int x[5]={2,3,5,7,11};
vector<int> vector1(&x[0],&x[5]);
int product=
accumulate(vector1.begin(),vector1.end(),1,mult);
assert(product==2310);
cout<<"--OK."<<endl;
return 0;
}
这里传递给accumulate函数的是一个普通函数的mult,实际上传递的是该函数的地址。
函数对象是一种实体，可以不带参数，也可以带有一个以上的参数，不能够从中获得一个值或者改变程序的状态。除了上面所示的普通函数，另一类函数对象是类或者结构的对象，且在其定义中重载了()运算符，而且这种方式在STL中更为常用。
请看下例：
#include<iostream>
#include<vector>
#include<cassert>
#include<numeric> //for accumulate
using namespace std;
class multiply
{
public:
int operator()(int x,int y) const{return x*y;}
};
int main()
{
int x[5]={2,3,5,7,11};
vector<int> vector1(&x[0],&x[5]);
int product=
accumulate(vector1.begin(),vector1.end(),1,multiply());
assert(product==2310);
cout<<"--OK."<<endl;
return 0;
}
通过在类multiply中定义运算符operator()，就定义了一种可以作为函数参数的对象，可以像使用函数一样使用这种对象。这里传递给accumulate的对象是通过调用multiply类的默认构造函数multiply()获得的。
使用以类的形式定义的函数对象比普通函数优越，它可以携带更多额外的信息（可以静态数据成员的形式），以后再举例子。
适配器
用来改变其他组件接口的组件称为适配器。包括迭代器适配器、容器适配器和函数适配器。
迭代器适配器
reverse_iterator将某种类型的迭代器变成一种新的迭代器，但保持其功能不变，而仅将其便利的顺序倒转过来。
容器适配器
栈适配器可以将序列容器变换到后进先出的栈接口中。
队列适配器可以将序列容器变换到先进先出的队列中。
优先级队列可以将序列容器变换到优先级队列中，由一个比较参数来控制对其元素的访问顺序。
函数适配器
取反器(negator)用于对判定函数对象（判定函数对象指那些返回值为bool类型的函数对象）的结果进行取反。
邦定器(binder)通过将二元函数的一个参数与某个特定的值邦定，可以将二元函数变成一元函数。
函数指针适配器从函数指针得到函数对象，与使用标准函数相比，这将使编译后的代码具有更大的灵活性。
下面一例使用反向迭代器。
#include<iostream>
#include<vector>
#include<cassert>
#include<numeric> //for accumulate
using namespace std;
int main()
{
float small=(float)1.0/(1<<26);
float x[5]={1.0,3*small,2*small,small,small};
vector<float> vector1(&x[0],&x[5]);
cout<<"Values to be added: "<<endl;
vector<float>::iterator i;
for(i=vector1.begin(); i != vector1.end(); ++i)
cout<<*i<<endl;
cout<<endl;
float sum=accumulate(vector1.begin(),vector1.end(),(float)0.0);
cout<<"Sum accumulated from left = "<<sum<<endl;
float sum1=accumulate(vector1.rbegin(),vector1.rend(),(float)0.0);
cout<<"sum accumulated from right = "<<(double)sum1<<endl;
return 0;
}
vector<float>::reverse_iterator类型是用迭代器适配器定义的。也可以在程序中直接使用适配器：
reverse_iterator<vector<float>::iterator> start(vector1.end()),finish(vector1.begin());
float sum1=accumulate(start,finish,(float)0.0);
reverse_iterator类型也提供了++和--运算符，但互换了这两个运算符的含义。上例中的vector1.rbegin()和vector1.rend()成员函数返回的即是reverse_iterator类型。
分配器
每种STL容器都是用了一种分配器类，用来封装程序所用的内存分配模式的信息。不同的内存分配模式采用不同的方法从
操作系统中检索内存。分配器类可以封装许多方面的信息，包括指针、常量指针、引用、常量引用、对象大小、不同类型指针之间的差别、分配函数与释放函数、以
及一些函数的信息。分配器上的所有操作都具有分摊常量的运行时间。
由于内存分配模式方面的信息可以封装在分配器中，所以提供不同的分配器，就可以使STL容易能够用于不同的内存分配模式。
对多数程序员来说，STL提供的默认分配器类已经可以满足编程的需要了。