windows编程技术21STL泛型编程.doc

《windows编程技术21STL泛型编程.doc》由会员分享，可在线阅读，更多相关《windows编程技术21STL泛型编程.doc（73页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、第三篇 高级编程前两篇分别介绍了Visual C+的MFC编程和Visual C# 的.NET编程的基础内容，重点放在用户界面和图形绘制部分。Windows编程技术非常广泛和丰富，许多内容属于高级课题，例如：系统编程、上下文帮助、动态链接库、组件编程、面向方面的编程、服务器端编程、分布式编程、云计算等等。限于篇幅，本书只简单介绍：企业级应用必须的泛型编程、基于多核CPU的并行编程、商业应用所需的数据库编程和应用广泛的网络编程。本篇包含如下4章内容：l 第21章 STL泛型编程l 第22章 多线程与多核编程l 第23章 数据库编程l 第24章 网络编程第21章 STL泛型编程泛型编程（gener

2、ic programming，类属编程）是一种通过模板（template）实现同一算法源代码用于不同数据类型的软件重用方法，广泛用于数据的遍历、查询、排序、添加/删除/复制/合并等操作和处理，是数据库管理和信息系统等企业级应用不可缺少的基础技术。泛型编程理论的最早实现是Alexander Stepanov和Dave Musser于1994年设计和开发出的STL（Standard Template Library，标准模板库），它成为C+标准（1998年）的一部分。源自C+的Java（1995年）和C# （2000年）语言在创建时，为了简化语法和降低复杂度，都不约而同地抛弃了C+的模板，从而不支

3、持泛型编程。但是事实很快就证明，这样做是犯了一个非常严重的错误。所以Java于2004年9月在Java SE 5.0（JDK 1.5）中开始使用（受限的）泛型技术，C# 和.NET框架也于2005年11月在2.0版中引入了泛型编程。限于篇幅，本书只讨论标准C+中的STL泛型编程的基本内容。21.1 概述面向过程的编程重用函数的目标代码，面向对象的编程重用类和对象的目标代码，泛型编程则重用算法的源代码。传统C+的泛型编程，仅仅局限于简单的模版技术。标准C+引入了容器（container）、迭代器（iterator）、分配器（allocator）和STL等概念和内容，才真正进入泛型编程的广阔天地。

4、21.1.1 泛型编程与过程及对象编程泛型编程和面向过程以及面向对象一起，构成混合型程序设计语言C+的三种编程范式（paradigm，范例/范型）。面向过程的编程，可以将常用代码段封装在一个函数中，然后通过函数调用来达到目标代码重用的目的，是最早使用的软件重用方法。面向对象的方法，则可以通过类的继承和对象成员的使用来实现（对象的目标）代码的重用。如果需要编写一个可用于不同数据类型的算法，可以采用的方法有：l 面向过程对源代码进行复制和修改，生成不同数据类型版本的算法函数，调用时需要对数据类型进行手工的判断。l 面向对象可以在一个类中，编写多个同名函数，它们的算法一致，但是所处理数据的类型不同，

5、当然函数的输入参数类型也不同，可通过函数重载来自动调用对应数据类型版本的函数。显然，这两种方法都需编写了多个算法相同的不同函数，不能做到代码重用。它们二者之间的主要差别，只是调用的方便与否。如果采用泛型编程（例如可采用以类型作为参数的传统C+的模板技术），就可以做到源代码级的重用：l 泛型编程编写以类型作为参数的一个模板函数，在调用时再将参数实例化为具体的数据类型。注意，模版的实例化，是在编译阶段完成的，属于静态性质的方法，与C/C+的宏替代方式非常相似，但是却更为安全、更易理解、且更加高效。为了实现一个，在具有不同组织结构（如数组、链表、队列、堆栈等）、含同一类型（如char、int、flo

6、at、struct或class等）的数据或对象的集合（容器）上的，与具体数据类型无关的参数化通用算法（如排序、检索、复制、合并等）。光有模版是远远不够的，还需要能够表示这种集合的容器、能够在容器中遍历的迭代器、能够为算法和容器实现抽象存储的分配器、能够在不同容器之间进行转换的适配器、以及针对容器中数据集合的各种与具体类型无关的通用算法等。这些正是泛型编程的研究内容，也是STL要实现的目标。21.1.2 泛型编程与STL泛型编程是一种面向算法的多态技术，STL是它的一种具体实现。1泛型编程在计算机科学中，泛型（generic，类属）是一种允许一个值取不同数据类型（所谓多态）的技术，强调使用这种技

7、术的编程风格被称为泛型编程。泛型编程研究对软件组件的系统化组织，目标是推出一种针对算法、数据结构和内存分配机制的分类方法，以及其他能够带来高度可重用性、模块化和可用性的软件工具。与针对问题和数据的面向对象的方法不同，泛型编程中强调的是算法。是一类通用的参数化算法，它们对各种数据类型和各种数据结构都能以相同的方式进行工作，从而实现源代码级的软件重用。例如，不管（容器）是数组、队列、链表、还是堆栈，不管里面的元素（类型）是字符、整数、浮点数、还是对象，都可以使用同样的（迭代器）方法来遍历容器内的所有元素、获取指定元素的值、添加或删除元素，从而实现排序、检索、复制、合并等各种操作和算法。泛型编程的通

8、用化算法，是建立在各种抽象化基础之上的：利用参数化模版来达到数据类型的抽象化、利用容器和迭代器来达到数据结构的抽象化、利用分配器和适配器来达到存储分配和转换接口的抽象化。2STLSTL（Standard Template Library，标准模板库）是泛型编程思想的实际体现和具体实现，它是一种为泛型组件建立大型标准库的可扩展架构。STL本身，与面向对象无关，也与具体的程序设计语言无关。STL的目标是，在不损失效率的基础上，进行抽象。这里的不损失效率，是指尽最大努力来保证其所有的泛型算法是最优的，并且和手工为具体类型编写的代码具有同样的运行效率。抽象的基础是数学逻辑和冯诺依曼计算模型（存储程序体

9、系结构）。如果用数学语言来描述，STL的本质就是：不同的数据结构，对应于不同的地址代数结构、以及不同的地址连接方式。从数据结构的一个地址，转向下一个地址的一些列操作，就对应于迭代器。在数据结构中添加和删除地址的操作，就对应于容器。STL将容器看作是结构的泛化，它们都拥有成员，可以描述整体和局部这一现实世界事物的关键属性。STL使用了赋值的算法，要求采用面向值的语义。STL还假定对容器中的数据和对象，定义了全序。STL的主要内容是容器、泛型算法、迭代器、函数对象、分配器和适配器等6种组件。在标准C+中，STL是作为C+标准库的一部分而出现的。作为STL的基础的模板，则是C+语法的一部分。3历史泛

10、型程序最早出现1970年代的CLU和Ada语言中，后来被许多基于对象和面向对象的语言所采用，包括BETA、C+、D和Eiffel等。1993年C+在3.0版中引入的模版技术就属于泛型编程的范畴，1994年7月ANSI/ISO C+标准委员会通过的STL，更是泛型编程的集大成者，它已被纳入1998年9月推出的C+国际标准之中。Visual C+从2005版开始，全面支持C+的1998年和2003年国际标准，当然也包括STL泛型编程。Java于2004年9月在Java SE 5.0（JDK 1.5）中开始使用泛型技术，并且因此将从JDK 1.21.4一直使用的Java 2改名为Java 5，但是为

11、了在语法、类库和字节码上与传统的Java 2兼容，Java中的泛型做出了很多牺牲，包括类型信息被擦除。所以Java中的泛型是一种受限的非完整泛型。微软于2005年11月在.NET框架2.0版、C# 2.0和Visual Basic 2005中也于引入了泛型编程，并在2007年11月推出的.NET框架3.5版中又增加了对STL的支持。David Musser Alexander Stepanov1971年，美国计算机科学家David Musser首先提出并推广了泛型编程的理论，但是主要局限于软件开发和计算机代数领域。1979年，苏联籍的美国计算机科学家Alexander Stepanov开始研究

12、泛型编程，1987年他与David Musser一道，开发出Ada的泛型表处理库。1990年前后，Stepanov先后在贝尔实验室和HP实验室，进行泛型编程的研究和库设计，提出了STL的体系结构。1993年11月，受贝尔实验室的Andrew Koening 的邀请，Stepanov在ANSI/ISO C+标准委员会的会议上，介绍了泛型编程的理论和他们的工作。Stepanov和Meng Lee按委员会的要求，于1994年3月提出了STL的草案。委员会提出了一些修改意见，其中最重要的是对关联容器的扩充，由Musser完成了扩充部分的实现工作。1994年7月，ANSI/ISO C+标准委员会终于通过

13、了修改后的STL方案，并将其纳入1998年推出的C+标准之中。1994年8月，HP将Stepanov和Lee等人开发的STL，在因特网上免费发布。1995年Stepanov又到SGI工作，他与Hans Boehm和Matthew H. Austern一起，为SGI开发了STL。SGI也把它免费地放在了因特网上（鉴于Alexander Stepanov对STL的重大贡献，他被誉为STL之父。21.2 容器容器（container）是装有其他对象的对象。容器里面的对象必须是同一类型，该类型必须是可拷贝构造和可赋值的，包括内置的基本数据类型和带有公用拷贝构造函数和赋值操作符的类。典型的容器有队列、链

14、表和向量等。在标准C+中，容器一般用模版类来表示。不过STL不是面向对象的技术，不强调类的层次结构，而是以效率和实用作为追求的目标。所以在STL并没有一个通用的容器类，各种具体的容器也没有统一的基类。容器可以视为是数组的推广，即对象的数组（广义数组），其中的元素（对象）可以用下标（索引）来访问。容器的设计有两条准则：一是在各个容器的设计中，提供尽可能大的自由度；二是使各种容器能够向用户呈现出一个公共的界面/接口。目的是，使容器的实现能达到最佳效率，同时也使用户能写出不依赖于所使用的特定容器类型的通用代码。容器的设计通常只能满足这两条中的一条，但是STL却提供了一个同时具有通用性和执行效率的解决

15、方案。21.2.1 分类标准C+的STL框架中的主要容器有序列容器和关联容器两大类，另外两大类容器分别是容器适配器和拟容器。1序列容器序列容器（sequence container，顺序容器）将一组具有相同类型T的对象，以严格的线性形式组织在一起。序列容器可以视为数组和链表的推广。STL中的序列容器有如下3种：1） vector（向量） 提供对变长序列的快速随机访问（即对第i个元素的访问时间，是与i无关的常量），对序列末尾的插入和删除操作的时间是分摊常量；（似变长数组）（对应于vector类，定义在头文件中）。2） deque（double-ended queue，双端队列） 提供对变长序列的

16、快速随机访问，对序列头尾的插入和删除操作的时间都是分摊常量；（似双向变长数组）（对应于deque类，定义在头文件中）。3） list（表） 提供对变长序列的线性时间访问（O(N)，N为序列的当前长度），但是在序列的任意位置的插入和删除操作均为常量时间。（似双向链表）（对应于list类，定义在头文件中）。2关联容器关联容器（associative container，联合容器）的特点是（键）有序的，即元素是按预定义的键顺序（如升序）插入的。关联容器具有从基于键的集合中快速提取对象的能力，其中集合的大小在运行时是可变的。关联容器可以视为关联数组、映射或字典的推广，它们保存的都是值的对偶，给定了其中

17、的一个被称为键（key）的值，就可以快速访问与其对偶的另一个被称为映射值（mapped value）的值。STL中的关联容器有如下4种：1） set（集合） 支持唯一键值，并提供对键本身的快速检索；例如set：学号。集合关联容器，对应于set类，定义在头文件中。2） multiset（多重集合） 支持可重复键值，并提供对键本身的快速检索；例如set：姓名（可能有同名的）。多重集合关联容器，对应于multiset类，也定义在头文件中。3） map（映射/映像） 支持唯一Key类型的键值，并提供对另一个基于键的类型T的快速检索；例如map：(学号, 姓名)、(电话号码, 姓名)等。映射关联容器，对

18、应于map类，定义在头文件中。4） multimap（多重映射） 支持可重复Key类型的键值，并提供对另一个基于键的类型T的快速检索；例如map：(姓名, 地址)、(姓名, 年龄)等。多重映射关联容器，对应于multimap类，也定义在头文件中。为了改进搜索的时间，微软还在STL的VC实现中，增加了4种对应的散列（hash）关联容器类型：1） hash_set（散列集），对应于hash_set类，定义在头文件中。2） hash_multiset（散列多集），对应于hash_multiset类，也定义在头文件中。3） hash_map（散列映射），对应于hash_map类，定义在头文件中。4）

19、hash_multimap（散列多映射），对应于hash_multimap类，也定义在头文件中。3容器适配器容器适配器（container adapter）不是独立的容器，只是某种容器的变种，它提供原容器的一个专用的受限接口。特别是，容器适配器不提供迭代器。在STL中有如下3种容器适配器：1） stack（栈） 只支持top()（读取栈顶元素）、push()（在栈顶处加入新元素）和pop()（取出栈顶元素）操作（先入后出）的一种序列容器。可以是对任意一种序列容器（默认为双端队列deque）的限制实现：删除非栈操作，将原来序列容器的标准操作back()、push_back()和pop_back(

20、)重新命名为top()、push()和pop()。栈容器适配器，对应于stack类，定义在头文件中。2） queue（队列） 与stack类似，queue也是对序列容器（默认也为双端队列deque）的限制实现。与栈相比，队列也支持back()（读取队尾处的元素）和push_back()（在队尾处插入新元素）操作，但是不再支持pop_back()（取出队尾处的元素）操作。不过，队列却允许front()（读取队首处的元素）和pop_front()（取出队首处的元素）操作（前出后入）。由于矢量vector容器不支持pop_front()操作，所以不能作为队列queue的基础容器。与前后都可出入的双端

21、队列deque相比，队列queue缺少push_front()和pop_back()操作。队列容器适配器，对应于queue类，定义在头文件中。3） priority_queue（优先队列） 也是一种队列queue，不过其中的每个元素都被给定了一个优先级，用来控制元素到达队首top()的顺序。默认情况下，优先队列简单地使用运算符进行元素比较，top()返回最大的元素。注意，优先队列，并不要求其全部元素都是有序的，而只要求其第一个元素是最大的。优先队列容器适配器，对应于priority_queue类，也定义在头文件中。4拟容器拟容器（almost container，似容器）在许多情况下可视为容器

22、，但是又缺乏标准容器接口的某些方面和特性，不能与开发完全的容器进行全面互换。除了内置数组外，STL中的拟容器有如下三3种：1） string（串） 是实例化模版类basic_string的类型定义typedef（另一个常用的wstring类，则是实例化模版类basic_string的类型定义typedef）。基本串basic_string提供下标操作、随机访问迭代器和其他序列容器的几乎所有功能，但是它不像容器那样支持广泛的元素类型选择，而且它还为作为字符串使用进行了优化，所以其典型使用方式与容器有着显著差异。串拟容器，对应于string类，定义在头文件中。有关string和wstring类的更

23、详细内容，会在后面的21.6节中介绍。2） valarray（值数组） 是为数值计算而进行了优化的向量，并不是一个具有通用性的容器。valarray提供了许多有用的数值运算和常用的数学函数，但是它只提供了标准容器操作中的size()和下标操作，此外，其中元素的指针是一种随机迭代器。值数组拟容器，对应于valarray类，定义在头文件中。3） bitset（位集） 是标志位字段的扩展，它通过提供在N个二进制位的集合（下标0N-1）上的各种操作，使对标志位的运算更为方便。bitset可视为一个N位的二进制数，位取值0/1代表真假或开关，每一位从低位向高位进行编号。位集拟容器，对应于bitset类，

24、定义在头文件中。5总结比较我们将STL的各种容器及其性能罗列于表21-1中。表21-1 STL容器类型容器访问方式添加元素删除元素说明序列容器向量vector随机尾尾似变长数组双端队列deque随机头尾头尾似双向变长数组表list线形任意位置任意位置似双向链表关联容器集合set随机顺序移复唯一健多重集合multiset随机顺序移复可多健映射map随机顺序移复唯一健多重映射multimap随机顺序移复可多健容器适配器栈stack尾(栈顶)尾(栈顶)尾(栈顶)默认基deque队列queue头尾尾头默认基deque优先队列priority_queue头尾尾头默认基deque头部的值最大拟容器内置数组

25、aN随机不能不能只支持内置基本数据类型串string和wstring随机任意位置任意位置是basic_string对char和wchar_t类型的实例化值数组valarray随机不能不能适合数值计算位集bitset随机不能不能N个bool标志位其中，“移复”是指，通过对被删元素后面的元素进行前移复制，来完成删除操作。由于篇幅的限制，不能对每个容器都作详细介绍。只是从中挑选几个典型的容器，在下面的几个小节中进行具体的讲解。21.2.2 vector向量容器vector是STL中最简单且最典型的一个。它在标准C+里，是一个定义在命名空间std中的模版类（由头文件给出）。1定义namespace s

26、td / 取自C+2003标准（节选）template class T, class Allocator = allocator class vector public:/ types: 类型typedef implementation defined iterator; / 迭代器T*typedef T value_type; / 元素类型typedef Allocator allocator_type; / 分配器类型typedef std:reverse_iterator reverse_iterator; / 反向迭代器explicit vector(const Allocator&

27、= Allocator(); / 构造函数vector(); / 析构函数/ iterators:迭代器iterator begin(); / 指向首元素iterator end(); / 指向尾元素后的一个位置reverse_iterator rbegin(); / 指向反向序列的首元素reverse_iterator rend(); / 指向反向序列尾元素后的一个位置/ capacity:容量size_type size() const; / 元素个数bool empty() const; / 清空/ element access:元素访问reference operator(size_t

28、ype n); / 下标运算符重载（不带检查的访问）reference at(size_type n); / 带检查的访问reference front(); / 首元素reference back(); / 尾元素/ modifiers:修改方法/ 堆栈操作：void push_back(const T& x); / 在尾部加入元素void pop_back(); / 从尾部删除元素/ 表操作：iterator insert(iterator position, const T& x); / 在指定位置插入元素iterator erase(iterator position); / 删除指定

29、位置的元素void clear(); / 删除所有元素;/ 比较运算符重载：=、=、=、template / 相等bool operator=(const vector& x, const vector& y);template / 小于bool operator (const vector& x, const vector& y);/ specialized algorithms:专用算法template / 交换向量x与向量y的句柄void swap(vector& x, vector& y);在C+的标准库中，还专门化了一个布尔型向量的模版类（带有分配器参数）：template clas

30、s std:vector;2图书评级例下面是一个使用向量容器给图书评级的例子：/ Review.cpp#include #include #include using namespace std;struct Review / 图书评价结构string title; / 书名int rating; / 等级;bool FillReview(Review &rv);void ShowReview(const Review &rv);int main( ) vector books;Review rv;while (FillReview(rv) books.push_back(rv);cout n

31、谢谢。你的输入如下：n评级t图书n;/ 手工循环int num = books.size();for (int i = 0; i num; i+) ShowReview(booksi);cout n重复：n评级t图书n;/ 迭代器循环vector:iterator pr;for (pr = books.begin(); pr != books.end(); pr+) ShowReview(*pr);vector oldrv(books); / 使用拷贝构造函数/ 删加元素if (num 3) / 删除2个元素books.erase(books.begin()+1, books.begin()+

32、3); cout n删除后：n;for (pr = books.begin(); pr != books.end(); pr+) ShowReview(*pr);books.insert(books.begin(), oldrv.begin() + 1,oldrv.begin() + 2); / 插入1个元素cout n插入后：n;for (pr = books.begin(); pr != books.end(); pr+) ShowReview(*pr);books.swap(oldrv); / 交换向量cout n交换向量后：n;for (pr = books.begin(); pr !

33、= books.end(); pr+) ShowReview(*pr);return 0;bool FillReview(Review &rv) cout 输入书名（quit终止）：;getline(cin, rv.title);if (rv.title = quit) return false;cout rv.rating;if(!cin) return false;cin.get();return true;void ShowReview(const Review &rv) cout rv.rating t rv.title endl;可创建一个名为stl的“Visual C+/常规/空项

34、目”型项目，将上面的Review.cpp文件加入到该项目中（本章后面的例子也类似处理）。编译后运行的结果如图21-1所示（也可以使用中文书名）。图21-1 图书评级21.2.3 stackstack（堆栈）是一种容器适配器，而不是独立的容器。它只是某种序列容器的变种，它提供原容器的一个专用的受限接口。默认stack类，是对deque（双端队列）的一种限制。1定义namespace std / 取自C+2003标准中的头文件（节选）template class T, class Container = deque class stack public:typedef typename Conta

35、iner:value_type value_type; / 值类型typedef typename Container:size_type size_type; / 大小类型typedef Container container_type; / 容器类型protected:Container c; / 容器public:explicit stack(const Container& = Container(); / 构造函数bool empty() const return c.empty(); / 清空size_type size() const return c.size(); / 大小v

36、alue_type& top() return c.back(); / 读取栈顶元素const value_type& top() const return c.back(); / 读取栈顶元素void push(const value_type& x) c.push_back(x); / 压栈void pop() c.pop_back(); / 出栈;/ 比较运算符重载：当然，你也可以从对其他序列容器的限制来得到栈。2逆序输出代码行例下面是一个将代码文件的文本内容逐行压入栈顶，然后再逐行显示并弹出栈顶元素的例子，其中灰色部分为其他基容器版本的栈：/ Stack.cpp#include #in

37、clude #include #include / #include / #include using namespace std;/ Rearrange comments below to use different versions.typedef stack Stack1; / Default: deque/ typedef stackstring, vector Stack2;/ typedef stackstring, list Stack3;int main() ifstream in(Stack.cpp); Stack1 textlines; / Try the differen

38、t versions / Stack2 textlines; / Version 2 / Stack3 textlines; / Version 3 / Read file and store lines in the stack: string line; while(getline(in, line) textlines.push(line + n); / Print lines from the stack and pop them: while(!textlines.empty() cout textlines.top(); textlines.pop(); 输出结果如图21-2所示（

39、对三个不同基容器的版本，结果是一样的）。21.2.4 map映射容器map是一种关联容器，表示的是对偶（键，值）的序列。它支持唯一Key类型的键值，并提供对另一个基于键的类型T的快速检索。map还提供双向迭代器。映射容器map在标准C+中，对应于map类，被定义在头文件中。映射：键值，值 = 映射键（似f：x y，y = f(x)）。即，可以通过映射，由键来快速定位值。图21-2 逆序输出代码文件行1定义namespace std / 取自C+2003标准（节选）template class Key, class T, class Compare = less, class Allocator

40、 = allocator pair class map public: 节选/ types:类型typedef Key key_type;typedef T mapped_type;typedef pair value_type;/ map operations:映射操作iterator find(const key_type& x);pairequal_range(const key_type& x);pairequal_range(const key_type& x) const;/ 比较运算符重载：template bool operator=(const map& x, const m

41、ap& y);2pairmap容器的值类型是pair：typedef pair value_type;其中的pair是标准C+定义在头文件中的模版结构：template struct pair typedef Type1 first_type; typedef Type2 second_type Type1 first; Type2 second; pair( ); pair(const Type1& _Val1, const Type2& _Val2); template pair(const pair& _Right);3单词计数例为了显示映射容器的威力，我们举一个单词计数程序的例子。此处的单词是以白空符分隔的广义字符串。注意，我们在下面的代码中（特别是在标点符号和运算符的两边），人为增加了许多空格符：/ WordCount.cpp#include #include #include #include using namespace std ;int main ( int argc , char* argv ) typedef map WordMap ; / 定义特定的单词映射类型 typedef WordMap : iterator wmIter ; / 定义该类型的迭代器 const char* fname =