第十一章 标准模板库（STL）

1、第十一章 标准模板库（STL）,库（library）是一系列程序组件的集合，它们可 以在不同的程序中重复使用。库函数设计的第一位的要求就是通用性，模板（template）为通用性带来了不可估量的前景，我们可以在使用模板时才对某些类型作选择。模板是标准C+实现代码复用的有力工具，特别是在有关数据结构的算法方面。为程序员提供大量实用的库是C+的又一特色。 标准模板库（Standard Template Library）是ANSI/ISO C+最有特色、最实用的部分之一。STL包含了容器类（container）、迭代子（iterator）和算法（algorithm）三个部分。泛型算法（generic

2、 algorithm）和函数对象（function object）的概念与使用使算法摆脱了对不同类型数据个性操作的依赖，这样就可以编出更具通用性的算法。,11.1 标准模板库简介,11.3 顺序容器,11.2 迭代子类,11.5 容器适配器,11.7 VC+中的STL,11.6 泛型算法与函数对象,11.4 关联容器,第十一章 标准模板库（STL）,11.1 标准模板库简介,容器类是管理序列的类，是容纳一组对象或对象集的类。通过由容器类提供的成员函数，可以实现诸如向序列中插入元素，删除元素，查找元素等操作，这些成员函数通过返回迭代子来指定元素在序列中的位置。,STL提供了一个标准化的模板化的对

3、象容器库，包含多种数据结构及其算法，可以节省大量的时间和精力，而且程序是高质量的。,迭代子是面向对象版本的指针，它提供了访问容器或序列中每个对象的方法。这样就可以把算法用于容器所管理的序列。,泛型算法不依赖于具体的容器，通用的算法更易于扩充。泛型算法中采用函数对象（function object）引入不同情况下同一算法的差异。它没有使用继承和多态，避免了虚函数的开销，使STL效率更高。,11.1 标准模板库简介,容器分为三大类：,11.1 标准模板库简介,顺序容器和关联容器称为第一类容器（first-class container）。另外有四种容器称为近容器（near container）：C

4、语言风格数组、字符串string、操作1/0标志值的bitset和进行高速数学矢量运算的valarray。 它们虽然提供与第一类容器类似的功能，但没有全部功能。,STL也使容器提供类似的接口。许多基本操作是所有容器都适用的，而有些操作则适用于类似容器的子集。这样就可以用新的类来扩展STL。这些函数和运算符可通称为容器的接口。,表11.2 所有标准库容器共有的函数,11.1 标准模板库简介,11.1 标准模板库简介,表11.3 只在第一类中的函数,11.1 标准模板库简介,使用STL容器或容器适配器，要包含定义该容器模板类头文件。参见表11.4。这些头文件的内容都在std名字空间域中，程序中必须

5、加以说明。,表11.4 标准容器库的头文件,11.1 标准模板库简介,在有关数组、链表和二叉树等线性表和非线性表的讨论中，若要访问其中一个元素（结点），我们可以用下标或者指针去访问，而下标实际上也是一种指针即地址，访问时取地址的方式还有很多，一系列的访问方法都可以抽象为迭代子（iterator）。访问方法最终要归于内存地址的获得，所以说迭代子是面向对象版本的指针。,迭代子与指针有许多相同之处，但迭代子保存所操作的特定容器需要的状态信息，从而实现与每种容器类型相适应的迭代子。而且有些迭代子操作在所有容器中是一致的，如+运算符总是返回容器下一个元素的迭代子，间接引用符“*”，总是表示迭代子指向的容

6、器元素。,迭代子用来将STL的各部分结合在一起。从本质上说，STL提供的所有算法都是模板，我们可以通过使用自己指定的迭代子来对这些模板实例化。迭代子可以包括指针，但又不仅是一个指针。,11.1 标准模板库简介,STL最大的优点是提供能在各种容器中通用的算法，例如插入、删除、查找、排序等等。 STL提供70种左右的标准算法。算法只是间接通过迭代子操作容器元素。 算法通常返回迭代子。一个算法通常可用于多个不同的容器，所以称为泛型算法（generic algorithm）。 算法分为： 修改容器的算法，即变化序列算法（mutating-sequence algorithm），如copy()、remo

7、ve()、replace()、swap()等。 不修改容器的算法，即非变化序列算法（non-mutating-sequence algorithm），如count()、find()等。 数字型算法。,11.2 迭代子类,C+标准库中有五种预定义迭代子，其功能最强最灵活的是随机访问迭代子。,输入 InputIterator 输出 OutputIterator 正向 ForwardIterator 双向Bidirectional Iterator 随机访问 Random AccessIterator,从容器中读取元素。输入迭代子只能一次一个元素地向前移动（即从容器开头到容器末尾）。要重读必须从头开

8、始。 向容器写入元素。输出迭代子只能一次一个元素地向前移动。输出迭代子要重写，必须从头开始。 组合输入迭代子和输出迭代子的功能，并保留在容器中的位置（作为状态信息），所以重新读写不必从头开始。 组合正向迭代子功能与逆向移动功能（即从容器序列末尾到容器序列开头）。 组合双向迭代子的功能，并能直接访问容器中的任意元素，即可向前或向后跳过任意个元素。,表11.5 迭代子类别,11.2 迭代子类,标准库定义迭代子的层次结构，按这个层次，从上到下，功能越来越强。但不是继承！,图11.1 迭代子层次,11.2 迭代子类,只有第一类容器能用迭代子遍历。,表11.6 STL容器支持的迭代子类别,表11.7 各

9、种迭代子可执行的操作,结合find()算法讨论迭代子与泛型算法的关系。find()定义如下： template InputIterator find(InputIterator first, InputIterator last, count T value ) for(;first!=last;+first) if(value=*first) return first; return last 可见，泛型算法不直接访问容器的元素，与容器无关。元素的全部访问和遍历都通过迭代子实现。并不需要预知容器类型。,11.2 迭代子类,【例11.1】寻找数组元素。 #include #include us

10、ing namespace std; void main() int search_value,ia9=47,29,37,23,11,7,5,31,41; coutsearch_value; int* presult=find( 这里a9数组元素并不存在，但内存地址单元存在。,11.2 迭代子类,【例11.2】寻找vector容器元素。 #include #include #include using namespace std; void main() int search_value,ia9=47,29,37,23,11,7,5,31,41; vector vec(ia,ia+9); /数

11、据填入vector coutsearch_value; vector:iterator presult; /定义迭代子 presult=find(vec.begin(),vec.end(),search_value); cout数值search_value (presult=vec.end() ?不存在:存在)endl;,11.2 迭代子类,在头文件中还定义了一些专用迭代子： 反转型迭代子（reverse iterator）把一切都颠倒过来。正向遍历一个第一类容器时，如果用了反转迭代子，实际上实现的是反向遍历。第一类容器支持两对操作：begin()和end()，分别返回指向容器首元素和容器的末

12、元素的后继的迭代子；而rbegin()和rend()，分别返回指向容器末元素和容器的首元素的前导的迭代子。后一对操作用于支持反转型迭代子。 vector veco; vector:reverse_iterator r_iter; for(r_iter=veco.rbegin(); /将r_iter指向到末元素 r_iter!=veco.rend(); /不等于首元素的前导 r_iter+) /实际是上是递减 如果要把升序的序列改为降序的序列，只要使用反转迭代子就可以了。反转迭代子定义为随机迭代子。,11.2 迭代子类,插入型迭代子（insertion iterator）：可以用输出迭代子来产生

13、一个元素序列。可以添加元素而不必重写。有三种插入迭代子：,back_insert_iterator是输出迭代子，用来将产生的元素添加到类型为Type的容器对象的末端。就象在一个字符串末尾加一个串（strcat()）。,front_insert_iterator是输出迭代子，用来将产生的元素添加到容器的前端，就是，产生出来的元素以逆序方式结束于被控序列前端。,insert_iterator也是输出迭代子，它用来将产生的元素插入到一个由迭代子（第二个参数Iter）指定的元素的前面。与之对应的也有三个相关的适配器函数，它们返回特定的插入迭代子：,back_inserter(Type void mai

14、n() istream_iterator input(cin); istream_iterator end_of_stream; vector vec; copy(input,end_of_stream,inserter(vec,vec.begin(); /输入Z结束流 sort(vec.begin(),vec.end(),greater(); /升序排列 ostream_iteratoroutput(cout, ); unique_copy(vec.begin(),vec.end(),output); ,11.2 迭代子类,首先，用一个istream_iterator迭代子input（其实参

15、为cin，即标准输入）读入一个整数集到一个矢量类对象中，出现光标后，可输入： 41 3 9 5 7 23 17 19 13 11 37 31 23 29 41 39 Z,例中泛型算法copy()定义如下： templateOutputIterator copy(InputIterator first,InputIterator last,OutputInterator x) for(;first!=last;+x,+first) *x=*first return (x); ,end_of_stream是指示文件（流）的结束位置，它使用了缺省的构造函数，不必由读者去为它定参数和做任何事，这里标识

16、符是无关紧要的，重要的是无参，调用缺省的构造函数。输入时必须在最后一个数字后加分隔符，然后加Ctrl-Z结束。拷贝算法要求提供一对iterator来指示文件（流）内部的开始和结束位置。我们使用由istream对象初始化的istream_iterator提供开始位置，本例中为input。 本例中插入迭代子inserter作为copy的第三个参数，它是输出型的，把流插入vec。,11.2 迭代子类,泛型算法sort()为升序排序算法，声明如下 template void sort(RandomAccessIterator first, RandomAccessInterator last, Pr

17、p);,第三参数为排序方式，greater()是预定义的“大于”函数对象，排序时用它来比较数值大小。缺省时为“小于”，即升序排序。,例中用输出迭代子output来输出，泛型算法unique_copy（），复制一个序列，并删除序列中所有重复元素。本例中，拷贝到output迭代子，即用空格分隔各整数的标准输出。输出为： 41 39 37 31 29 23 19 17 13 11 9 7 5 3,流缓冲迭代子。这是STL后添加的一对迭代子，用来直接从一个流缓冲区（streambuffer）中插入或提取某种类型（通常为char）的元素。,11.3 顺序容器,1. 矢量（vector）类提供了具有连续内

18、存地址的数据结构。通过下标运算符 直接有效地访问矢量的任何元素。与数组不同，矢量的内存用尽时，矢量自动分配更大的连续内存区，将原先的元素复制到新的内存区，并释放旧的内存区。这是矢量类的优点。在这里内存分配是由分配子（allocator）完成。 矢量可以用来实现队列、堆栈、列表和其他更复杂的结构。vector支持随机访问迭代子，具有最强的功能 。vector的迭代子通常实现为vector元素的指针。所谓选择容器类，实际上很大部分是在选择所支持的迭代子。,C+标准模板库提供三种顺序容器：vector，list和deque。vector类和deque类是以数组为基础的，list类是以双向链表为基础的

19、。,11.3 顺序容器,使用向量容器的声明如下： #include vector vi; /定义存放整形序列的向量容器对象vi，长度为0的空vector vector vf;/存放实型序列的向量容器 vector vch;/存放字符序列的向量容器 vectorvstr;/存放字符串序列的向量容器,使用方法是典型的函数模板的使用方法。调用缺省的构造函数，创建长度为0的向量。矢量容器有多种构造函数。包括构造一个有n个元素的矢量，每个元素都是由元素缺省的构造函数所构造出来的，还可以为每个元素用同一个对象来赋初值。还包括拷贝构造函数，可以由一个已有的矢量容器对象来初始化新容器各元素的构造函数。这些构造

20、函数还可以显式给出分配子(allocator)对象。,11.3 顺序容器,2. 列表（list）是由双向链表（doubly linked list）组成的。我们也已经在有关链表的一节中介绍过了，它有两个指针域，可以向前也可以向后进行访问，但不能随机访问，即支持的迭代子类型为双向迭代子。使用起来很方便，与我们在7.2节中定义的双链表类模板相似，但通用性更好，使用更方便。列表的定义在头文件中。,3. 双端队列（deque）（double-ended queue）类。双端队列允许在队列的两端进行操作。以顺序表为基础，支持随机访问迭代子。 双端队列有高度的灵活性，它放松了访问的限制，对象既可从队首进队

21、，也可以从队尾进队，同样也可从任一端出队。除了可从队首和队尾移走对象外，也支持通过使用下标操作符“ ”进行访问。 要增加存储空间时，可以在内存块中对deque两端分别进行分配。并且新分配的存储空间保存为指向这些块的指针数组，这样双端队列可以利用不连续内存空间。因此它的迭代子比vector的迭代子更加智能化。为双端队列分配的存储块，往往要等删除双端队列时才释放，它比重复分配（再分配和释放）更有效，但也更浪费内存。 使用双端队列，必须包含头文件。,11.4 关联容器,关联容器（associative container）能通过关键字（search key）直接访问(存储和读取元素)。四个关联容器为

22、：集合（set），多重集合（multiset），映射（map）和多重映射（multimap）。,集合和多重集合类提供了控制数值集合的操作，其中数值是关键字，即不必另有一组值与每个关键字相关联。集合与多重集合类的主要差别在于多重集合允许重复的关键字（key），而集合不允许重复的关键字。元素的顺序由比较器函数对象（comparator function object）确定。如对整型multiset，只要用比较器函数对象less排序关键字，元素即可按升序排列。,multiset和set通常实现为红黑二叉排序树。在生成二叉排序树时，当输入数据为已排好序时，会形成高度不平衡的只有半边的斜杠形的树，即退化

23、为链表，二叉排序树只有形成平衡的树，也就是接近完全二叉数或满二叉树的形状才能达到对半查找的效果。红黑二叉排序树是实现平衡二叉排序树的方法之一。,11.4 关联容器,【例11.4】整型多重集合关联容器类的演示。类模板声明: template, typename A = allocator class multiset; /模板参数表中的非类型参数同样可有缺省值 #include #include /包含集合头文件 #include/包含算法头文件 using namespace std; /C+标准库名字空间域 typedef multisetINTMS; /特例取名INTMS，整型多重集合按升

24、序排列,void main() const int size=16; int asize=17,11,29,89,73,53,61,37,41,29,3,47,31,59,5,2; INTMS intMultiset(a,a+size);/用a来初始化INTMS容器实例 ostream_iterator output(cout, ); /整型输出迭代子output，可通过cout输出一个用空格分隔的整数 cout这里原来有intMultiset.count(17)个数值17endl; /查找有几个关键字17,11.4 关联容器,intMultiset.insert(17); /插入一个重复的数

25、17 cout输入后这里有intMultiset.count(17)个数值17endl; INTMS:const_iterator result; /const_iterator使程序可读INTMS的元素 /但不让程序修改它的元素，result为INTMS的迭代子 result=intMultiset.find(18); /找到则返回所在位置，设找到返回与调end()返回的同样值 if(result=intMultiset.end() cout没找到值18endl; else cout找到值18endl; coutintMultiset容器中有endl; copy(intMultiset.be

26、gin(),intMultiset.end(),output); /输出容器中全部元素 coutendl; 运行结果为： 这里原来有1个数值17 输入后这里有2个数值17 没找到值18 容器中有： 2 3 5 11 17 17 29 29 31 37 41 47 53 59 61 73 89 请注意multiset容器中自动作了升序排列。,11.4 关联容器,映射和多重映射类提供了操作与关键字相关联的映射值（mapped value）的方法。映射和多重映射的主要差别在于多重映射允许存放与映射值相关联的重复关键字，而映射只允许存放与映射值一一对应的单一关键字。 多重映射和映射关联容器类用于快速存

27、储和读取关键字与相关值（关键字/数值对，key/value pair）。如果保存学生的简明资料，要求按学号排序，使用映射关联容器（因为不会重号）是最合适的。如用姓名排序，因姓名可能重复，使用多重映射更为合适。使用时要用头文件。,11.5 容器适配器,STL提供了三个容器适配器（container adapter）：栈，队列和优先级队。栈是标准的栈，使用时要用头文件。队也是标准的，使用时要用头文件。所谓适配器并不独立，它依附在一个顺序容器上。如要声明一个用矢量实现的字符型堆栈，可使用如下声明： stack sk;,优先级队列（priority_queue）适配器实现优先级队列。元素插入是自动按优

28、先级顺序插入，使最高优先级元素首先从优先级队列中取出。优先级队列（priority_queue）的每个常用操作都实现为内联函数，调用基础容器的相应函数时，可避免二次函数调用的开销。常用矢量为基础容器。缺省情况下priority_queue实现时用vector为基础数据结构。,然后它就可以象顺序容器一样使用。但是它没有自己的构造和析构函数，它使用其实现类（如vector）的构造和析构函数。就象一个仪器加了一个适配器增加了某些功能一样。队列（queue）缺省用deque为基础，栈（stack）可用vector或deque为基础。,11.5 容器适配器,【例11.5】优先级队列类演示，头文件用，优先

29、级用数表示，数值越大优先级越高。 #include #include #include using namespace std; void main() priority_queue prioque; /实例化存放int值的优先级队列，并用deque作为基础数据结构 prioque.push(7); /压入优先级队列 prioque.push(12); prioque.push(9); prioque.push(18); cout从优先级队列中弹出endl; while(!prioque.empty() coutprioque.top()t; /取最高优先级数据 prioque.pop();

30、/弹出最高优先级数据 coutendl; 输出结果为：从优先级队列中弹出：18 12 9 7,11.6 泛型算法与函数对象,算法表现为一系列的函数模板，它们是STL中最类似于传统函数库的部分。它们不是作为预先编译好的对象模块组成的可链接库来提供。它们完整定义在STL头文件中。使用者可以用很多方式来特化每一个模板函数，大大提高了它作为通用型程序组件的适用性。一般这些函数模板都使用迭代子作为它的参数和返回值，以此在容器（序列）上进行各种操作。如每个容器都可使用find()算法。,11.6.1 函数对象,11.6.2 泛型算法,11.6.1 函数对象,在C+中，为了使程序的安全性更好，采用“引用”来

31、代替指针作为函数的参数或返回值。在C+的泛型算法中类似地采用了“函数对象”（function object）来代替函数指针。函数对象是一个类，它重载了函数调用操作符（operator()）。该操作符封装了应该被实现为一个函数的操作。典型情况下，函数对象被作为实参传递给泛型算法。和“引用”一样，“函数对象”独立使用比较少。函数对象亦称拟函数对象（function_like object）和函子（functor）,每个泛型算法（generic algorithm）的实现都独立于单独的容器类型，它消除了算法的类型依赖性。,【例11.6】求和函数对象的定义和测试。 函数对象是一个类，它重载了调用操作符

32、“()”。使用方法与类模板相同： #include templateclass Sum T res; public: Sum(T i=0):res(i) /构造函数,即sum(T i=0)res=i; T operator()(T x)res+=x;return res; /累加，重载的调用操作符() T result() const return res; ;,11.6.1 函数对象,template T Func1(FuncObject fob,const T /函数对象标准用法，未实现累加 ,注意Sum仅能实例化为有限种类型：整型、实型、字符型等等。,11.6.1 函数对象,函数对象与函

33、数指针相比较有三个优点：第一，函数指针是间接引用，不能作为内联函数，而函数对象可以，这样速度更快；第二，函数对象可以拥有任意数量的额外数据，用这些数据可以用来缓冲当前数据和结果，提高运行质量，当然多数情况下不一定使用，上例中res就是一个额外数据；第三，编译时对函数对象作类型检查。,下面给出采用函数对象作为“数值比较算法”的求序列中最小值的函数模板： template const Type 例中Comp为比较函数对象类，对不同的数据类型，可以定义不同的函数对象。,11.6.1 函数对象,预定义函数对象分为算术、关系和逻辑操作。每个对象都是一个类模板，其中操作数类型作为模板参数。使用时要包含头文

34、件： #include 以加法为例，讨论名为plus的类模板，对整数的用法实例如下： plusintAdd; int ival1=30,ival2=15; int sum=intAdd(ival1,ival2);/等效于:sum=ival1+inval2,函数对象有多种来源 1. 标准库预定义的一组算术，关系和逻辑函数对象； 2. 预定义的一组函数适配器，允许对预定义的函数对象进行特殊化或扩展； 3. 自定义函数对象。,函数对象主要是作为泛型算法的实参使用，通常用来改变缺省的操作，比如在【例11.3】中有 sort(vec.begin(),vec.end(),greater(); 这就是把整数

35、的大于关系函数对象作为实参，得降序排列。如果是字符串，则有： sort(svec.begin(),svec.end(),greater(); 只要改一下参数就又可用于字符串的排序。,11.6.1 函数对象,greater的 比较算法在内置类型int，字符串类string中定义。譬如可以自定义整数类Int，其中重载了“”运算符： class Int public: Int(int ival=0):_val(ival) int operator-()return -_val; /负数符号重载 int operator%(int ival)return _val%ival; /求余符号重载 bool

36、 operator(int ival)return _valival; /小于符号重载 bool operator!()return _val=0; /逻辑非符号重载 private: int _val; ; 每个类对象都可以作为有名或无名对象传递给函数，同时也把所需重载的算法传递过去了。,11.6.1 函数对象,下面给出各种预定义的函数对象及其使用方法：参数和返回值。 为方便说明，定义以下变量（对象）： vectorsvec; string sval1,sval2,sres; complex cval1,cval2,cres; int ival1,ival2,ires; Int Ival1,

37、Ival2,Ires; double dval1,dval2,dres; 同时为了用实例来说明使用方法，再定义一个可用单参数函数对象(一元函数对象)的函数模板和一个可用双参数函数对象（二元函数对象）的函数模板： template Type UnaryFunc(FuncObjectfob,const Type,11.6.1 函数对象,算术函数对象： 加法：plus plusintPlus; ires=intPlus(ival1,ival2); dres=BinaryFunc(plus(),dval1,dval2); sres=BinaryFunc(plus(),sval1,sval2); 减法：

38、minus /同加法 乘法：multiplies /不能用串，可用于复数和浮点数等 multiplies intMulti;ires= intMulti(ival1,ival2); cres=BinaryFunc(multiplies(),cal1,cal2); dres=BinaryFunc(multiplies(),dval1,dval2); 除法：divides /同乘法 求余：modulus /不能用于复数,浮点数,只能用于整数 modulusIntModulus; /Int 自定义类型 Ires=IntModulus(Ival1,Ival2); ires=BinaryFunc(mod

39、ulus(),ival1,ival2); 取反：negate /同取余,但为单参数 ires=UnaryFunc(negate(),Ival1);,11.6.1 函数对象,逻辑函数对象，这里Type必须支持逻辑运算，有两个参数。 逻辑与：logical_and /对应& 逻辑或：logical_or /对应| 逻辑非：logical_not /对应!,关系函数对象，它们的返回值为布尔量，两个参数，第一参数和第二参数相比： 等于：equal_to 不等于：not_equal_to 大于：great 大于等于：great_equal 小于：less 小于等于：less_equal,返回布尔值的函数

40、对象称为谓词（predicate），默认的二进制谓词是小于比较操作符“”，所以默认的排序方式都是升序排列，它采用小于比较形式。,11.6.1 函数对象,和容器类一样，函数对象也可以由函数适配器来特殊化或扩展一元（单参数）或二元（双参数）函数对象： 1绑定器（binder）：把二元函数对象中的一个参数固定（绑定），使之转为一元函数，C+标准库提供两种预定义的binder适配器：bind1st和bind2nd，分别绑定了第一或第二个参数。 2取反器（negator）：把函数对象的值翻转的适配器，如原来为小于，用了它后就变成了大于。C+标准库也提供了两种negator适配器：not1和not2。no

41、t1用于一元预定义函数对象；not2用于二元预定义函数对象。,11.6.2 泛型算法,在C+标准库中给出了70余种算法，泛型算法函数名都加有后缀，这些后缀的意思如下： _if表示函数采用的操作是在元素上，而不是对元素的值本身进行操作。如find_if算法表示查找一些值满足函数指定条件的元素，而find查找特定的值。 _copy表示算法不仅操作元素的值，而且还把修改的值复制到一个目标范围中。reverser算法颠倒范围中元素的排列顺序，而reverse_copy算法同时把结果复制到目标范围中。 其它的后缀从英文意思上立即可以认出其意义，对照附录C,*在泛型算法中有一种习惯用语，不说满足某条件的元素，而讲满足指定二进制谓词规则的元素，因为谓词是返回布尔值的函数对象，满足则返回true，即与满足指定条件是同样意思。,11.6.2 泛型算法,其次我们介绍泛型算法的构造与使用方法。所有泛型算法的前两个实参是一对iterator，通常称为first和last，它们标出要操作的容器或内置数组中的元素范围。元素的范围，包括first，但不包含last的左闭合区间。即： first,last) 当first=last成立，则范围为空。 对it