第十一章标准模板库(STL 〓〓〓〓〓〓 库( library)是一系列程序组件的集合,它 们可以在不同的程序中重复使用。库函数设计的 第一位的要求就是通用性,为程序员提供大量实 用的库是C++的又一特色。 标准模板库( Standard Template Library) 是ANSI/IS0C++最有特色、最实用的部分之一。 STL包含了容器类( container)、迭代子 terator)和算法 去( algori thm )三个部分
第十一章 标准模板库（STL） 库（library）是一系列程序组件的集合，它 们可以在不同的程序中重复使用。库函数设计的 第一位的要求就是通用性，为程序员提供大量实 用的库是C++的又一特色。 标准模板库（Standard Template Library） 是ANSI/ISO C++最有特色、最实用的部分之一。 STL 包含了容器类 （ container ） 、 迭代子 （iterator）和算法（algorithm）三个部分
第十一章标准模板库(STL) 111标准模板库简介 11.5容器适配器 11.2迭代子类 1.6泛型算法与函数对象 11.3顺序容器 11.7VC++中的STL 1.4关联容器
第十一章 标准模板库（STL） 11.1 标准模板库简介 11.3 顺序容器 11.2 迭代子类 11.5 容器适配器 11.7 VC++中的STL 11.6 泛型算法与函数对象 11.4 关联容器
11.1标准模板库简介 sTL提供了一个标准化的模板化的对象容器库,包含多种数据结 构及其算法,可以节省大量的时间和精力,而且程序是高质量的。 容器类是管理序列的类,是容纳一组对象或对象集的对象,甚 至可以包含混合的对象,包含一组不同类型的对象,称为异类容器 ( heterogeneous container),一组相同类型的对象,称为同 类容器( homogenous container)。通过由容器类提供的成员函 数,可以实现诸如向序列中插入元素,删除元素,查找元素等操作, 这些成员函数通过返回迭代子来指定元素在序列中的位置。迭代子 是面向对象版本的指针,它提供了访问容器或序列中每个对象的方 法。这样就可以把算法用于容器所管理的序列。 四P四
11.1 标准模板库简介 STL提供了一个标准化的模板化的对象容器库，包含多种数据结 构及其算法，可以节省大量的时间和精力，而且程序是高质量的。 容器类是管理序列的类，是容纳一组对象或对象集的对象，甚 至可以包含混合的对象，包含一组不同类型的对象，称为异类容器 （heterogeneous container），一组相同类型的对象，称为同 类容器(homogenous container)。通过由容器类提供的成员函 数，可以实现诸如向序列中插入元素，删除元素，查找元素等操作， 这些成员函数通过返回迭代子来指定元素在序列中的位置。迭代子 是面向对象版本的指针，它提供了访问容器或序列中每个对象的方 法。这样就可以把算法用于容器所管理的序列
11.1标准模板库简介 容器分为三大类: 顺序容器( sequence container or sequential container) 关联容器( associative container) 容器适配器( container adopter) 顺序容器和关联容器称为第一类容器( first-class container)。另外有四种容器称为近容器( near container): C语言风格数组、字符串 string、操作1/0标志值的bbet和进行 高速数学矢量运算的 valarray
11.1 标准模板库简介 容器分为三大类： 顺序容器（sequence container or sequential container） 关联容器（associative container） 容器适配器（container adopter） 顺 序 容 器 和 关 联 容 器 称 为 第 一 类 容 器 （ first-class container）。另外有四种容器称为近容器（near container）： C语言风格数组、字符串string、操作1/0标志值的bitset和进行 高速数学矢量运算的valarray
11.1标准模板库简介 标准库容器类 说明 顺序容器 vector(参量) 从后面快速插入与删除,直接访问任何元素 deque(双端队列) 从前面或后面快速插入与删除,直接访问任何元素 ist(列表) 从任何地方快速插入与删除,双链表 关联容器 set(集合) 快速查找,不允许重复值 multiset(多重集合) 快速查找,允许重复值 map(映射) 对一映射,基于关键字快速查找,不允许重复值 multimap(多重映射)一对多映射,基于关键字快速查找,允许重复值 容器适配器 stack(栈) 后进先出(LIFo) queue(队列) 先进先出(FIFo) priority queue(优先级最高优先级元素总是第一个出列 队列) P四 表111标准库容器类
11.1 标准模板库简介 标准库容器类 说明 顺序容器 vector（参量） deque（双端队列） list（列表） 从后面快速插入与删除，直接访问任何元素 从前面或后面快速插入与删除，直接访问任何元素 从任何地方快速插入与删除，双链表 关联容器 set（集合） multiset（多重集合） map（映射） multimap（多重映射） 快速查找，不允许重复值 快速查找，允许重复值 一对一映射，基于关键字快速查找，不允许重复值 一对多映射，基于关键字快速查找，允许重复值 容器适配器 stack（栈） queue（队列） priority_queue（优先级 队列） 后进先出（LIFO） 先进先出（FIFO） 最高优先级元素总是第一个出列 表11.1 标准库容器类
11.1标准模板库简介 STL也使容器提供接口。许多基本操作是所 有容器都峾用的。而有些操作则适用于类似容 器的子集。可以用新的类来扩展STL。参见表 11.2。这些函数和运算符可通称为容器的接口。 各容器具体接口参见附录C 使用ST容器或容器适配器。要包含定义 该容器模板类头文件。参见表11.3。这些头文 件的内容部在std字空间域( namespace/std 中,程序中必须加以说明
11.1 标准模板库简介 STL也使容器提供接口。许多基本操作是所 有容器都适用的，而有些操作则适用于类似容 器的子集。可以用新的类来扩展STL。参见表 11.2。这些函数和运算符可通称为容器的接口。 各容器具体接口参见附录C。 使用STL容器或容器适配器，要包含定义 该容器模板类头文件。参见表11.3。这些头文 件的内容都在std名字空间域（namespace std） 中，程序中必须加以说明
111标准模板库简介回 在有关数组、链表和二叉树等线性表和非线性表的讨论中, 若要访问其中一个元素(结点),我们可以用下标或者指针去访 问,而下标实际上也是一种指针即地址,访问时取地址的方式还 有很多,一系列的访问方法都可以抽象为迭代子( iterator)。访 问方法最终要归于内存地址的获得,所以说 迭代子与指针有许多相同之处,但代子保存所操作 从而实现与每种容器类型相适应的迭代子 而且有些迭代子操作在所有容器中是一致的,如++运算符总是返 回容器下一个元素的迭代子,间接引用符“*”,总是表示迭代子 指向的容器元素。 迭代子用来将STL的各部分结合在一起。从本质上说,STL提 供的所有算法都是模板,我们可以通过使用自己指定的迭代子来 对这些模板实例化。迭代子可以包括指针,但又不仅是一个指针
11.1 标准模板库简介 在有关数组、链表和二叉树等线性表和非线性表的讨论中， 若要访问其中一个元素（结点），我们可以用下标或者指针去访 问，而下标实际上也是一种指针即地址，访问时取地址的方式还 有很多，一系列的访问方法都可以抽象为迭代子（iterator）。访 问方法最终要归于内存地址的获得，所以说迭代子是面向对象版 本的指针。 迭代子与指针有许多相同之处，但迭代子保存所操作的特定 容器需要的状态信息，从而实现与每种容器类型相适应的迭代子。 而且有些迭代子操作在所有容器中是一致的，如++运算符总是返 回容器下一个元素的迭代子，间接引用符“*”，总是表示迭代子 指向的容器元素。 迭代子用来将STL的各部分结合在一起。从本质上说，STL提 供的所有算法都是模板，我们可以通过使用自己指定的迭代子来 对这些模板实例化。迭代子可以包括指针，但又不仅是一个指针
11.1标准模板库简介 sTL最大的优点是提供能在各种容器中通用的算法,例如插入 删除、查找、排序等等。 STL提供70种左右的标准算法。算法只是间接通过迭代子操作 容器元素。 算法通常返回迭代子。一个算法通常可用于多个不同的容器, 所以称为泛型算法( generic algorithm)。 算法分为: 1.修改容器的算法,即变化序列算法( mutating-sequence algorithn),如 copy、 remove()、 replace(、 swapo等 2.不修改容器的算法,即非变化序列算法(non- mutating sequence algorithm),如 counto、 findo等。 3.数字型算法
11.1 标准模板库简介 STL最大的优点是提供能在各种容器中通用的算法，例如插入、 删除、查找、排序等等。 STL提供70种左右的标准算法。算法只是间接通过迭代子操作 容器元素。 算法通常返回迭代子。一个算法通常可用于多个不同的容器， 所以称为泛型算法（generic algorithm）。 算法分为： １．修改容器的算法，即变化序列算法（mutating-sequence algorithm），如copy()、remove()、replace()、swap()等。 ２．不修改容器的算法，即非变化序列算法（non-mutatingsequence algorithm），如count()、find()等。 ３．数字型算法
11.2选代子类 C++标准库中有五种预定义迭代子,其功能最强最 灵活的是随机访问迭代子。 标准库定义迭代子类型 说明 输入( Inputiterator) 从容器中读取元素。输入迭代子只能一次一个元素地向前移动 (即从容器开头到容器末尾)。要重读必须从头开始 输出( OutputIterator) 向容器写入元素。输出迭代子只能一次一个元素地向前移动。 输出迭代子要重写,必须从头开始。 正向( ForwardIterator) 组合输入迭代子和输出迭代子的功能,并保留在容器中的位置 (作为状态信息),所以重新读写不必从头开始 双向( BidirectionalIterator)组合正向迭代子功能与逆向移动功能(即从容器序列末尾到容 器序列开头) 随机访问 组合双向迭代子的功能,并能直接访问容器中的任意元素,即 RandomAccessiterator 可向前或向后跳过任意个元素。 表114迭代子类别 四P四
11.2 迭代子类 C++标准库中有五种预定义迭代子，其功能最强最 灵活的是随机访问迭代子。 标准库定义迭代子类型 说明 输入（InputIterator） 输出（OutputIterator） 正向（ForwardIterator） 双向（BidirectionalIterator） 随机访问 （RandomAccessIterator） 从容器中读取元素。输入迭代子只能一次一个元素地向前移动 （即从容器开头到容器末尾）。要重读必须从头开始。 向容器写入元素。输出迭代子只能一次一个元素地向前移动。 输出迭代子要重写，必须从头开始。 组合输入迭代子和输出迭代子的功能，并保留在容器中的位置 （作为状态信息），所以重新读写不必从头开始。 组合正向迭代子功能与逆向移动功能（即从容器序列末尾到容 器序列开头）。 组合双向迭代子的功能，并能直接访问容器中的任意元素，即 可向前或向后跳过任意个元素。 表11.4 迭代子类别
11.2选代子类 标准库定义迭代子的层次结构,按这个层次,从上到 下,功能越来越强。但不是继承! Input output forward bidirectional random access 图111迭代子层次
11.2 迭代子类 标准库定义迭代子的层次结构，按这个层次，从上到 下，功能越来越强。但不是继承！ input output forward bidirectional random access 图11.1 迭代子层次