第6章__C++标准模块库(STL)及其程序设计

第6章C++标准模块库(STL)及其程序设计第6章C++标准模块库(STL)及其程序设计6.1STL简介6.2vectors6.3STL与模板6.4迭代器6.5算法6.6容器6.7总结第6章C++标准模块库(STL)及其程序设计6.1STL简介由于C/C++和MicrosoftWindows控制的环境的声望不断扩大，许多第三方销售商以提供例行程序的方式发展极其有利可图的产品，这些库被设计用来存储和处理数据。为了继续维护C/C++的生存能力，使其成为值得选择的程序设计语言，ANSI/ISOC++通过严格控制C/C++语言和正规定义，使其不断发展，并增加了定义这些库的一个新方法，即标准模板库STL。第6章C++标准模块库(STL)及其程序设计6.1.1初识STL简而言之，STL封装了C/C++的原始能力，再加上数据结构中讲的先进高效的算法，绑定成了一个简单实用的形式。可以将STL看作一个可扩充的框架，其中包含一些组件，如语言支持、诊断程序、通用工具、字符串、本地化、容器、迭代符、算法、数值量和输入/输出。其中，容器、迭代符、算法是STL的核心。第6章C++标准模块库(STL)及其程序设计6.1.2STL和HP公司STL是由HP公司的AlexanderStepanov和MengLee开发的，STL被期望成为保存和处理数据的一个标准方法。主要编译器销售商正开始将STL结合到其产品中。STL不只是作为一个次要的部分添加到世界上最流行的程序设计语言中，它代表着一种革命性和能力。STL为C++程序设计语言带来一组成熟得使人惊奇的类属容器和算法，为C/C++增加了新的一面。第6章C++标准模块库(STL)及其程序设计6.1.3大众化的STL从类属类到模板，然后再到最好的跨平台、可移植的标准模板STL，是一个越来越方便程序员的过程。STL越来越大众化。第6章C++标准模块库(STL)及其程序设计6.1.4STL总览尽管STL的规模很大，并且其语法初看上去有些令人生畏，但实际上一旦理解其构造以及使用的元素，STL是很容易使用的。STL的核心是三个基础项，它们分别称为容器(Container)、算法(Algoithm)和迭代器(Iterator)。这些库一起工作，可以以一种可移植的格式产生常用算法的解决方案，比如创建数组、元素插入/删除、排序和元素输出。STL甚至还进一步提供了内部清晰、无缝、高效的输入/输出流(Iostream)集成和异常处理。第6章C++标准模块库(STL)及其程序设计6.1.5STL基本组件在概念上，STL包含三个分开的算法问题求解工具，这三个最重要的部分是容器、算法和迭代器。容器是数据在内存中的组织方法，例如数组、堆栈、队列、链表或二叉树。然而，还有许多其他种类的容器，STL包括那些最有用的容器。STL容器是用模板类实现的，因此可以容易地定制它们以得到不同类型的容器。第6章C++标准模块库(STL)及其程序设计所有的容器有共同的管理成员函数，在其模板中定义insert()、erase()、begin()、end()、size()、capacity()等，各容器有支持其自身需要的成员函数。算法是应用在容器上以各种方法处理其内容的行为或能力。例如，有对容器内容排序、复制、检索和合并的算法。在STL中，算法是由模板函数表现的，这些函数不是容器类的成员函数，而是独立的函数。的确，STL的令人吃惊的特点之一就是其算法如此通用，不仅可以将其用于STL容器，而且可以用于普通的C++数组或任何其他应用程序指定的容器。第6章C++标准模块库(STL)及其程序设计一组标准的算法为容器中的对象提供了检索、复制、排序、变换和数值操作功能。同一算法可用来为所有的对象类型的所有容器执行某一项特别的操作。一旦选定一种容器类型和数据行为，那么下面惟一要做的是用迭代器使其相互作用。可以把迭代器看作一个指向容器中元素的普通指针，可以像递增一个指针那样递增迭代器，使其依次指向容器中每一个后继的元素。迭代器是STL的一个关键部分，因为它将算法和容器连在一起。第6章C++标准模块库(STL)及其程序设计6.1.6其他STL组件除了容器、算法和迭代器之外，STL还定义了另外几种组件：(1)分配算符：为单个容器管理内存分配。(2)谓词：它们在本质上是一元或二元的，即其作用于一个或两个操作数并总是返回“真”或“假”。(3)比较函数：一种独特的二元谓词，比较两个元素并只在第一个参数小于第二个时返回“真”。(4)函数对象：包括加、减、乘、除、取模、取反、等于、不等于、大于、大于或等于、小于、小于或等于、逻辑与、逻辑或以及逻辑非。第6章C++标准模块库(STL)及其程序设计6.1.7完整的STL程序包现将STL的结构组件在逻辑上归纳为以下3类。(1)STL头文件可以分成三个主要的组织概念：①容器是支持普通数据组织方法的模板类，包括deque、list、map、multimap、queue、set、stack和vector。②算法是对对象序列执行普通操作的模板函数，包括algotithm、function和numeric。③迭代器是把算法和容器粘在一起的黏合剂，包括iterator、memoty和utility。第6章C++标准模块库(STL)及其程序设计(2)输入/输出包括以下各项内容的组件：①输入/输出流的向前声明iosfwd；②预定义输入/输出流对象iostream；③基输入/输出流类ios；④流缓冲streambuf；⑤流格式和操纵器iosmanip、stream和ostream；⑥字符串流sstream；⑦文件流fstream。(3)其余标准C++头文件包括语言支持、诊断、字符串、文化语言等组件。第6章C++标准模块库(STL)及其程序设计①语言支持包括：●在整个cstddef库中使用的普通类型定义的组件；●预定义类型limits、cfloat和climits的特征；●支持C++程序开始和结束的函数cstdlib；●对动态内存管理的支持new；●对动态类型标识符的支持typeinfo；●对异常处理的支持exception；●其他运行时的支持cstdarg、ctime、csetlmp和csignal。第6章C++标准模块库(STL)及其程序设计②诊断包括以下各项内容的组件：●报告几种异常情况stdexcept；●用文件证明程序断言cassert；●错误数字代码的全局变量cerrno。③字符串包括以下各项内容的组件：●字符串类string；●以NULL结尾的顺序工具cctype、cwctype和cwchar。④文化语言组件包括字符分类和字符串校对，数字、货币和日期/时间的格式和分析，以及消息检索的国际化支持，这可以使用locale和clocale组件。第6章C++标准模块库(STL)及其程序设计6.2vectors6.2.1vector程序实例让我们先看一个具体的例子，以此对容器、迭代器和算法有一些感性的认识，然后再逐步介绍STL。#includeiostream#includevector#includeiterator第6章C++标准模块库(STL)及其程序设计#includealgorithm#includefunctionalusingnamespacestd;intmain(){vectorintivec;coutsize=ivec.size()endl;ivec.push_back(1);ivec.push_back(5);第6章C++标准模块库(STL)及其程序设计ivec.push_back(9);ivec.push_back(3);ivec.push_back(7);coutsize=ivec.size()endl;vectorint::iteratorite;for(ite=ivec.begin();ite!=ivec.end();++ite)cout*ite'';coutendl;第6章C++标准模块库(STL)及其程序设计ite=find(ivec.begin(),ivec.end(),9);if(ite!=0)ivec.insert(ite,11);coutsize=ivec.size()endl;cout*ite'';for(ite=ivec.begin();ite!=ivec.end();++ite)cout*ite'';coutendl;第6章C++标准模块库(STL)及其程序设计ite=find(ivec.begin(),ivec.end(),3);if(ite!=0)cout*(ivec.erase(ite))endl;for(ite=ivec.begin();ite!=ivec.end();++ite)cout*ite'';coutendl;sort(ivec.begin(),ivec.end(),greaterint());for(ite=ivec.begin();ite!=ivec.end();++ite)cout*ite'';第6章C++标准模块库(STL)及其程序设计coutendl;return0;}程序的输出结果为：size=0size=515937size=61115119377151197119751第6章C++标准模块库(STL)及其程序设计STL的vector是一个简单的容器。在计算中，vector对应数组。vector表示一段连续的内存区域，每个元素被顺序存储在这段内存中。对vector的随机访问效率很高，因为每次访问离vector的起始处的位移都是固定的。但是，在不是vector末尾的任意位置插入或删除元素，效率很低。由此可见，vector类提供了与数组类似的操作，即可以创建vector对象，将一个vector对象赋给另一个vector对象，并使用[]操作符来访问vector元素。要使类成为通用的，应将它设计成模板类。这正是STL的工作，即在头文件vector中定义了一个vector模板。第6章C++标准模块库(STL)及其程序设计6.2.2初始化要创建vector模板对象，可用通常的type表示法来指出要使用的类型。在6.2.1节的程序中创建了int类型的vector对象ivec：vectorintivec;现在我们有了一个vector容器，可以使用它来装东西了。vector的成员函数push_back()把一个对象放到一个vector对象的后面。现在，对象ivec中有了5个元素，它们是1、5、9、3、7。第6章C++标准模块库(STL)及其程序设计另外，vector模板使用动态内存分配，因此可以用参数来创建vector对象，例如：#includevector#includestringusingnamespacestd;vectorintivec(5);//有5个整型元素的向量vectorstringsvec(24,tiger);//有24个字符串的向量第6章C++标准模块库(STL)及其程序设计各种STL容器模板都要接受一个可选的模板参数，该参数用于指定使用哪个分配器对象来管理内存。例如，vector模板的开头与以下代码类似：templateclassT,classAllocatorTclassvector{...}；如果省略该模板参数的值，则容器模板将默认使用allocatorT类。这个类以标准方式使用new和delete。第6章C++标准模块库(STL)及其程序设计6.2.3vector容器的方法所有的STL容器都提供了一些基本的方法，其中包括：size()——返回容器中元素的数目；swap()——交换两个容器的内容；begin()——返回一个指向