C++-STL讲解

第十一章标准模板库（STL）库（library）是一系列程序组件的集合，它们可以在不同的程序中重复使用。库函数设计的第一位的要求就是通用性，为程序员提供大量实用的库是C++的又一特色。标准模板库（StandardTemplateLibrary）是ANSI/ISOC++最有特色、最实用的部分之一。STL包含了容器类（container）、迭代子（iterator）和算法（algorithm）三个部分。第十一章标准模板库（STL）11.1标准模板库简介11.3顺序容器11.2迭代子类11.5容器适配器11.7VC++中的STL11.6泛型算法与函数对象11.4关联容器11.1标准模板库简介STL提供了一个标准化的模板化的对象容器库，包含多种数据结构及其算法，可以节省大量的时间和精力，而且程序是高质量的。容器类是管理序列的类，是容纳一组对象或对象集的对象，甚至可以包含混合的对象，包含一组不同类型的对象，称为异类容器（heterogeneouscontainer），一组相同类型的对象，称为同类容器(homogenouscontainer)。通过由容器类提供的成员函数，可以实现诸如向序列中插入元素，删除元素，查找元素等操作，这些成员函数通过返回迭代子来指定元素在序列中的位置。迭代子是面向对象版本的指针，它提供了访问容器或序列中每个对象的方法。这样就可以把算法用于容器所管理的序列。11.1标准模板库简介容器分为三大类：顺序容器（sequencecontainerorsequentialcontainer）关联容器（associativecontainer）容器适配器（containeradopter）顺序容器和关联容器称为第一类容器（first-classcontainer）。另外有四种容器称为近容器（nearcontainer）：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名字空间域（namespacestd）中，程序中必须加以说明。11.1标准模板库简介在有关数组、链表和二叉树等线性表和非线性表的讨论中，若要访问其中一个元素（结点），我们可以用下标或者指针去访问，而下标实际上也是一种指针即地址，访问时取地址的方式还有很多，一系列的访问方法都可以抽象为迭代子（iterator）。访问方法最终要归于内存地址的获得，所以说迭代子是面向对象版本的指针。迭代子与指针有许多相同之处，但迭代子保存所操作的特定容器需要的状态信息，从而实现与每种容器类型相适应的迭代子。而且有些迭代子操作在所有容器中是一致的，如++运算符总是返回容器下一个元素的迭代子，间接引用符“*”，总是表示迭代子指向的容器元素。迭代子用来将STL的各部分结合在一起。从本质上说，STL提供的所有算法都是模板，我们可以通过使用自己指定的迭代子来对这些模板实例化。迭代子可以包括指针，但又不仅是一个指针。11.1标准模板库简介STL最大的优点是提供能在各种容器中通用的算法，例如插入、删除、查找、排序等等。STL提供70种左右的标准算法。算法只是间接通过迭代子操作容器元素。算法通常返回迭代子。一个算法通常可用于多个不同的容器，所以称为泛型算法（genericalgorithm）。算法分为：１．修改容器的算法，即变化序列算法（mutating-sequencealgorithm），如copy()、remove()、replace()、swap()等。２．不修改容器的算法，即非变化序列算法（non-mutating-sequencealgorithm），如count()、find()等。３．数字型算法。11.2迭代子类C++标准库中有五种预定义迭代子，其功能最强最灵活的是随机访问迭代子。标准库定义迭代子类型说明输入（InputIterator）输出（OutputIterator）正向（ForwardIterator）双向（BidirectionalIterator）随机访问（RandomAccessIterator）从容器中读取元素。输入迭代子只能一次一个元素地向前移动（即从容器开头到容器末尾）。要重读必须从头开始。向容器写入元素。输出迭代子只能一次一个元素地向前移动。输出迭代子要重写，必须从头开始。组合输入迭代子和输出迭代子的功能，并保留在容器中的位置（作为状态信息），所以重新读写不必从头开始。组合正向迭代子功能与逆向移动功能（即从容器序列末尾到容器序列开头）。组合双向迭代子的功能，并能直接访问容器中的任意元素，即可向前或向后跳过任意个元素。表11.4迭代子类别11.2迭代子类标准库定义迭代子的层次结构，按这个层次，从上到下，功能越来越强。但不是继承！inputoutputforwardbidirectionalrandomaccess图11.1迭代子层次11.2迭代子类只有第一类容器能用迭代子遍历。表11.5给出各种不同容器所支持的迭代子类别。标准库定义的各种迭代子可进行的操作参见表11.6，容器支持的迭代子类别顺序容器vectordequelist随机访问（randomaccess）随机访问（randomaccess）双向（bidirection）关联容器setmultisetmapmultimap双向（bidirection）双向（bidirection）双向（bidirection）双向（bidirection）容器适配器stackqueuepriority_queue不支持迭代子不支持迭代子不支持迭代子11.2迭代子类下面结合find()算法讨论迭代子与泛型算法的关系。find()定义如下：templatetypenameInputIterator,typenameTInputIteratorfind(InputIteratorfirst,InputIteratorlast,countTvalue){for(;first!=last;++first)if(value==*first)returnfirst;returnlast}可见，泛型算法不直接访问容器的元素，与容器无关。元素的全部访问和遍历都通过迭代子实现。并不需要预知容器类型。find()算法也支持系统内置的数组类型：11.2迭代子类【例11.1】寻找数组元素。#includealgorithm#includeiostreamusingnamespacestd;voidmain(){intsearch_value,ia[9]={47,29,37,23,11,7,5,31,41};cout请输入需搜索的数：endl;cinsearch_value;int*presult=find(&ia[0],&ia[9],search_value);cout数值search_value(presult==&ia[9]?不存在:存在)endl;}这里a[9]数组元素并不存在，但内存地址单元存在。11.2迭代子类【例11.2】寻找vector容器元素。#includealgorithm#includevector#includeiostreamusingnamespacestd;voidmain(){intsearch_value,ia[9]={47,29,37,23,11,7,5,31,41};vectorintvec(ia,ia+9);//数据填入vectorcout请输入需搜索的数：endl;cinsearch_value;vectorint::iteratorpresult;//定义迭代子presult=find(vec.begin(),vec.end(),search_value);cout数值search_value(presult==vec.end()?不存在:存在)endl;}11.2迭代子类在iterator头文件中还定义了一些专用迭代子：反转迭代子(reverseiterator)；插入型迭代子(insertioniterator)；流迭代子(streamiterator)；流缓冲迭代子(streambufferiterator)；11.2迭代子类１．反转型迭代子（reverseiterator）把一切都颠倒过来vectorintveco;vectorint::reverse_iteratorr_iter;for(r_iter=veco.rbegin();//将r_iter指向到末元素r_iter!=veco.rend();//不等于首元素的前导r_iter++){//实际是上是递减//循环体}如果要把升序的序列改为降序的序列，只要使用反转迭代子就可以了。反转迭代子定义为随机迭代子。11.2迭代子类２．插入型迭代子（insertioniterator）：可以用输出迭代子来产生一个元素序列。可以添加元素而不必重写。有三种插入迭代子：back_insert_iteratorType是输出迭代子，用来将产生的元素添加到类型为Type的容器对象的末端。就象在一个字符串末尾加一个串（strcat()）。front_insert_iteratorType是输出迭代子，用来将产生的元素添加到容器的前端，就是，产生出来的元素以逆序方式结束于被控序列前端。insert_iteratorType,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声明方式为：i