第十一章 标准模板库（ STL）
库 （ library） 是一系列程序组件的集合,它们可以在不同的程序中重复使用 。 库函数设计的第一位的要求就是通用性,为程序员提供大量实用的库是 C++的又一特色 。
标准模板库 （ Standard Template Library）
是 ANSI/ISO C++最有特色,最实用的部分之一 。
STL 包含了容器类 （ container ）,迭代子
（ iterator） 和算法 （ algorithm） 三个部分 。
第十一章 标准模板库（ STL）
11.1 标准模板库简介
11.3 顺序容器
11.2 迭代子类
11.5 容器适配器
11.7 VC++中的 STL
11.6 泛型算法与函数对象
11.4 关联容器
11.1 标准模板库简介
STL提供了一个标准化的模板化的对象容器库,包含多种数据结构及其算法,可以节省大量的时间和精力,而且程序是高质量的 。
容器类是管理序列的类，是容纳一组对象或对象集的对象，甚至可以包含混合的对象，包含一组不同类型的对象，称为异类容器
（ heterogeneous container），一组相同类型的对象，称为同类容器 (homogenous container)。通过由容器类提供的成员函数，可以实现诸如向序列中插入元素，删除元素，查找元素等操作，
这些成员函数通过返回迭代子来指定元素在序列中的位置。迭代子是面向对象版本的指针，它提供了访问容器或序列中每个对象的方法。这样就可以把算法用于容器所管理的序列。
11.1 标准模板库简介容器分为三大类：
顺序容器 （ sequence container or sequential container）
关联容器 （ associative container）
容器适配器 （ container adopter）
顺 序 容 器 和 关 联 容 器 称 为 第 一 类 容 器 （ first-class
container） 。 另外有四种容器称为近容器 （ near container）,
C语言风格数组,字符串 string,操作 1/0标志值的 bitset和进行高速数学矢量运算的 valarray。
11.1 标准模板库简介标准库容器类 说明顺序容器
vector（ 参量 ）
deque（ 双端队列 ）
list（ 列表 ）
从后面快速插入与删除,直接访问任何元素从前面或后面快速插入与删除,直接访问任何元素从任何地方快速插入与删除,双链表关联容器
set（ 集合 ）
multiset（ 多重集合 ）
map（ 映射 ）
multimap（ 多重映射 ）
快速查找,不允许重复值快速查找,允许重复值一对一映射,基于关键字快速查找,不允许重复值一对多映射,基于关键字快速查找,允许重复值容器适配器
stack（ 栈 ）
queue（ 队列 ）
priority_queue（ 优先级队列 ）
后进先出 （ LIFO）
先进先出 （ FIFO）
最高优先级元素总是第一个出列表 11.1 标准库容器类
11.1 标准模板库简介
STL也使容器提供接口 。 许多基本操作是所有容器都适用的,而有些操作则适用于类似容器的子集 。 可以用新的类来扩展 STL。 参见表
11.2。 这些函数和运算符可通称为容器的接口 。
各容器具体接口参见附录 C。
使用 STL容器或容器适配器，要包含定义该容器模板类头文件。参见表 11.3。 这些 头文件的内容都在 std名字空间域（ namespace std）
中,程序中必须加以说明 。
11.1 标准模板库简介在有关数组、链表和二叉树等线性表和非线性表的讨论中，
若要访问其中一个元素（结点），我们可以用下标或者指针去访问，而下标实际上也是一种指针即地址，访问时取地址的方式还有很多，一系列的访问方法都可以抽象为迭代子（ iterator）。访问方法最终要归于内存地址的获得，所以说 迭代子是面向对象版本的指针 。
迭代子与指针有许多相同之处，但 迭代子保存所操作的特定容器需要的状态信息,从而实现与每种容器类型相适应的迭代子。
而且有些迭代子操作在所有容器中是一致的，如 ++运算符总是返回容器下一个元素的迭代子，间接引用符,*”，总是表示迭代子指向的容器元素。
迭代子用来将 STL的各部分结合在一起。从本质上说,STL提供的所有算法都是模板，我们可以通过使用自己指定的迭代子来对这些模板实例化。迭代子可以包括指针，但又不仅是一个指针。
11.1 标准模板库简介
STL最大的优点是提供能在各种容器中通用的算法,例如插入,
删除,查找,排序等等 。
STL提供 70种左右的标准算法。算法只是间接通过迭代子操作容器元素。
算法通常返回迭代子。一个算法通常可用于多个不同的容器，
所以称为泛型算法（ generic algorithm）。
算法分为：
１,修改容器的算法，即变化序列算法（ mutating-sequence
algorithm），如 copy(),remove(),replace(),swap()等。
２．不修改容器的算法，即非变化序列算法（ non-mutating-
sequence algorithm），如 count(),find()等。
３．数字型算法。
11.2 迭代子类
C++标准库中有五种预定义迭代子，其功能最强最灵活的是随机访问迭代子。
标准库定义迭代子类型 说明输入 （ InputIterator）
输出 （ OutputIterator）
正向 （ ForwardIterator）
双向 （ BidirectionalIterator）
随机访问
（ RandomAccessIterator）
从容器中读取元素 。 输入迭代子只能一次一个元素地向前移动
（ 即从容器开头到容器末尾 ） 。 要重读必须从头开始 。
向容器写入元素 。 输出迭代子只能一次一个元素地向前移动 。
输出迭代子要重写,必须从头开始 。
组合输入迭代子和输出迭代子的功能,并保留在容器中的位置
（ 作为状态信息 ）,所以重新读写不必从头开始 。
组合正向迭代子功能与逆向移动功能 （ 即从容器序列末尾到容器序列开头 ） 。
组合双向迭代子的功能,并能直接访问容器中的任意元素,即可向前或向后跳过任意个元素 。
表 11.4 迭代子类别
11.2 迭代子类标准库定义迭代子的层次结构,按这个层次,从上到下,功能越来越强 。 但不是继承 ！
input output
forward
bidirectional
random access
图 11.1 迭代子层次
11.2 迭代子类只有第一类容器能用迭代子遍历。表 11.5给出各种不同容器所支持的迭代子类别。标准库定义的各种迭代子可进行的操作参见表 11.6，
容器 支持的迭代子类别顺序容器
vector
deque
list
随机访问 （ random access）
随机访问 （ random access）
双向 （ bidirection）
关联容器
set
multiset
map
multimap
双向 （ bidirection）
双向 （ bidirection）
双向 （ bidirection）
双向 （ bidirection）
容器适配器
stack
queue
priority_queue
不支持迭代子不支持迭代子不支持迭代子
11.2 迭代子类下面结合 find()算法讨论迭代子与泛型算法的关系 。 find()定义如下：
template<typename InputIterator,typename T >
InputIterator find(InputIterator first,InputIterator
last,count T value ){
for(;first!=last;++first) if(value==*first) return first;
return last
}
可见,泛型算法不直接访问容器的元素,与容器无关 。 元素的全部访问和遍历都通过迭代子实现 。 并不需要预知容器类型 。 find()
算法也支持系统内置的数组类型：
11.2 迭代子类
【 例 11.1】 寻找数组元素 。
#include<algorithm>
#include<iostream>
using namespace std;
void main(){
int search_value,ia[9]={47,29,37,23,11,7,5,31,41};
cout<<"请输入需搜索的数,"<<endl;
cin>>search_value;
int* presult=find(&ia[0],&ia[9],search_value);
cout<<"数值 "<<search_value<<(presult==&ia[9]?"不存在 ":"存在 ")<<endl;
}
这里 a[9]数组元素并不存在，但内存地址单元存在。
11.2 迭代子类
【 例 11.2】 寻找 vector容器元素 。
#include<algorithm>
#include<vector>
#include<iostream>
using namespace std;
void main(){
int search_value,ia[9]={47,29,37,23,11,7,5,31,41};
vector<int> vec(ia,ia+9); //数据填入 vector
cout<<"请输入需搜索的数,"<<endl;
cin>>search_value;
vector<int>::iterator presult; //定义迭代子
presult=find(vec.begin(),vec.end(),search_value);
cout<<"数值 "<<search_value<<(presult==vec.end()?"不存在
":"存在 ")<<endl; }
11.2 迭代子类在 <iterator>头文件中还定义了一些专用迭代子：
反转迭代子 (reverse iterator)；
插入型迭代子 (insertion iterator)；
流迭代子 (stream iterator)；
流缓冲迭代子 (stream buffer iterator)；
11.2 迭代子类
１．反转型迭代子（ reverse iterator）把一切都颠倒过来
vector<int> veco;
vector<int>::reverse_iterator r_iter;
for(r_iter=veco.rbegin();//将 r_iter指向到末元素
r_iter!=veco.rend();//不等于首元素的前导
r_iter++){//实际是上是递减
//循环体
}
如果要把升序的序列改为降序的序列，只要使用反转迭代子就可以了。反转迭代子定义为随机迭代子。
11.2 迭代子类
２,插入型迭代子 （ insertion iterator）,可以用输出迭代子来产生一个元素序列 。
可以添加元素而不必重写 。 有三种插入迭代子：
back_insert_iterator<Type>是输出迭代子,用来将产生的元素添加到类型为
Type的容器对象的末端 。 就象在一个字符串末尾加一个串 （ strcat()） 。
front_insert_iterator<Type>是输出迭代子,用来将产生的元素添加到容器的前端,就是,产生出来的元素以逆序方式结束于被控序列前端 。
insert_iterator<Type,Iter>也是输出迭代子,它用来将产生的元素插入到一个由迭代子 （ 第二个参数 Iter） 指定的元素的前面 。 与之对应的也有三个相关的适配器函数,它们返回特定的插入迭代子：
back_inserter(Type&)：它使用容器的 push_back()插入操作代替赋值操作符,
实参是容器自己 。 返回一个 back_inserter迭代子 。
front_insertor(Type&)：使用容器的 push_front()插入操作代替赋值操作符,
实参也是容器本身 。 返回一个 front_inserter迭代子 。
inserter（ Type&,Iter）：用容器的 insert()插入操作符代替赋值操作符。
inserter()要求两个实参：容器本身和它的一个迭代子指示起始插入的位置。标记起始插入位置的迭代子并不保持不变，而是随每个被插入的元素而递增，这样每个元素就能顺序被插入。
11.2 迭代子类
３,流 迭 代 子 有 输 入 流 迭 代 子 （ istream_iterator ） 和 输 出 流 迭 代 子
（ ostream_iterator） 。 在 <iostream.h>,<fstream.h>等头文件中定义了流类库,在 STL中为输入 /输出流 iostream提供了迭代子,它们可以与标准库容器类型和泛型算法结合起来工作 。 使用这两个迭代子必须包含头文件 <iterator>。
输入流迭代子 （ istream_iterator） 类支持在 istream及其派生类 （ 如 ifstream）
上的迭代子操作 。 istream_iterator声明方式为：
istream_iterator<Type>迭代子标识符 (istream&);
//Type为已定义了输入操作的类型,实参可以是任意公有派生的 istream的子类型的对象输出流也有对应的 ostream_iterator类支持,其声明方式为：
ostream_iterator<Type>迭代子标识符 (ostream&)//实参同样可以是公有派生子类型对象
ostream_iterator<Type>迭代子标识符 (ostream&,char*)//第二参数为 C风格字符串
11.2 迭代子类下面结合 copy算法和 sort算法来介绍 istream iterator和 ostream_iterator。
【 例 11.3】 用 istream iterator从标准输入读入一个整数集到 vector中 。
#include<iostream>
#include<iterator>
#include<algorithm>
#include<vector>
#include<functional>
using namespace std;
void main(){ istream_iterator<int> input(cin);
istream_iterator<int> end_of_stream;
vector<int> vec;
copy(input,end_of_stream,inserter(vec,vec.begin()));//输入 ^Z结束流
sort(vec.begin(),vec.end(),greater<int>());//升序排列
ostream_iterator<int>output(cout," ");
unique_copy(vec.begin(),vec.end(),output);
}
11.2 迭代子类输入：
41 3 9 5 7 23 17 19 13 11 37 31 23 29 41 39 ^Z
泛型算法 copy()定义如下：
template<typename InputIterator,typename InputIterator,typename OutputInterator>OutputIterator
copy(InputIterator first,InputIterator last,OutputInterator x){
for(;first!=last;++x,++first) *x=*first
return (x);
}
11.2 迭代子类
end_of_stream是指示文件 （ 流 ） 结束位置,它使用了缺省的构造函数,输入时必须在最后一个数字后加分隔符,然后加 Ctrl-Z结束 。 拷贝算法要求我们提供一对
iterator来指示文件 （ 流 ） 内部的开始和结束位置 。 我们使用由 istream对象初始化的
istream_iterator提供开始位置,本例中为 input。
本例中插入迭代子 inserter作为 copy的第三个参数,它是输出型的,把流插入 vec。
泛 型 算 法 sort() 为 升 序 排 序 算 法,声 明 如 下 template<typename
RandomAccessInterator,typename Pr>
void sort(RandomAccessIterator first,RandomAccessInterator last,Pr p);
第三参数为排序方式,greater<int>()是预定义的,大于,函数对象,排序时用它来比较数值大小 。 缺省时为,小于,,即升序排序 。
例中用输出迭代子 output来输出,泛型算法 unique_copy（ ）,复制一个序列,
并删除序列中所有重复元素 。 本例中,拷贝到 output迭代子,即用空格分隔各整数的标准输出 。 输出为：
41 39 37 31 29 23 19 17 13 11 9 7 5 3
11.2 迭代子类
４．流缓冲迭代子。这是 STL后添加的一对迭代子，用来直接从一个流缓冲区（ streambuffer）中插入或提取某种类型（通常为 char）的元素。
11.3 顺序容器
C++标准模板库提供三种顺序容器,vector,list和 deque。
vector类和 deque类是以数组为基础的,list类是以双向链表为基础的。
矢量 （ vector） 类提供了具有连续内存地址的数据结构 。 通过下标运算符 [ ]直接有效地访问矢量的任何元素 。 与数组不同,vector的内存用尽时,vector自动分配更大的连续内存区,将原先的元素复制到新的内存区,并释放旧的内存区 。 这是矢量 （ vector） 类的优点 。
在这里内存分配是由分配子 （ allocator） 完成 。
矢量可以用来实现队列,堆栈,列表和其他更复杂的结构 。
vector支持随机访问迭代子,vector的迭代子通常实现为 vector
元素的指针。所谓选择容器类，实际上很大部分是在选择所支持的迭代子。
11.3 顺序容器使用向量容器的声明如下：
#include<vector>
……
vector<int> vi;//定义存放整形序列的向量容器对象 vi,长度为 0的空 vector
vector<float> vf; //存放实型序列的向量容器
vector<char> vch; //存放字符序列的向量容器
vector<char *> vstr; //存放字符串 （ 字符指针 ） 序列的向量容器使用方法是典型的函数模板的使用方法 。 调用缺省的构造函数,创建长度为 0的向量 。 矢量容器有多种构造函数 。 包括构造一个有 n个元素的矢量,每个元素都是由元素缺省的构造函数所构造出来的,还可以为每个元素用同一个对象来赋初值 。 还包括拷贝构造函数,可以由一个已有的矢量容器对象来初始化新容器各元素的构造函数 。 这些构造函数还可以显式给出分配子 (allocator)对象 。
11.3 顺序容器对矢量的操作包含了在顺序表中所列出的操作，而且更多。
１．列表（ list）是由双向链表（ doubly linked list）组成的。我们也已经在有关链表的一节中介绍过了，它有两个指针域，可以向前也可以向后进行访问，但不能随机访问，
即支持的迭代子类型为双向迭代子。使用起来很方便，与我们在 § 7.2节中定义的双链表类模板相似，但通用性更好，
使用更方便。列表的定义在头文件 <list>中。
２．双端队列（ deque）（ double-ended queue）类。
双端队列允许在队列的两端进行操作。 支持随机访问迭代子 。 也支持通过使用下标操作符,[ ]”进行访问。
11.3 顺序容器当要增加双端队列的存储空间时,可以在内存块中 deque两端进行分配,通常保存为这些块的指针数组 。 双端队列 利用不连续内存空间,它的 迭代子比 vector的迭代子更加智能化 。 对双端队列分配存储块后,往往要等删除双端队列时才释放,它 比重复分配 （ 释放和再分配 ） 更有效,
但也更浪费内存 。
使用双端队列,必须包含头文件 <deque>。
11.4 关联容器查找和排序总是 对 关键字 进行的，函数模板和类模板中只介绍了 通用类型（亦称泛型类型）,并没有涉及关键字。关联容器（ associative container）能通过关键字（ search key）直接访问 (存储和读取元素 )。四个关联容器为：集合（ set），多重集合（ multiset），映射（ map），多重映射（ multimap）。集合和多重集合类提供了控制数值集合的操作，其中数值是关键字，
映射和多重映射类提供了操作与关键字相关联的映射值
（ mapped value）的方法。
多重集合关联容器用于快速存储和读取关键字。
11.4 关联容器
multiset和 set通常实现为 红黑二叉排序树。
常用的二叉排序树一般结点有四个域：一个数据域，三个指针域（左孩子指针，右孩子指针和双亲指针）。双亲指针使直接回访成为可能，它使二叉排序树删除节点的算法变的简单。在生成二叉排序树时，当输入数据为已排好序时，会形成高度不平衡的只有半边的斜杠形的树，即退化为链表，二叉排序树只有形成平衡的树，也就是接近完全二叉数或满二叉树的形状才能达到对半查找的效果。红黑二叉排序树是实现平衡二叉排序树的方法之一。
11.4 关联容器
【 例 11.4】 整型多重集合关联容器类的演示 。 类模板声明,
template<typename Key,typename Pred = less<Key>,typename A = allocator<Key>
> class multiset;//模板参数表中的非类型参数同样可有缺省值
#include<iostream>
#include<set> //包含集合头文件
#include<algorithm> //包含算法头文件
using namespace std; //C++标准库名字空间域
typedef multiset<int> INTMS; //特例取名 INTMS,整型多重集合按升序排列
11.4 关联容器
void main(){const int size=16;
int a[size]={17,11,29,89,73,53,61,37,41,29,3,47,31,59,5,2};
INTMS intMultiset(a,a+size); ostream_iterator<int>
output(cout," ");
cout<<"这里原来有 "<<intMultiset.count(17)<<"个数值 17"<<endl;
intMultiset.insert(17); //插入一个重复的数 17
cout<<"输入后这里有 "<<intMultiset.count(17)<<"个数值 17"<<endl;
INTMS::const_iterator result; result=intMultiset.find(18);
if(result==intMultiset.end()) cout<<"没找到值 18"<<endl;
else cout<<"找到值 18"<<endl;
cout<<"intMultiset容器中有 "<<endl;
copy(intMultiset.begin(),intMultiset.end(),output); cout<<endl;
}
11.4 关联容器请注意 multiset容器中自动作了升序排列 。 如需要,
可以在 VC++帮助中 （ MSDN） 由关键字 multiset查找有关迭代子,成员函数的定义和用法 。
多重映射和映射关联容器类用于快速存储和读取关键字与相关值（关键字 /数值对,key/value pair）。
如果保存学生的简明资料，要求按学号排序，使用映射关联容器（因为不会重号）是最合适的。如用姓名排序，
因姓名可能重复，使用多重映射更为合适。使用时要用头文件 <set>。
11.5 容器适配器
STL提供了三个容器适配器（ container adapter）：栈（ stack），
队列（ queue）和优先级队。栈是标准的栈，使用时要用头文件 <stack>。
队也是标准的，使用时要用头文件 <queue>。所谓适配器并不独立，它依附在一个顺序容器上。如要声明一个用矢量实现的字符型堆栈，可使用如下声明：
stack<vector<char>> sk;
然后它就可以象顺序容器一样使用。但是它没有自己的构造和析构函数，它使用其实现类（如 vector）的构造和析构函数。就象一个仪器加了一个适配器增加了某些功能一样。队列（ queue）缺省用 deque为基础，
栈（ stack）可用 vector或 deque为基础。
优先级队列（ priority_queue）适配器实现优先级队列。元素插入是自动按优先级顺序插入，使最高优先级元素首先从优先级队列中取出。优先级队列（ priority_queue）的每个常用操作都实现为内联函数，调用基础容器的相应函数时，可避免二次函数调用的开销。常用矢量为基础容器。
缺省情况下 priority_queue实现时用 vector为基础数据结构。
11.5 容器适配器
【 例 11.5】 优先级队列类演示,头文件用 <queue>,优先级用数表示,数值越大优先级越高 。
#include<iostream>
#include<queue>
#include<functional>
using namespace std;
11.5 容器适配器
void main(){
priority_queue<int> prioque;
//实例化存放 int值的优先级队列,并用 deque作为基础数据结构
prioque.push(7);//压入优先级队列
prioque.push(12);
prioque.push(9);
prioque.push(18);
cout<<"从优先级队列中弹出 "<<endl;
while(!prioque.empty()){
cout<<prioque.top()<<'\t';//取最高优先级数据
prioque.pop();//弹出最高优先级数据
}
cout<<endl;
}
11.6 泛型算法与函数对象算法表现为一系列的函数模板，它们完整定义在 STL头文件中。一般这些函数模板都使用迭代子作为它的参数和返回值，以此在容器（序列）上进行各种操作。
11.6.1 函数对象
11.6.2 泛型算法
11.6.1 函数对象每个泛型算法（ generic algorithm）的实现都独立于单独的容器类型，它消除了算法的类型依赖性。
在 C++中,为了使程序的安全性更好,采用,引用,来代替指针作为函数的参数或返回值 。 在 C++的泛型算法中类似地采用了,函数对象,（ function object）
来代替函数指针 。 函数对象是一个类,它重载了函数调用操作符 （ operator()） 。
该操作符封装了应该被实现为一个函数的操作 。 典型情况下,函数对象被作为实参传递给泛型算法 。 和,引用,一样,,函数对象,独立使用比较少 。 函数对象亦称拟函数对象 （ function_like object） 和函子 （ functor） 。 下面给出一个求和函数对象的定义：
template<typename T>class Sum{
T res;
public:
sum(T i=0):res(i){}//构造函数,即 sum(T i=0){res=i;}
void operator()(T x){res+=x;}//累加
T result() const {return res;}//
}
11.6.1 函数对象函数对象与函数指针相比较有三个优点：第一,函数指针是间接引用,不能作为内联函数,而函数对象可以,这样速度更快；第二,函数对象可以拥有任意数量的额外数据,用这些数据可以缓冲当前数据和结果,
当然多数情况下不一定使用,上例中 res就是一个额外数据；第三,编译时对函数对象做类型检查 。
下面给出采用函数对象作为,数值比较算法,的求序列中最小值的函数模板 。
template<typename Type,typename Comp>
const Type& min(const Type*p,int size,Comp comp){
int minIndex=0;//最小元素下标初值为 0,即设 0号元素最小
for(int i=1;i<size;i++)
if(comp(p[i],p[minIndex])) minIndex=i;
return p[minIndex];
}
11.6.1 函数对象函数对象来源 。
1,标准库预定义的一组算术,关系和逻辑函数对象；
2,预定义的一组函数适配器,允许对预定义的函数对象进行特殊化或扩展；
３．自定义函数对象。
预定义函数对象分为算术,关系和逻辑操作 。 每个对象都是一个类模板,其中操作数类型作为模板参数 。 使用时要包含头文件：
#include<functional>
11.6.1 函数对象我们以加法为例,讨论名为 plus的类模板,对整数的用法实例如下：
plus<int>intAdd;
int ival1=30,ival2=15;
int sum=intAdd(ival1,ival2);//等效于,sum=ival1+inval2
但是函数对象主要是作为泛型算法的实参使用,通常用来改变缺省的操作,比如在 【 例 11.3】 中有
sort(vec.begin(),vec.end(),greater<int>());
这就是把整数的大于关系函数对象作为实参,得降序排列 。
如果是字符串,则有：
sort(svec.begin(),svec.end(),greater<string>());
11.6.1 函数对象比较算法在内置类型 int,字符串类 string中定义 。 还可以自定义整数类 Int:
class Int{
public:
Int(int ival=0):_val(ival){}
int operator_(){return -_val;}//负数符号重载
int operator%(int val){return _val%ival;}//求余符号重载
bool operator<(int val){return _val<ival;}//小于符号重载
bool operator!(){return _val==0;}//逻辑非符号重载
private:
int _val;
};
每个类对象都可以作为有名或无名对象传给函数，同时也把所需重载的算法传过去了。
11.6.1 函数对象下面给出各种函数对象及其使用方法：参数和返回值 。 为方便,定义以下变量 （ 对象 ）
vector<string>svec;
string sval1,sval2,sres;
complex cval1,cval2,cres;
int ival1,ival2,ires;
Int Ival1,Ival2,Ires;
double dval1,dval2,dres;
11.6.1 函数对象为了用实例来说明使用方法,定义一个可用单参数函数对象
(一元函数对象 )的函数模板和一个可用双参数函数对象 （ 二元函数对象 ） 的函数模板：
template<Typename FuncObject,Typename Type>
Type UnaryFunc(FuncObjectfob,const Type&val){return fob(val);}
template<Typename FuncObject,Typename Type>
Type BinaryFunc(FuncObjectfob,const Type&val1,const
Type&val2){return fob(val1,val2);}
11.6.1 函数对象算术函数对象：
加法,plus<Type>
minus<int>intSub;ires=intSub(ival1,ival2);
dres=BinaryFunc(plus<double>(),dval1,dval2);
sres=BinaryFunc(plus<string>(),sval1,sval2);
减法,minus<Type>//同加法乘法,multiplies<Type>//对串类无定义,不能用串,可用于复数和浮点数等
cres=BinaryFunc(multiplies<complex>(),cal1,cal2);
dres=BinaryFunc(multiplies<double>(),dval1,dval2);
除法,divides<Type>//同乘法求余,modulus<Type>//不能用于复数,浮点数,只能用于整数
modulus<Int>ImtModulus;Ires=IntModulus<Ival1,Ival2);//自定义类型
ires=BinaryFunc(modulus<int>(),ival1,ival2);
11.6.1 函数对象取反,negate<Type>//同取余,但为单参数
ires=UnaryFunc(negate<Int>(),Ival1);
逻辑函数对象,这里 Type必须支持逻辑运算,有两个参数 。
逻辑与,//对应 &&
逻辑或,//对应 ||
逻辑非,//对应 !
关系函数对象,它们的返回值为布尔量,两个参数,第一参数和第二参数相比：
等于,equal_to<Type>
不等于,not_equal_to<Type>
大于,great<Type>
大于等于,great_equal<Type>
小于,less<Type>
小于等于,less_equal<Type>
11.6.1 函数对象返回布尔值的函数对象称为谓词 （ predicate）,默认的二进制谓词是小于比较操作符,<”,所以默认的排序方式都是升序排列,它采用小于比较形式 。
和容器类一样,函数对象也可以由函数适配器来特殊化或扩展一元 （ 单参数 ） 或二元 （ 双参数 ） 函数对象：
1,绑定器 （ binder）,把二元函数对象中的一个参数固定
（ 绑定 ）,使之转为一元函数,C++标准库提供两种预定义的
binder适配器,bind1st和 bind2nd,分别绑定了第一或第二个参数 。
２．取反器（ negator）：把函数对象的值翻转的适配器，如原来为小于，用了它后就变成了大于。 C++标准库也提供了两种
negator适配器,not1和 not2。 not1用于一元预定义函数对象；
not2用于二元预定义函数对象。
11.6.2 泛型算法在 C++标准库中给出了 70余种算法,泛型算法函数名都加有后缀,这些后缀的意思如下：
_if 表示函数采用的操作是在元素上,而不是对元素的值本身进行操作 。 如 find_if算法表示查找一些值满足函数指定条件的元素,而 find查找特定的值 。
_copy 表示算法不仅操作元素的值,而且还把修改的值复制到一个目标范围中 。 reverser算法颠倒范围中元素的排列顺序,而 reverse_copy算法同时把结果复制到目标范围中 。
其它的后缀从英文意思上立即可以认出其意义，对照附录 C
11.6.2 泛型算法其次我们介绍泛型算法的构造与使用方法 。 所有泛型算法的前两个实参是一对 iterator,通常称为 first和
last,它们标出要操作的容器或内置数组中的元素范围 。
元素的范围,包括 first,但不包含 last的左闭合区间 。
即：
[first,last)
当 first==last成立,则范围为空 。
对 iterator的类则要求在每个算法声明中指出（ 5个基本类别），所声明的是最低要求。
11.6.2 泛型算法泛型算法分以下几类：
１,查找算法,有 13种查找算法用各种策略去判断容器 中 是 否 存 在 一 个 指 定 值 。 equal_range(),
lower_bound()和 upper_bound()提供对半查找形式 。
２,排序和通用整序算法,共有 14种排序 （ sorting）
和通用整序 （ ordering） 算法,为容器中元素的排序提供各种处理方法 。 所谓整序,是按一定规律分类,如分割 （ partition） 算法把容器分为两组,一组由满足某条件的元素组成,另一组由不满足某条件的元素组成 。
３．删除和代替算法,有 15种删除和代替算法。
11.6.2 泛型算法
４．排列组合算法,有 2种算法。排列组合是指全排列。如：三个字符 {a,b,c}组成的序列有 6种可能的全排列,abc,acb,bac，
bca,cab,cba；并且六种全排列按以上顺序排列，认为 abc最小，
cba最大，因为 abc是全顺序（从小到大）而 cba是全逆序（从大到小）。
５．生成和改变算法,有 6种，包含生成（ generate），填充
（ fill）等等。
６．关系算法,有 7种关系算法，为比较两个容器提供了各种策略，
包括相等（ equal()），最大（ max()），最小（ min()）等等。
７．集合算法,4种集合（ set）算法提供了对任何容器类型的通用集合操作。包括并（ union），交（ intersection），差
（ difference）和对称差（ symmetric difference）。
11.7 VC++中的 STL
VC++支持 STL,STL放在标准 C++库中 （ Standard C++ Library）,由一系列的头文件组成,名称采用标准 STL中的名称 。
标准 C++库中与模板有关的头文件主要有：输入输出流 （ iostream） 和标准模板库 。 VC++中对 STL有所扩展,它另外包括以下容器：
hash map； hash multimap； hash set； hash multiset；
采用散列算法 。 这样 VC++共有 11种一类容器 。
在 VC++的 MFC中有微软开发的群 （ collections） 类 （ 微软自译为集合类,为不和 set混淆,本书取群类 ）,包括有任何类型的对象群和任何类型对象指针群：
CArray； CList ； CMap ； CTypePtrArray ； CTypePtrList ；
CTypePtrMap；
它们也都是模板 。
在 VC++的活动模板库类 （ ATL,Active Template Library） 中也有微软开发的群 （ collections） 类：
CAtlArray CAtllist CAtlMap CAutoPtrArray CAutoPtrlist
CAutoPtrMap
后三种为智能指针。
库 （ library） 是一系列程序组件的集合,它们可以在不同的程序中重复使用 。 库函数设计的第一位的要求就是通用性,为程序员提供大量实用的库是 C++的又一特色 。
标准模板库 （ Standard Template Library）
是 ANSI/ISO C++最有特色,最实用的部分之一 。
STL 包含了容器类 （ container ）,迭代子
（ iterator） 和算法 （ algorithm） 三个部分 。
第十一章 标准模板库（ STL）
11.1 标准模板库简介
11.3 顺序容器
11.2 迭代子类
11.5 容器适配器
11.7 VC++中的 STL
11.6 泛型算法与函数对象
11.4 关联容器
11.1 标准模板库简介
STL提供了一个标准化的模板化的对象容器库,包含多种数据结构及其算法,可以节省大量的时间和精力,而且程序是高质量的 。
容器类是管理序列的类，是容纳一组对象或对象集的对象，甚至可以包含混合的对象，包含一组不同类型的对象，称为异类容器
（ heterogeneous container），一组相同类型的对象，称为同类容器 (homogenous container)。通过由容器类提供的成员函数，可以实现诸如向序列中插入元素，删除元素，查找元素等操作，
这些成员函数通过返回迭代子来指定元素在序列中的位置。迭代子是面向对象版本的指针，它提供了访问容器或序列中每个对象的方法。这样就可以把算法用于容器所管理的序列。
11.1 标准模板库简介容器分为三大类：
顺序容器 （ sequence container or sequential container）
关联容器 （ associative container）
容器适配器 （ container adopter）
顺 序 容 器 和 关 联 容 器 称 为 第 一 类 容 器 （ first-class
container） 。 另外有四种容器称为近容器 （ near container）,
C语言风格数组,字符串 string,操作 1/0标志值的 bitset和进行高速数学矢量运算的 valarray。
11.1 标准模板库简介标准库容器类 说明顺序容器
vector（ 参量 ）
deque（ 双端队列 ）
list（ 列表 ）
从后面快速插入与删除,直接访问任何元素从前面或后面快速插入与删除,直接访问任何元素从任何地方快速插入与删除,双链表关联容器
set（ 集合 ）
multiset（ 多重集合 ）
map（ 映射 ）
multimap（ 多重映射 ）
快速查找,不允许重复值快速查找,允许重复值一对一映射,基于关键字快速查找,不允许重复值一对多映射,基于关键字快速查找,允许重复值容器适配器
stack（ 栈 ）
queue（ 队列 ）
priority_queue（ 优先级队列 ）
后进先出 （ LIFO）
先进先出 （ FIFO）
最高优先级元素总是第一个出列表 11.1 标准库容器类
11.1 标准模板库简介
STL也使容器提供接口 。 许多基本操作是所有容器都适用的,而有些操作则适用于类似容器的子集 。 可以用新的类来扩展 STL。 参见表
11.2。 这些函数和运算符可通称为容器的接口 。
各容器具体接口参见附录 C。
使用 STL容器或容器适配器，要包含定义该容器模板类头文件。参见表 11.3。 这些 头文件的内容都在 std名字空间域（ namespace std）
中,程序中必须加以说明 。
11.1 标准模板库简介在有关数组、链表和二叉树等线性表和非线性表的讨论中，
若要访问其中一个元素（结点），我们可以用下标或者指针去访问，而下标实际上也是一种指针即地址，访问时取地址的方式还有很多，一系列的访问方法都可以抽象为迭代子（ iterator）。访问方法最终要归于内存地址的获得，所以说 迭代子是面向对象版本的指针 。
迭代子与指针有许多相同之处，但 迭代子保存所操作的特定容器需要的状态信息,从而实现与每种容器类型相适应的迭代子。
而且有些迭代子操作在所有容器中是一致的，如 ++运算符总是返回容器下一个元素的迭代子，间接引用符,*”，总是表示迭代子指向的容器元素。
迭代子用来将 STL的各部分结合在一起。从本质上说,STL提供的所有算法都是模板，我们可以通过使用自己指定的迭代子来对这些模板实例化。迭代子可以包括指针，但又不仅是一个指针。
11.1 标准模板库简介
STL最大的优点是提供能在各种容器中通用的算法,例如插入,
删除,查找,排序等等 。
STL提供 70种左右的标准算法。算法只是间接通过迭代子操作容器元素。
算法通常返回迭代子。一个算法通常可用于多个不同的容器，
所以称为泛型算法（ generic algorithm）。
算法分为：
１,修改容器的算法，即变化序列算法（ mutating-sequence
algorithm），如 copy(),remove(),replace(),swap()等。
２．不修改容器的算法，即非变化序列算法（ non-mutating-
sequence algorithm），如 count(),find()等。
３．数字型算法。
11.2 迭代子类
C++标准库中有五种预定义迭代子，其功能最强最灵活的是随机访问迭代子。
标准库定义迭代子类型 说明输入 （ InputIterator）
输出 （ OutputIterator）
正向 （ ForwardIterator）
双向 （ BidirectionalIterator）
随机访问
（ RandomAccessIterator）
从容器中读取元素 。 输入迭代子只能一次一个元素地向前移动
（ 即从容器开头到容器末尾 ） 。 要重读必须从头开始 。
向容器写入元素 。 输出迭代子只能一次一个元素地向前移动 。
输出迭代子要重写,必须从头开始 。
组合输入迭代子和输出迭代子的功能,并保留在容器中的位置
（ 作为状态信息 ）,所以重新读写不必从头开始 。
组合正向迭代子功能与逆向移动功能 （ 即从容器序列末尾到容器序列开头 ） 。
组合双向迭代子的功能,并能直接访问容器中的任意元素,即可向前或向后跳过任意个元素 。
表 11.4 迭代子类别
11.2 迭代子类标准库定义迭代子的层次结构,按这个层次,从上到下,功能越来越强 。 但不是继承 ！
input output
forward
bidirectional
random access
图 11.1 迭代子层次
11.2 迭代子类只有第一类容器能用迭代子遍历。表 11.5给出各种不同容器所支持的迭代子类别。标准库定义的各种迭代子可进行的操作参见表 11.6，
容器 支持的迭代子类别顺序容器
vector
deque
list
随机访问 （ random access）
随机访问 （ random access）
双向 （ bidirection）
关联容器
set
multiset
map
multimap
双向 （ bidirection）
双向 （ bidirection）
双向 （ bidirection）
双向 （ bidirection）
容器适配器
stack
queue
priority_queue
不支持迭代子不支持迭代子不支持迭代子
11.2 迭代子类下面结合 find()算法讨论迭代子与泛型算法的关系 。 find()定义如下：
template<typename InputIterator,typename T >
InputIterator find(InputIterator first,InputIterator
last,count T value ){
for(;first!=last;++first) if(value==*first) return first;
return last
}
可见,泛型算法不直接访问容器的元素,与容器无关 。 元素的全部访问和遍历都通过迭代子实现 。 并不需要预知容器类型 。 find()
算法也支持系统内置的数组类型：
11.2 迭代子类
【 例 11.1】 寻找数组元素 。
#include<algorithm>
#include<iostream>
using namespace std;
void main(){
int search_value,ia[9]={47,29,37,23,11,7,5,31,41};
cout<<"请输入需搜索的数,"<<endl;
cin>>search_value;
int* presult=find(&ia[0],&ia[9],search_value);
cout<<"数值 "<<search_value<<(presult==&ia[9]?"不存在 ":"存在 ")<<endl;
}
这里 a[9]数组元素并不存在，但内存地址单元存在。
11.2 迭代子类
【 例 11.2】 寻找 vector容器元素 。
#include<algorithm>
#include<vector>
#include<iostream>
using namespace std;
void main(){
int search_value,ia[9]={47,29,37,23,11,7,5,31,41};
vector<int> vec(ia,ia+9); //数据填入 vector
cout<<"请输入需搜索的数,"<<endl;
cin>>search_value;
vector<int>::iterator presult; //定义迭代子
presult=find(vec.begin(),vec.end(),search_value);
cout<<"数值 "<<search_value<<(presult==vec.end()?"不存在
":"存在 ")<<endl; }
11.2 迭代子类在 <iterator>头文件中还定义了一些专用迭代子：
反转迭代子 (reverse iterator)；
插入型迭代子 (insertion iterator)；
流迭代子 (stream iterator)；
流缓冲迭代子 (stream buffer iterator)；
11.2 迭代子类
１．反转型迭代子（ reverse iterator）把一切都颠倒过来
vector<int> veco;
vector<int>::reverse_iterator r_iter;
for(r_iter=veco.rbegin();//将 r_iter指向到末元素
r_iter!=veco.rend();//不等于首元素的前导
r_iter++){//实际是上是递减
//循环体
}
如果要把升序的序列改为降序的序列，只要使用反转迭代子就可以了。反转迭代子定义为随机迭代子。
11.2 迭代子类
２,插入型迭代子 （ insertion iterator）,可以用输出迭代子来产生一个元素序列 。
可以添加元素而不必重写 。 有三种插入迭代子：
back_insert_iterator<Type>是输出迭代子,用来将产生的元素添加到类型为
Type的容器对象的末端 。 就象在一个字符串末尾加一个串 （ strcat()） 。
front_insert_iterator<Type>是输出迭代子,用来将产生的元素添加到容器的前端,就是,产生出来的元素以逆序方式结束于被控序列前端 。
insert_iterator<Type,Iter>也是输出迭代子,它用来将产生的元素插入到一个由迭代子 （ 第二个参数 Iter） 指定的元素的前面 。 与之对应的也有三个相关的适配器函数,它们返回特定的插入迭代子：
back_inserter(Type&)：它使用容器的 push_back()插入操作代替赋值操作符,
实参是容器自己 。 返回一个 back_inserter迭代子 。
front_insertor(Type&)：使用容器的 push_front()插入操作代替赋值操作符,
实参也是容器本身 。 返回一个 front_inserter迭代子 。
inserter（ Type&,Iter）：用容器的 insert()插入操作符代替赋值操作符。
inserter()要求两个实参：容器本身和它的一个迭代子指示起始插入的位置。标记起始插入位置的迭代子并不保持不变，而是随每个被插入的元素而递增，这样每个元素就能顺序被插入。
11.2 迭代子类
３,流 迭 代 子 有 输 入 流 迭 代 子 （ istream_iterator ） 和 输 出 流 迭 代 子
（ ostream_iterator） 。 在 <iostream.h>,<fstream.h>等头文件中定义了流类库,在 STL中为输入 /输出流 iostream提供了迭代子,它们可以与标准库容器类型和泛型算法结合起来工作 。 使用这两个迭代子必须包含头文件 <iterator>。
输入流迭代子 （ istream_iterator） 类支持在 istream及其派生类 （ 如 ifstream）
上的迭代子操作 。 istream_iterator声明方式为：
istream_iterator<Type>迭代子标识符 (istream&);
//Type为已定义了输入操作的类型,实参可以是任意公有派生的 istream的子类型的对象输出流也有对应的 ostream_iterator类支持,其声明方式为：
ostream_iterator<Type>迭代子标识符 (ostream&)//实参同样可以是公有派生子类型对象
ostream_iterator<Type>迭代子标识符 (ostream&,char*)//第二参数为 C风格字符串
11.2 迭代子类下面结合 copy算法和 sort算法来介绍 istream iterator和 ostream_iterator。
【 例 11.3】 用 istream iterator从标准输入读入一个整数集到 vector中 。
#include<iostream>
#include<iterator>
#include<algorithm>
#include<vector>
#include<functional>
using namespace std;
void main(){ istream_iterator<int> input(cin);
istream_iterator<int> end_of_stream;
vector<int> vec;
copy(input,end_of_stream,inserter(vec,vec.begin()));//输入 ^Z结束流
sort(vec.begin(),vec.end(),greater<int>());//升序排列
ostream_iterator<int>output(cout," ");
unique_copy(vec.begin(),vec.end(),output);
}
11.2 迭代子类输入：
41 3 9 5 7 23 17 19 13 11 37 31 23 29 41 39 ^Z
泛型算法 copy()定义如下：
template<typename InputIterator,typename InputIterator,typename OutputInterator>OutputIterator
copy(InputIterator first,InputIterator last,OutputInterator x){
for(;first!=last;++x,++first) *x=*first
return (x);
}
11.2 迭代子类
end_of_stream是指示文件 （ 流 ） 结束位置,它使用了缺省的构造函数,输入时必须在最后一个数字后加分隔符,然后加 Ctrl-Z结束 。 拷贝算法要求我们提供一对
iterator来指示文件 （ 流 ） 内部的开始和结束位置 。 我们使用由 istream对象初始化的
istream_iterator提供开始位置,本例中为 input。
本例中插入迭代子 inserter作为 copy的第三个参数,它是输出型的,把流插入 vec。
泛 型 算 法 sort() 为 升 序 排 序 算 法,声 明 如 下 template<typename
RandomAccessInterator,typename Pr>
void sort(RandomAccessIterator first,RandomAccessInterator last,Pr p);
第三参数为排序方式,greater<int>()是预定义的,大于,函数对象,排序时用它来比较数值大小 。 缺省时为,小于,,即升序排序 。
例中用输出迭代子 output来输出,泛型算法 unique_copy（ ）,复制一个序列,
并删除序列中所有重复元素 。 本例中,拷贝到 output迭代子,即用空格分隔各整数的标准输出 。 输出为：
41 39 37 31 29 23 19 17 13 11 9 7 5 3
11.2 迭代子类
４．流缓冲迭代子。这是 STL后添加的一对迭代子，用来直接从一个流缓冲区（ streambuffer）中插入或提取某种类型（通常为 char）的元素。
11.3 顺序容器
C++标准模板库提供三种顺序容器,vector,list和 deque。
vector类和 deque类是以数组为基础的,list类是以双向链表为基础的。
矢量 （ vector） 类提供了具有连续内存地址的数据结构 。 通过下标运算符 [ ]直接有效地访问矢量的任何元素 。 与数组不同,vector的内存用尽时,vector自动分配更大的连续内存区,将原先的元素复制到新的内存区,并释放旧的内存区 。 这是矢量 （ vector） 类的优点 。
在这里内存分配是由分配子 （ allocator） 完成 。
矢量可以用来实现队列,堆栈,列表和其他更复杂的结构 。
vector支持随机访问迭代子,vector的迭代子通常实现为 vector
元素的指针。所谓选择容器类，实际上很大部分是在选择所支持的迭代子。
11.3 顺序容器使用向量容器的声明如下：
#include<vector>
……
vector<int> vi;//定义存放整形序列的向量容器对象 vi,长度为 0的空 vector
vector<float> vf; //存放实型序列的向量容器
vector<char> vch; //存放字符序列的向量容器
vector<char *> vstr; //存放字符串 （ 字符指针 ） 序列的向量容器使用方法是典型的函数模板的使用方法 。 调用缺省的构造函数,创建长度为 0的向量 。 矢量容器有多种构造函数 。 包括构造一个有 n个元素的矢量,每个元素都是由元素缺省的构造函数所构造出来的,还可以为每个元素用同一个对象来赋初值 。 还包括拷贝构造函数,可以由一个已有的矢量容器对象来初始化新容器各元素的构造函数 。 这些构造函数还可以显式给出分配子 (allocator)对象 。
11.3 顺序容器对矢量的操作包含了在顺序表中所列出的操作，而且更多。
１．列表（ list）是由双向链表（ doubly linked list）组成的。我们也已经在有关链表的一节中介绍过了，它有两个指针域，可以向前也可以向后进行访问，但不能随机访问，
即支持的迭代子类型为双向迭代子。使用起来很方便，与我们在 § 7.2节中定义的双链表类模板相似，但通用性更好，
使用更方便。列表的定义在头文件 <list>中。
２．双端队列（ deque）（ double-ended queue）类。
双端队列允许在队列的两端进行操作。 支持随机访问迭代子 。 也支持通过使用下标操作符,[ ]”进行访问。
11.3 顺序容器当要增加双端队列的存储空间时,可以在内存块中 deque两端进行分配,通常保存为这些块的指针数组 。 双端队列 利用不连续内存空间,它的 迭代子比 vector的迭代子更加智能化 。 对双端队列分配存储块后,往往要等删除双端队列时才释放,它 比重复分配 （ 释放和再分配 ） 更有效,
但也更浪费内存 。
使用双端队列,必须包含头文件 <deque>。
11.4 关联容器查找和排序总是 对 关键字 进行的，函数模板和类模板中只介绍了 通用类型（亦称泛型类型）,并没有涉及关键字。关联容器（ associative container）能通过关键字（ search key）直接访问 (存储和读取元素 )。四个关联容器为：集合（ set），多重集合（ multiset），映射（ map），多重映射（ multimap）。集合和多重集合类提供了控制数值集合的操作，其中数值是关键字，
映射和多重映射类提供了操作与关键字相关联的映射值
（ mapped value）的方法。
多重集合关联容器用于快速存储和读取关键字。
11.4 关联容器
multiset和 set通常实现为 红黑二叉排序树。
常用的二叉排序树一般结点有四个域：一个数据域，三个指针域（左孩子指针，右孩子指针和双亲指针）。双亲指针使直接回访成为可能，它使二叉排序树删除节点的算法变的简单。在生成二叉排序树时，当输入数据为已排好序时，会形成高度不平衡的只有半边的斜杠形的树，即退化为链表，二叉排序树只有形成平衡的树，也就是接近完全二叉数或满二叉树的形状才能达到对半查找的效果。红黑二叉排序树是实现平衡二叉排序树的方法之一。
11.4 关联容器
【 例 11.4】 整型多重集合关联容器类的演示 。 类模板声明,
template<typename Key,typename Pred = less<Key>,typename A = allocator<Key>
> class multiset;//模板参数表中的非类型参数同样可有缺省值
#include<iostream>
#include<set> //包含集合头文件
#include<algorithm> //包含算法头文件
using namespace std; //C++标准库名字空间域
typedef multiset<int> INTMS; //特例取名 INTMS,整型多重集合按升序排列
11.4 关联容器
void main(){const int size=16;
int a[size]={17,11,29,89,73,53,61,37,41,29,3,47,31,59,5,2};
INTMS intMultiset(a,a+size); ostream_iterator<int>
output(cout," ");
cout<<"这里原来有 "<<intMultiset.count(17)<<"个数值 17"<<endl;
intMultiset.insert(17); //插入一个重复的数 17
cout<<"输入后这里有 "<<intMultiset.count(17)<<"个数值 17"<<endl;
INTMS::const_iterator result; result=intMultiset.find(18);
if(result==intMultiset.end()) cout<<"没找到值 18"<<endl;
else cout<<"找到值 18"<<endl;
cout<<"intMultiset容器中有 "<<endl;
copy(intMultiset.begin(),intMultiset.end(),output); cout<<endl;
}
11.4 关联容器请注意 multiset容器中自动作了升序排列 。 如需要,
可以在 VC++帮助中 （ MSDN） 由关键字 multiset查找有关迭代子,成员函数的定义和用法 。
多重映射和映射关联容器类用于快速存储和读取关键字与相关值（关键字 /数值对,key/value pair）。
如果保存学生的简明资料，要求按学号排序，使用映射关联容器（因为不会重号）是最合适的。如用姓名排序，
因姓名可能重复，使用多重映射更为合适。使用时要用头文件 <set>。
11.5 容器适配器
STL提供了三个容器适配器（ container adapter）：栈（ stack），
队列（ queue）和优先级队。栈是标准的栈，使用时要用头文件 <stack>。
队也是标准的，使用时要用头文件 <queue>。所谓适配器并不独立，它依附在一个顺序容器上。如要声明一个用矢量实现的字符型堆栈，可使用如下声明：
stack<vector<char>> sk;
然后它就可以象顺序容器一样使用。但是它没有自己的构造和析构函数，它使用其实现类（如 vector）的构造和析构函数。就象一个仪器加了一个适配器增加了某些功能一样。队列（ queue）缺省用 deque为基础，
栈（ stack）可用 vector或 deque为基础。
优先级队列（ priority_queue）适配器实现优先级队列。元素插入是自动按优先级顺序插入，使最高优先级元素首先从优先级队列中取出。优先级队列（ priority_queue）的每个常用操作都实现为内联函数，调用基础容器的相应函数时，可避免二次函数调用的开销。常用矢量为基础容器。
缺省情况下 priority_queue实现时用 vector为基础数据结构。
11.5 容器适配器
【 例 11.5】 优先级队列类演示,头文件用 <queue>,优先级用数表示,数值越大优先级越高 。
#include<iostream>
#include<queue>
#include<functional>
using namespace std;
11.5 容器适配器
void main(){
priority_queue<int> prioque;
//实例化存放 int值的优先级队列,并用 deque作为基础数据结构
prioque.push(7);//压入优先级队列
prioque.push(12);
prioque.push(9);
prioque.push(18);
cout<<"从优先级队列中弹出 "<<endl;
while(!prioque.empty()){
cout<<prioque.top()<<'\t';//取最高优先级数据
prioque.pop();//弹出最高优先级数据
}
cout<<endl;
}
11.6 泛型算法与函数对象算法表现为一系列的函数模板，它们完整定义在 STL头文件中。一般这些函数模板都使用迭代子作为它的参数和返回值，以此在容器（序列）上进行各种操作。
11.6.1 函数对象
11.6.2 泛型算法
11.6.1 函数对象每个泛型算法（ generic algorithm）的实现都独立于单独的容器类型，它消除了算法的类型依赖性。
在 C++中,为了使程序的安全性更好,采用,引用,来代替指针作为函数的参数或返回值 。 在 C++的泛型算法中类似地采用了,函数对象,（ function object）
来代替函数指针 。 函数对象是一个类,它重载了函数调用操作符 （ operator()） 。
该操作符封装了应该被实现为一个函数的操作 。 典型情况下,函数对象被作为实参传递给泛型算法 。 和,引用,一样,,函数对象,独立使用比较少 。 函数对象亦称拟函数对象 （ function_like object） 和函子 （ functor） 。 下面给出一个求和函数对象的定义：
template<typename T>class Sum{
T res;
public:
sum(T i=0):res(i){}//构造函数,即 sum(T i=0){res=i;}
void operator()(T x){res+=x;}//累加
T result() const {return res;}//
}
11.6.1 函数对象函数对象与函数指针相比较有三个优点：第一,函数指针是间接引用,不能作为内联函数,而函数对象可以,这样速度更快；第二,函数对象可以拥有任意数量的额外数据,用这些数据可以缓冲当前数据和结果,
当然多数情况下不一定使用,上例中 res就是一个额外数据；第三,编译时对函数对象做类型检查 。
下面给出采用函数对象作为,数值比较算法,的求序列中最小值的函数模板 。
template<typename Type,typename Comp>
const Type& min(const Type*p,int size,Comp comp){
int minIndex=0;//最小元素下标初值为 0,即设 0号元素最小
for(int i=1;i<size;i++)
if(comp(p[i],p[minIndex])) minIndex=i;
return p[minIndex];
}
11.6.1 函数对象函数对象来源 。
1,标准库预定义的一组算术,关系和逻辑函数对象；
2,预定义的一组函数适配器,允许对预定义的函数对象进行特殊化或扩展；
３．自定义函数对象。
预定义函数对象分为算术,关系和逻辑操作 。 每个对象都是一个类模板,其中操作数类型作为模板参数 。 使用时要包含头文件：
#include<functional>
11.6.1 函数对象我们以加法为例,讨论名为 plus的类模板,对整数的用法实例如下：
plus<int>intAdd;
int ival1=30,ival2=15;
int sum=intAdd(ival1,ival2);//等效于,sum=ival1+inval2
但是函数对象主要是作为泛型算法的实参使用,通常用来改变缺省的操作,比如在 【 例 11.3】 中有
sort(vec.begin(),vec.end(),greater<int>());
这就是把整数的大于关系函数对象作为实参,得降序排列 。
如果是字符串,则有：
sort(svec.begin(),svec.end(),greater<string>());
11.6.1 函数对象比较算法在内置类型 int,字符串类 string中定义 。 还可以自定义整数类 Int:
class Int{
public:
Int(int ival=0):_val(ival){}
int operator_(){return -_val;}//负数符号重载
int operator%(int val){return _val%ival;}//求余符号重载
bool operator<(int val){return _val<ival;}//小于符号重载
bool operator!(){return _val==0;}//逻辑非符号重载
private:
int _val;
};
每个类对象都可以作为有名或无名对象传给函数，同时也把所需重载的算法传过去了。
11.6.1 函数对象下面给出各种函数对象及其使用方法：参数和返回值 。 为方便,定义以下变量 （ 对象 ）
vector<string>svec;
string sval1,sval2,sres;
complex cval1,cval2,cres;
int ival1,ival2,ires;
Int Ival1,Ival2,Ires;
double dval1,dval2,dres;
11.6.1 函数对象为了用实例来说明使用方法,定义一个可用单参数函数对象
(一元函数对象 )的函数模板和一个可用双参数函数对象 （ 二元函数对象 ） 的函数模板：
template<Typename FuncObject,Typename Type>
Type UnaryFunc(FuncObjectfob,const Type&val){return fob(val);}
template<Typename FuncObject,Typename Type>
Type BinaryFunc(FuncObjectfob,const Type&val1,const
Type&val2){return fob(val1,val2);}
11.6.1 函数对象算术函数对象：
加法,plus<Type>
minus<int>intSub;ires=intSub(ival1,ival2);
dres=BinaryFunc(plus<double>(),dval1,dval2);
sres=BinaryFunc(plus<string>(),sval1,sval2);
减法,minus<Type>//同加法乘法,multiplies<Type>//对串类无定义,不能用串,可用于复数和浮点数等
cres=BinaryFunc(multiplies<complex>(),cal1,cal2);
dres=BinaryFunc(multiplies<double>(),dval1,dval2);
除法,divides<Type>//同乘法求余,modulus<Type>//不能用于复数,浮点数,只能用于整数
modulus<Int>ImtModulus;Ires=IntModulus<Ival1,Ival2);//自定义类型
ires=BinaryFunc(modulus<int>(),ival1,ival2);
11.6.1 函数对象取反,negate<Type>//同取余,但为单参数
ires=UnaryFunc(negate<Int>(),Ival1);
逻辑函数对象,这里 Type必须支持逻辑运算,有两个参数 。
逻辑与,//对应 &&
逻辑或,//对应 ||
逻辑非,//对应 !
关系函数对象,它们的返回值为布尔量,两个参数,第一参数和第二参数相比：
等于,equal_to<Type>
不等于,not_equal_to<Type>
大于,great<Type>
大于等于,great_equal<Type>
小于,less<Type>
小于等于,less_equal<Type>
11.6.1 函数对象返回布尔值的函数对象称为谓词 （ predicate）,默认的二进制谓词是小于比较操作符,<”,所以默认的排序方式都是升序排列,它采用小于比较形式 。
和容器类一样,函数对象也可以由函数适配器来特殊化或扩展一元 （ 单参数 ） 或二元 （ 双参数 ） 函数对象：
1,绑定器 （ binder）,把二元函数对象中的一个参数固定
（ 绑定 ）,使之转为一元函数,C++标准库提供两种预定义的
binder适配器,bind1st和 bind2nd,分别绑定了第一或第二个参数 。
２．取反器（ negator）：把函数对象的值翻转的适配器，如原来为小于，用了它后就变成了大于。 C++标准库也提供了两种
negator适配器,not1和 not2。 not1用于一元预定义函数对象；
not2用于二元预定义函数对象。
11.6.2 泛型算法在 C++标准库中给出了 70余种算法,泛型算法函数名都加有后缀,这些后缀的意思如下：
_if 表示函数采用的操作是在元素上,而不是对元素的值本身进行操作 。 如 find_if算法表示查找一些值满足函数指定条件的元素,而 find查找特定的值 。
_copy 表示算法不仅操作元素的值,而且还把修改的值复制到一个目标范围中 。 reverser算法颠倒范围中元素的排列顺序,而 reverse_copy算法同时把结果复制到目标范围中 。
其它的后缀从英文意思上立即可以认出其意义，对照附录 C
11.6.2 泛型算法其次我们介绍泛型算法的构造与使用方法 。 所有泛型算法的前两个实参是一对 iterator,通常称为 first和
last,它们标出要操作的容器或内置数组中的元素范围 。
元素的范围,包括 first,但不包含 last的左闭合区间 。
即：
[first,last)
当 first==last成立,则范围为空 。
对 iterator的类则要求在每个算法声明中指出（ 5个基本类别），所声明的是最低要求。
11.6.2 泛型算法泛型算法分以下几类：
１,查找算法,有 13种查找算法用各种策略去判断容器 中 是 否 存 在 一 个 指 定 值 。 equal_range(),
lower_bound()和 upper_bound()提供对半查找形式 。
２,排序和通用整序算法,共有 14种排序 （ sorting）
和通用整序 （ ordering） 算法,为容器中元素的排序提供各种处理方法 。 所谓整序,是按一定规律分类,如分割 （ partition） 算法把容器分为两组,一组由满足某条件的元素组成,另一组由不满足某条件的元素组成 。
３．删除和代替算法,有 15种删除和代替算法。
11.6.2 泛型算法
４．排列组合算法,有 2种算法。排列组合是指全排列。如：三个字符 {a,b,c}组成的序列有 6种可能的全排列,abc,acb,bac，
bca,cab,cba；并且六种全排列按以上顺序排列，认为 abc最小，
cba最大，因为 abc是全顺序（从小到大）而 cba是全逆序（从大到小）。
５．生成和改变算法,有 6种，包含生成（ generate），填充
（ fill）等等。
６．关系算法,有 7种关系算法，为比较两个容器提供了各种策略，
包括相等（ equal()），最大（ max()），最小（ min()）等等。
７．集合算法,4种集合（ set）算法提供了对任何容器类型的通用集合操作。包括并（ union），交（ intersection），差
（ difference）和对称差（ symmetric difference）。
11.7 VC++中的 STL
VC++支持 STL,STL放在标准 C++库中 （ Standard C++ Library）,由一系列的头文件组成,名称采用标准 STL中的名称 。
标准 C++库中与模板有关的头文件主要有：输入输出流 （ iostream） 和标准模板库 。 VC++中对 STL有所扩展,它另外包括以下容器：
hash map； hash multimap； hash set； hash multiset；
采用散列算法 。 这样 VC++共有 11种一类容器 。
在 VC++的 MFC中有微软开发的群 （ collections） 类 （ 微软自译为集合类,为不和 set混淆,本书取群类 ）,包括有任何类型的对象群和任何类型对象指针群：
CArray； CList ； CMap ； CTypePtrArray ； CTypePtrList ；
CTypePtrMap；
它们也都是模板 。
在 VC++的活动模板库类 （ ATL,Active Template Library） 中也有微软开发的群 （ collections） 类：
CAtlArray CAtllist CAtlMap CAutoPtrArray CAutoPtrlist
CAutoPtrMap
后三种为智能指针。
