11.1 11.1 基本数据结构知识基本数据结构知识11.2 11.2泛型程序设计与标准模板类库泛型程序设计与标准模板类库STLSTL简介简介11.3 11.3 向量向量11.4 11.4 链表类的使用链表类的使用11.5 11.5 双端队列双端队列11.6 11.6 栈与队列栈与队列11.7 11.7 集合集合第第 11 11 章章 标准模板类库标准模板类库STLSTLEvaluation only.Evaluation only. Created with Aspose.Slides for .NET 3.5 Client Profile 5.2.0.0.Created with Aspose.Slides for .NET 3.5 Client Profile 5.2.0.0. Copyright 2004-2011 Aspose Pty Ltd.Copyright 2004-2011 Aspose Pty Ltd.C+ C+语言的标准模板类库语言的标准模板类库STL(Standard Template Library)STL(Standard Template Library)已经成为一已经成为一 个标准，它是一个基于模板的群性类库，包含群体类（链表、向量、栈、个标准，它是一个基于模板的群性类库，包含群体类（链表、向量、栈、 队列、集合、映象），算法队列、集合、映象），算法( (排序、查找排序、查找) )以及迭代子以及迭代子(iterator)(iterator)。本章将着重。本章将着重 介绍介绍STLSTL的使用。的使用。实现了数组和链表，它们属于实现了数组和链表，它们属于线性群体线性群体。还有两种特殊的线性群体：。还有两种特殊的线性群体：栈和栈和 队列队列。Ele1Ele1 Ele2Ele2ElenElen入栈入栈出栈出栈栈顶栈顶栈底栈底图图栈的示意图栈的示意图栈是栈是只能从一端访问的线性群体只能从一端访问的线性群体，可以，可以 访问的这一端称访问的这一端称栈顶栈顶，另一端称，另一端称栈底栈底。对栈。对栈 顶位置的标记称为顶位置的标记称为栈顶指针栈顶指针，对栈底位置的，对栈底位置的 标记称为标记称为栈底指针栈底指针。向栈顶添加元素称为向栈顶添加元素称为“ “压入栈压入栈”(push)”(push)， 删除栈顶元素称为删除栈顶元素称为“ “弹出栈弹出栈”(pop)”(pop)。栈中元素的添加和删除操作具有栈中元素的添加和删除操作具有“ “后进先后进先 出出” ”（LIFOLIFO）的特性。的特性。【 11.1 11.1 基本数据结构知识基本数据结构知识】 Evaluation only.Evaluation only. Created with Aspose.Slides for .NET 3.5 Client Profile 5.2.0.0.Created with Aspose.Slides for .NET 3.5 Client Profile 5.2.0.0. Copyright 2004-2011 Aspose Pty Ltd.Copyright 2004-2011 Aspose Pty Ltd.有一种限定的线性数据群体叫有一种限定的线性数据群体叫双端队列双端队列，它类似于限定删除和插入操作都，它类似于限定删除和插入操作都 必须在两端进行的链表。必须在两端进行的链表。队列是一种特殊的线性群体。队列队列是一种特殊的线性群体。队列只能向一端添加元素只能向一端添加元素，从另一端删除，从另一端删除 元素的线性群体，可以添加元素的一端称元素的线性群体，可以添加元素的一端称队尾队尾，可以删除元素的一端称，可以删除元素的一端称队头队头 。对队头位置的标记称为。对队头位置的标记称为队头指针队头指针，对队尾位置的标记称为，对队尾位置的标记称为队尾指针队尾指针。 Ele1Ele1出队出队入队入队Ele2Ele2ElenElen队头队头队尾队尾非线性群体：集合和映射。非线性群体：集合和映射。集合集合由若干个元素组成，对于一个指定的元素由若干个元素组成，对于一个指定的元素 ，它或者属于该集合，或者不属于；可以对两个集合求交集和差等。，它或者属于该集合，或者不属于；可以对两个集合求交集和差等。映射映射 则类似于字典的功能，如一个身份证号码可以映射为某个确定的人，图书则类似于字典的功能，如一个身份证号码可以映射为某个确定的人，图书 馆中一本书的编号和这本书也是一个映射。馆中一本书的编号和这本书也是一个映射。向队尾添加元素称为向队尾添加元素称为“ “入队入队” ”，删除队头元素称为，删除队头元素称为“ “出队出队” ”。 队列中元素的添加和删除操作具有队列中元素的添加和删除操作具有“ “先进先出先进先出” ”（FIFOFIFO）的特性。的特性。图图队列的逻辑结构示意图队列的逻辑结构示意图Evaluation only.Evaluation only. Created with Aspose.Slides for .NET 3.5 Client Profile 5.2.0.0.Created with Aspose.Slides for .NET 3.5 Client Profile 5.2.0.0. Copyright 2004-2011 Aspose Pty Ltd.Copyright 2004-2011 Aspose Pty Ltd.11.2.111.2.1泛型程序设计泛型程序设计 将程序写得尽可能通用将程序写得尽可能通用 将算法从特定的数据结构中抽象出来，成为通用的将算法从特定的数据结构中抽象出来，成为通用的 C+C+的模板为泛型程序设计奠定了关键的基础的模板为泛型程序设计奠定了关键的基础 STLSTL是泛型程序设计的一个范例是泛型程序设计的一个范例 容器容器(container)(container) 迭代器迭代器(iterator)(iterator) 算法（算法（algorithmsalgorithms） 函数对象（函数对象（function objectfunction object）【 11.211.2泛型程序设计与标准模板类库泛型程序设计与标准模板类库STLSTL简介简介】Evaluation only.Evaluation only. Created with Aspose.Slides for .NET 3.5 Client Profile 5.2.0.0.Created with Aspose.Slides for .NET 3.5 Client Profile 5.2.0.0. Copyright 2004-2011 Aspose Pty Ltd.Copyright 2004-2011 Aspose Pty Ltd.4命名空间（命名空间（NamespaceNamespace） 一个命名空间将不同的标识符集合在一个命名作用域（一个命名空间将不同的标识符集合在一个命名作用域（ named scopenamed scope）内）内 为了解决命名冲突为了解决命名冲突 例如，声明一个命名空间例如，声明一个命名空间NSNS： namspace NS namspace NS class File;class File; void Fun ();void Fun (); 则引用标识符的方式如下，则引用标识符的方式如下， NS: File obj;NS: File obj; NS: Fun ();NS: Fun (); 没有声明命名空间的标识符都处于无名的命名空间中没有声明命名空间的标识符都处于无名的命名空间中概念和术语Evaluation only.Evaluation only. Created with Aspose.Slides for .NET 3.5 Client Profile 5.2.0.0.Created with Aspose.Slides for .NET 3.5 Client Profile 5.2.0.0. Copyright 2004-2011 Aspose Pty Ltd.Copyright 2004-2011 Aspose Pty Ltd.5命名空间（命名空间（NamespaceNamespace） 可以用可以用usingusing来指定命名空间来指定命名空间 例如，经过以下声明：例如，经过以下声明： using NS:File;using NS:File; 在当前作用域中就可以直接引用在当前作用域中就可以直接引用FileFile using namespace std;using namespace std; 命名空间命名空间stdstd中所有标识符都可直接引用中所有标识符都可直接引用 在新的在新的C+C+标准程序库中，所有标识符都声明在命名空间标准程序库中，所有标识符都声明在命名空间stdstd 中，头文件都不使用扩展名中，头文件都不使用扩展名概念和术语Evaluation only.Evaluation only. Created with Aspose.Slides for .NET 3.5 Client Profile 5.2.0.0.Created with Aspose.Slides for .NET 3.5 Client Profile 5.2.0.0. Copyright 2004-2011 Aspose Pty Ltd.Copyright 2004-2011 Aspose Pty Ltd.6容器容器 容器类是容纳、包含一组元素或元素集合的对象。容器类是容纳、包含一组元素或元素集合的对象。 异类容器类与同类容器类异类容器类与同类容器类 顺序容器与关联容器顺序容器与关联容器 七种基本容器：七种基本容器： 向量（向量（vectorvector）、双端队列（）、双端队列（dequedeque）、列表（）、列表（listlist）、集）、集 合（合（setset）、多重集合（）、多重集合（multisetmultiset）、映射（）、映射（mapmap）和多重）和多重 映射（映射（multimapmultimap）概念和术语Evaluation only.Evaluation only. Created with Aspose.Slides for .NET 3.5 Client Profile 5.2.0.0.Created with Aspose.Slides for .NET 3.5 Client Profile 5.2.0.0. Copyright 2004-2011 Aspose Pty Ltd.Copyright 2004-2011 Aspose Pty Ltd.7容器的接口容器的接口 通用容器运算符通用容器运算符 =，!=!=， ，=，。Evaluation only.Evaluation only. Created with Aspose.Slides for .NET 3.5 Client Profile 5.2.0.0.Created with Aspose.Slides for .NET 3.5 Client Profile 5.2.0.0. Copyright 2004-2011 Aspose Pty Ltd.Copyright 2004-2011 Aspose Pty Ltd.1219941994年年7 7月，月，STLSTL正式成为标准正式成为标准C+