第13章 标准模板库(STL)

第13章标准模板库（STL）•STL，即StandardTemplateLibrary，不是面向对象的编程，而是一种新的编程模式：泛型编程（GenericProgramming）。STL是C++标准库的组成部分，STL是很庞大复杂的系统，单单就STL就可写出厚达千页的技术书籍，所以，本章不可能做到面面俱到，重点在于介绍泛型编程的思想和本质，介绍一些常用的方法，为初学者学习STL提供一些感性认识，起到抛砖引玉的作用。•STL是一项比较新的技术，VC6是微软公司比较老的一款编译器，其对STL的支持并不是太好，因此，在本章学习时，推荐采用较新的VC2005甚至是VC2008编译器。13.1理解STL•STL库是用摸板（template）写出来的，在第12章中也已经提及：模板是STL库的基础所在，大致来说，STL是由三部分组成的：•容器（container）•迭代器（iterator）•容器适配器（Adapter）•算法（algorithm）•容器、容器适配器和迭代器都是用类摸板实现的，迭代器用于遍历容器中的每一个元素，算法用于操作数据。13.1.1容器•如果没有STL的支持，在处理一些复杂问题时，要自行设计存储模式，如数组管理，插入删除操作等，这不但很繁琐，而且bug频出，是程序出问题最多的地方。STL运用模板类库机制，为数据存储，查找和其他操作提供了一整套方案，大大提高了程序的正确性，不仅如此，类库对常用的很多操作进行了优化处理，大大提高了程序的效率。•容器即是可容纳一些数据的模板类，STL中有vector，list，deque，set，map，multimap和multiset等容器。13.1.2适配器•适配器就是Interface(接口)，对容器、迭代器和算法进行包装，但其实质还是容器、迭代器和算法，只是不依赖于具体的标准容器、迭代器和算法类型，容器适配器可以理解为容器的模板，迭代器适配器可理解为迭代器的模板，算法适配器可理解为算法的模板。•常见的容器适配器有stack、queue和priority_queue。13.1.3迭代器•在有的专业书籍中，迭代器也称游标，可以将迭代器初步理解为广义指针，迭代器和指针功能很像，迭代器是通过重载一元的”*”和”-”来从容器中间接地返回一个值。•迭代器有5种，依次为：随机访问迭代器（RandomAccessIterator）、双向迭代器（BidirectionalIterator）、前向迭代器（ForwardIterator）、输入迭代器（InputIterator）和输出迭代器（OutputIterator），稍后会有详细的介绍。13.1.4算法•STL包含了很多对容器进行处理的函数，它们的处理思路大体相同：使用迭代器来标识要处理的数据或数据段、以及结果的存放位置，有的函数还作为对象参数传递给另一个函数，实现数据的处理。13.2使用序列式容器•容器是STL的基础，容器有序列式容器（sequentialcontainer）和关联式容器（associativecontainer）之分。总体来说，序列式容器会强调元素的次序，依次维护第一个元素、第二个元素……，直到最后一个元素，面向序列式容器的操作主要是迭代操作，本节来讨论下序列式容器vector、list和deque的用法，以及序列式容器的共同操作。13.2.1序列式容器的创建和元素的访问•要使用序列式容器，必须包含相关的头文件，vector、list以及deque分别对应于：•#includevector•#includelist•#includedeque•首先看一下如何创建序列式容器的对象，大体有以下几种方式：•（1）创建空的容器，此时容器中的元素个数为0。•（2）产生特定大小的容器，，此时容器中的元素被创建，但未被显式初始化，编译器使用默认值为元素隐式初始化，像int、float和double等内建的数据类型会被初始化为0，对于类对象元素，将调用其无参构造函数（用户定义的或编译器缺省提供的）或每个参数都有默认值的构造函数。•（3）在（2）的基础上更进一步，创建特定大小的容器，并且为其中的每个元素指定初始值，此时在元素多少的参数后增加一个参数。•（4）根据已有同类型的容器创建新容器，并将其中的元素完全复制过来，设obV1、obL1和obD1都是现成的容器，里面存储的数据均为int型，则可用下述命令创建新容器。•（5）通过一对迭代器（可暂时理解为指针），以使编译器决定元素的个数和出值，这对迭代器用以标识一组元素区间。13.2.2所有容器都支持的特征•中，“obL.begin()”返回的是指向容器第一个元素的迭代器，这是所有容器（容器和容器适配器）都支持的特征，此外，还有如所示的所有容器都支持的特征，其中ob、ob1和ob2是容器对象名：13.2.3序列式容器中元素的插入和删除•在普通数组中，元素的插入和删除是件很繁琐的事情，但在序列式容器中，只要调用操作函数，所有的事情都由STL类库自动完成，而且容器对象都能随着元素的插入和删除自动地增大或缩小。•在创建数组时，需要指定元素的个数以帮助编译器开辟所需内存区域，而在创建容器对象时不必指明容器对象的最大容量，因为由STL类库管理的容器对象内存是动态的。•（1）push_back(t)和pop_back(void)•（2）push_front(t)和pop_front(void)•（3）front(void)和back(void)•（4）insert插入操作•（5）erase删除操作•（6）clear操作•（6）clear操作13.2.4vector容器•介绍完vector、list以及deque的通用用法，下面分别讨论下其特别之处。首先是vector，字面翻译为向量，其用法类似于前面介绍的数组，但其功能比数组更强大。简单地说，vector是数组的类表示，它提供了自动管理内存的功能，可以动态改变vector对象的长度，并随着元素的增删而增大或缩小，提供了对元素的随机访问，和数组一样，在vector尾部添加和删除元素（push_back和pop_back）的时间是固定的，但在vector中间或头部增删元素(insert,erase)的时间和复杂度线性比于vector容器对象中元素的多少。13.2.5deque容器•deque表示双端队列（double-endedqueue），deque容器对象支持下标随机访问，在deque头部和尾部添加删除元素时的时间都是固定的，因此，如果有很多操作是针对序列的头部位置的，建议使用deque容器。但是，如果是在deque的中间进行元素的增删处理，操作的复杂度和时间正比于deque对象中元素的多少。13.2.6list容器•list类模板表示双向链表，除了首尾元素外，list容器对象中的每个元素都和前面的元素相链接。list不支持下标随机访问，只能通过迭代器双向遍历。•和vector和deque不同的是，在list的任何位置增删元素的时间都是固定的。•说明：除了上述介绍的基本操作外，序列式容器还有其它用于特定场合的成员函数操作，限于篇幅原因，本章只对STL作入门式介绍，更详细的内容可查阅相关资料。13.3使用关联式容器•关联式容器（associative）又称“联合容器”，将值（value）和关键字（keyword）成对关联，举例来说，在学生管理系统设计时，可以将学号作为关键字，起索引的目的，而将学生姓名、性别、籍贯等信息作为值与学号配对。•标准的STL提供了4种联合容器类模板：set、map、multiset和multimap，总体来说，set中仅仅包含关键字，而没有值的概念，map中存储的是“关键字――值”对，map和set中不会出现多个相同的关键字，multiset和multimap可以分别看作是对set和map的扩展，再multimap和multiset中允许相同关键字的存在。4种关联式容器都会根据指定的或默认的排列函数，以关键字为索引，对其中的元素进行排序。13.3.1set容器•要使用set，必须使用头文件包含命令“#includeset”，和前面介绍的序列式容器vector、deque和list相似，set也使用模板参数来提供要存储的值的类型：•set存储类型[,排序函数或对象]容器对象名;•第一个模板类型参数用以指定存储类型，而可选的第2个模板类型参数用来指定对关键字进行排序的函数或函数对象，关于函数对象在本章稍后章节会有介绍。在默认情况下，将使用less模板，字面意义上可理解为按从小到大进行排列。•根据set的特点，STL提供了3中创建set的方式：•创建空set容器对象，如：•setintobS;•将迭代器的区间作为参数的构造函数，如：•intsz[9]={1,2,3,4,5,6,3,5,6};•setintA(sz,sz+9);•根据已有同类型的容器创建新容器，如•setintB(A);13.3.2multiset容器•使用multiset同样需要包含头文件set，multiset的创建方式与set相同，有3种方式。multiset与set不同之处在于其允许出现相同的元素，是的修改版本：13.3.3map容器•使用map必须包括头文件map，map是一对对的“关键字――值”组合，“关键字”用于搜寻，而“值”用来表示我们要存储和取出的数据，在map容器对象中，每个关键字只能出现一次，或者说特定的关键字只能和一个值相关联。•为了方便对map和multimap进行增删处理，STL使用pairclassType1,classType2类模板将两个类型Type1和Type2存储到一个对象中，如果keyword是关键字类型，value是被存储的数据类型，那么可以用下述指令生成map容器对象的一个元素t：•pairconstkeyword,valuet(keydata,valuedata);•也可以创建pairconstkeyword,value对象的匿名对象，调用格式为：•pairconstkeyword,value(keydata,valuedata);13.3.4multimap容器•multimap与map的关系，类似于multiset与set的关系，使用multimap同样需要包含头文件map，multimap的创建方式与map相同，有3种方式。multimap与map不同之处在于其允许出现相同的元素，和几乎完全一样，不同的是将map换成了multimap，以帮助读者理解两者的不同。13.4关联式容器支持的成员函数操作•和序列式容器一样，关联式容器同样支持插入、删除及元素的查找和访问等通用操作，本节将从上述3个方面分别加以介绍。13.4.1元素的插入•几种insert函数的描述见，其中，ob代表关联式容器对象名，t对set和multiset来说，是个关键字，而对map和multimap来说，是个pair结构。13.4.2元素的删除•关联式容器支持以下4种删除元素的方式：•（1）ob.erase(keyword)•（2）voidob.erase(p)•（3）voidob.erase(q1,q2)•（4）voidclear(void)13.4.3元素的查找与访问•STL为关联式容器提供了一些元素的查找与访问成员函数操作，以方便对元素的管理，见表13.6。13.5迭代器•在本章介绍过的示例代码中，迭代器起到了很重要的作用，从前面的用法看，迭代器类似于指针，用以指示容器中的某个元素。实际上，我们使用的类内迭代器只是迭代器的一种形式，本节将详细介绍迭代器的相关知识。13.5.1理解迭代器本质•模板的引入使得函数和类定义脱离了存储类型的限制，在需要时指定即可，是一种泛化的思维观念，这使得算法独立于类型，迭代器是种更高层次的抽象，它使得算法独立于容器。•迭代器是种类型，在程序中使用的是其对象。从迭代器的层面上看，对所有类型容器元素的访问应该是等价的，因此，迭代器对象应具备以下功能