第十部分STL简介教学课件.ppt

第十章 STL 简介,10.1 标准 C+ 库 标准的 C+ 不仅包含了全部标准 C 运行库（在原 有库的基础上做了一些必要的增补和修改，以便支持 安全类型），而且还增加了一些 C+ 自己的库。这些 新增的库比标准的 C 库功能更强，这些 C+ 库包括： 1 输入输出流库。 2 语言支持库：包含从 C 运行库继承的成分，例如： 在 和 头文件中声明了 C+ 库对 和 头文件中声明的 C 运行库所 增加的实现限制；, 在 头文件中的声明了内存动态管理功能； 在 头文件中声明了支持异常处理的功 能，例如，terminate 和 unexpected 函数等； 在 头文件中声明了用于运行时类型识 别的 RTTI (Run-time type identification) 。 3 诊断库 提供一些组件，使得 C+ 程序能够发现和 报告错误。在 中声明了标准异常类； 头文件与 C 运行库中的 的作用 相同支持断言诊断。,4 通用的实用库：该库提供的库成员既可以在编程中 被使用，又被其他 C+ 库的成员使用。这些库成员 包括 !=、= 等运算符的模板化版本，带 有 tuple（元组）模板函数的 pair 模板类，支持 STL 的一套函数模板对象和与 STL 一起使用的内存管理 函数模板对象（能使我们可以容易地修改存储分配 机制）。,5 字符串库：提供了字符串模板类 basic_string 可能是我们曾经见过的最完整的字符串处理工具。 我们在 C 中要用数行代码才能完成的工作都可以用 字符串类的一个成员函数来代替，这些函数包括 append、assign、remove、insert、replace、resize、 copy、find、 rfind、compare、substr、find_first_of、 find_last_of、find_first_not_of、find_last_not_of 等。 此外还重载了运算符 =、+=、 等使这些运算更直 观地用于字符串运算。支持国际字符集的 wstring 类 是实例化 basic_string 产生的。由于该字符串模板类 与 iostream 的无缝结合，甚至无需使用 strstream。,6 本地化库：该库用来调整字符集以便使程序能在不 同国家使用，包括货币、数字、日期、时间等。 7 容器库：主要由标准模板库 STL 的容器类组成。 8 循环子库：包括用于访问 STL 容器类的工具流及流 缓冲区。 9 算法库：所提供的算法都是模板函数，并使用循环 子来完成 STL 容器上的运算，例如： adjacent_find、random_shuffer、remove_copy、rotate、 remove、replace_copy、includes、search、sort、swap 等。,10 数字运算库：该库的目的是允许编译器的实现者在 用数字运算时充分利用低层机器结构。使得高层的 数字运算库函数可以使用这些数字运算库，以便更 高效地实现函数的运算，并且不必为每种不同的机 器都编写数字运算的实现代码。这个数字库还包括 了以 float、double 和 long double 的形式实现的高层 数字运算类。,10.2 标准模板库 STL 第六章已经论述了 C+ 中模板的强大的功能以及为 程序设计提供的重用机制和灵活性。模板是实现通用 目的的编程工具，使用模板可以方便地解决能施加于 不同类型数据的通用编程问题。C+ 的 STL 是一个功 能强大的库，它是建立在模板机制上，能够满足用户 对存储管理不同类型数据的通用容器和施加在这些容 器上的通用算法的巨大需求，并且具有完全的可移植 性。因此在寻求程序的解决方案时，应该首先在 STL 中寻求恰当的容器和算法。,STL 是一个通用性极高的编程工具，这种通用性不仅 表现在可以使用通用的容器存储和管理任意类型的数 据，更重要的是可以对不同的容器施加统一通用的算 法和操作。实现这种通用性的关键思想就是：通过引 进一个间接层对象对不同结构的数据容器进行统一的 访问操作，从而简化了对容器的操作，使得实现操作 的算法和函数通用化。这种思想是 STL 的设计原则之 一，也是软件设计中一个重要设计思想。 例10-1 是一个使用间接类 istackIter 简化对整数堆栈类 istack 进行操作的实例。,分析： 其中的 istackIter 是一个循环子类，是堆栈类 istack 的 友元类。我们可以把 istackIter 对象当作仅能与 istack 对 象协同工作的超指针，它的功能是扫视 istack，并能在 中取值。通过它简化了对整数堆栈 istack 的操作，并使 对堆栈元素的访问独立于堆栈的结构。 在 STL 中对容器访问的简化和独立就是通过循环子 实现的，循环子可以无须依据某种特定容器的数据结 构而完成对容器元素的访问，从而使得数据的存储结 构与施加于数据的操作相互独立。,这种独立性的优点使我们能够在学会了使用 STL 中 一种容器的基础上，就能很方便地掌握对 STL 的其他 容器的使用。当然，熟悉使用 STL 中处理问题的思想 和方法是需要花费一定时间的。幸运的是，使用 STL 处理问题的方法具有统一的模式，因此很容易从一种 STL 工具的使用推广到其他 STL 工具使用。 例10-2 是一个使用 int 数据类型将 STL 的 set 容器类实 例化，并创建一个 intset 的实例。,分析： set 的第一个参数是包含在这个集合中的元素类型， 第二个参数产生一个运算，用于在使用整型堆栈的 成员函数 insert 插入元素时的排序算法。 copy 函数展示了使用循环子访问整型堆栈 intset 的 功能。set 的成员函数 begin 和 end 的返回值是循环 子值。copy 函数就是使用这两个值作为它运算的开 始点和结束点，并在由它们产生的边界之间简单移 动，从而把 intset 中的元素拷贝到由第三个参数 （也是一个循环子），指定的输入输出流的确定位 置上。这样就实现了将一个 int 对象序列放到了 cout 中，并在两个 int 对象之间加入行分隔符。, copy 函数实际上可用于任何场合，它只需要通过三 个循环子来访问和传输数据即可。STL 中的其他算 法和函数也都遵循了 copy 函数的这种形式，并只须 简单地管理循环子（额外的替代间接层）。 例10-3 是使用一个自定义类 Hstring 将 STL 的 set 容器 类实例化，并创建一个文本文件中获取所有不重 复的单词的实例。 该实例与例10-2 的唯一的区别在于 set 的元素类型是 Hstring 而不是 int。被插入的词是从一个文本文件中读 入的，并用 strtok() 函数完成单词分解。其他操作与对 intset 的操作完全一样。,10.3 STL 的组成 标准模板库 STL 是由容器类模板，用于访问这些容 器的循环子类模板和可以通过循环子在这些容器上实 现的各种算法类模板以及函数类模板组成的。STL 为 这种标准算法和函数（包括用户定义的函数）借助循 环子在容器上实现的应用建立了统一的规则。 10.3.1 标准容器（Standard Containers) 标准库中定义了两种标准的容器： 1 序列容器（Sequence） 向量 vector、表 list 和双向队列 deque。,2 序列转接器容器（Sequence Adapter） 序列转接器：堆栈 stack、队列 queue 和优先级队列 priority_queue。 3 关联容器 (Associative container) 映射 map、multimap 和集合 set、multiset。 4 预定义数组、字符串类 string、数值数组类 valarray 和位集合 bitset 均可以视为容器，但不是标准容器。 标准容器的成员绝大部分都具有共同的成员名，下 面的表格中分类列出这些共同的和几乎共同的成员名 以及它们的意义。,表中各种容器所对应的表项的含义如下： 空表项 - 表示容器无此项操作。 const - 表示容器此项操作的时间复杂度为常量。 O(n) - 表示容器此项操作的时间复杂度与容器中元 素个数 n 的线性相关。 O(n)+ - 表示容器此项操作的时间复杂度与容器中 元素个数 n 线性相关并且还需要增加一些附加操作 时间花费。, O(log(n) - 表示容器此项操作的时间复杂度与容器 中元素个数 n 对数相关。 O(log(n)+ - 表示容器此项操作的时间复杂度与容器 中元素个数 n 对数相关并且还需要增加一些附加操 作时间花费。 Ran - 表示容器对应的循环子为随机访问循环子。 Bi - 表示容器对应的循环子为双向访问循环子。,1 vector 该标准容器是一个定义在 namespace std 中的模板， 该模板的原型声明在头文件 中。它的数据 结构很像一个数组，所以与其他容器相比，vector 能 非常方便和高效访问单个元素。因此，在 vector 中 提供随机访问循环子。,2 list 该标准容器是一个定义在 namespace std 中的模板， 该模板的原型声明在头文件 中。list 是一个对 容器元素的插入和删除操作进行了优化的序列。但 与 vector 和 deque 相比，对元素的下标访问操作的 低效是不能容忍的，因此 list 不提供这类操作，即不 提供随机访问循环子，而提供双向循环子。这意味 着 list 是典型的通过使用双链表实现的序列结构。除 了通用的序列操作外，list 还提供了一些特别适合 list 结构的管理操作：,template class list public: / list-specific operations: void splice(iterator pos, list / move *p from x to before pos in this list without / copying. (If pos=p|pos=+p, no change occurs.),void splice(iterator pos, list,对于 list，front 操作和 back 操作都同样高效和方便。 因此，如果希望使用 list 编写的代码演变为能应用于 多种其他容器的通用代码，则使用更具广泛适用性 的 back 操作是最好的选择。 list 元素的插入和删除操作尤为高效，所以 list 更适 合在插入和删除操作频繁的应用中使用。,3 deque 该标准容器是一个定义在 namespace std 中的模板， 该模板的原型声明在头文件 中。deque 是一 个双向队列，也是一个优化序列。在 deque 两端的 操作与 list 一样高效，对元素的下标操作的效 率又与 vector 类似，而对容器元素的插入和删除操作的效率则介于 list 和 vector 之间。,4 stack 这个容器转接器是一个定义在 namespace std 中的模板，该模板的原型声明定义在头文件 中： template class stack public: typedef Cont:allocator_type alloctor_type; typedef Cont:value_type value_type; typedef Cont:size_type size_type; explicit stack(const allocator_type,bool empty() const; size_type size() const; allocator_type get_allocator() const; value_type,5 queue 这个容器转接器是一个定义在 namespace std 中的模板，该模板的原型声明定义在头文件 中： template class queue public: typedef Cont:allocator_type alloctor_type; typedef Cont:value_type value_type; typedef Cont:size_type size_type; explicit queue(const allocator_type,bool empty() const; size_type size() const; allocator_type get_allocator() const; value_type,6 priority_queue 该容器转接器是一个定义在 namespace std 中的模板，该模板的原型声明定义在头文件 中： template , class Pred = less class priority_queue public: typedef Cont:allocator_type alloctor_type; typedef Cont:value_type value_type; typedef Cont:size_type size_type;,explicit priority_queue(const Pred,void push(const value_type,7 map 该标准关联容器是一个定义在 namespace std 中的模 板，该模板的原型声明在头文件 中。 map 是 一个元素对（关键字，映射值）序列，它提供了以 关键字为基础的快速检索。map 中的每一个关键字 必须是唯一的。map 提供双向循环子。该容器除提 供通用的容器属性和操作外，还增加了一些与 map 结构对应的特定属性和操作：,template , class A = allocator class map public: typedef Key key_type; typedef T referent_type; typedef Pred key_compare; typedef A allocator_type; typedef pair value_type; typedef A:size_type size_type; typedef A:difference_type difference_type;,typedef A:rebind:other:reference reference; typedef A:rebind:other:const_reference const_reference; typedef T0 iterator; typedef T1 const_iterator; typedef reverse_bidirectional_iterator reverse_iterator; typedef reverse_bidirectional_iterator const_reverse_iterator;,/ map operations: iterator find(const Key,8 multimap 该标准关联容器是一个定义在 namespace std 中的模 板，该模板的原型声明在头文件 中。 multimap 除了元素对的关键字不必须唯一外，其他与 map 相同。,9 set 该标准关联容器是一个定义在 namespace std 中的模 板，该模板的原型声明在头文件 中。 set 可以 被视为只有关键字而没有相关的映射值的 map，因 此 set 的用户接口也发生了微小的变化，即成员类型中没有： typedef Key value_type; typedef Cmp value_compare 操作中没有元素的下标访问操作。,10 multiset 该标准关联容器是一个定义在 namespace std 中的模 板，该模板的原型声明在头文件 中。multiset 除了元素不必须唯一外，与 set 相同。 11 string basic_string 是一个定义在 namespace std 中的模板， 该模板的原型声明在头文 中。basic_string 提 供了下标访问操作、随机访问循环字和一个容器的几乎所有的符号工具。不过 basic_string 不提供选择 字符以外的其他类型作为容器的元素类型的功能。,12 valarray valarray 是一个定义在 namespace std 中的模板，该模 板的原型声明在头文件 中。valarray 是一 个用于优化数值计算的向量，但是不能试图将它作 为一个通用容器。 valarray 提供了许多有用的特定数值操作，然而对于 标准的容器通用操作，它只提供了 size 和下标访问 操作。用于 valarray 的循环子是随机访问循环子。,13 bitset bitset 是一个定义在 namespace std 中的模板，该模板 的原型声明在头文件 中。 在系统中经常用一个标志集合（这些标志指示一些 如 good/bad, true/false 和 on/off 等双态值）来表示状 态。bitset 通过产生一个 N 位的小集合和大量的相应 的位操作为实现上述需求提供高效、方便的工具。 bitset 提供了三个版本的构造函数：,template class bitset public: / constructor: bitset(); / N zero-bits bitset(unsigned long val); / bits from val template / T is a character trait explicit bitset(const string,bitset b1; / 0000000000 bitset b2 = 0xaaaa; / 1010101010101010 bitset b3 = 0xaaaa; / 00000000000000001010101010101010 bitset b4(“1010101010“); / 1010101010 bitset b5(“10110111011110“,4); / 0111011110 bitset b6(“10110111011110“,2,8); / 0011011101 bitset b7(“n0g00d“); / invalid_argument thrown bitset b8 = “n0g00d“; / error: no char* to bitset conversion bitset 提供的操作有两类,一类是对整个集合操作而另 一类是位操作：,template class bitset public: class reference; reference operator(size_t pos); / bi bool operator(size_t pos) const; reference at(size_t pos); bool at(size_t pos) const; bitset / and,bitset,bitset 其中用于实现 bitset 集合中每个位元素的位操作的引用类 reference 的定义如下：,class reference / reference to single bit friend class bitset; reference(); / bi refer to the (i+1)th bit public: reference(); reference,10.3.2 算法和函数(Algorithm and Function Object) 容器只有被诸如获取容器大小、循环访问、复制、 排序和搜寻等基本操作支持才是真正有效的。标准模 板库提供的算法用于能满足用户对使用容器的通用和 基本的需要。 函数对象提供了一种机制，通过这种机制用户可以 定制标准算法的行为。函数对象为使用一个算法完成 对用户数据的操作提供所需要的关键信息。因此，重 要的是如何定义和使用这些函数对象。,标准模板库中的算法覆盖了大多数在容器上的操作， 例如，往返移动、排序、搜寻以及插入和删除元素 等。标准算法都是定义在 namespace std 中的模板,所有 的算法模板的原型声明在头文件 中。下面 的 7 个表中列出了各种算法模板的功能： 表1 中所列的操作用于从序列中提取元素信息或在序 列中寻找元素位置，而不修改元素值。,表2 中所列出的操作均可以用于修改序列中的元素值。,表3 中所列出的操作用于序列中元素的排序、搜索和基 于有序序列的管理。,表5 中所列出了将序列按照堆结构的操作。堆操作在状 态上仍然保持为一个序列，使得在需要的时候能够使 用序列的操作对堆的元素进行相应的操作。,表6 中的操作用于建立在比较操作上的选取序列元素。 表7 中的两种置换操作均返回布尔标志，表示序列是否 已经按字典顺序或逆序排列。,标准函数对象也是定义在 namespace std 中的模板， 所有函数对象的原型声明在头文件 中。下面 的 3 个表中列出了各种函数对象的功能：,依据表1 和表2 所列出的标准函数对象，用户可以为 自定义类定义断言运算和算术运算，并在容器的算法 中使用这些运算。,标准模板库提供了一些函数对象用于构造定制的函数 对象： Binder 类函数对象允许通过将一个参数绑定为值， 使一个双目函数对象作为单目函数对象使用。 成员函数的 Adapter 类函数对象允许将一个成员函 数作为一个算法的参数。 成员函数指针的 Adapter 类函数对象允许将一个指 向成员函数的指针作为一个算法的参数。 Negate 类函数对象允许用户表达一个断言函数的相 反含义。,算法和函数对象的使用实例： 例如对一个整数序列容器中小于指定值 n 的元素进行 排序，就可以使用算法 partition 或 stable_partition ，而 该算法所需要的断言操作函数对象可使用 less ，并使 用 Binders 类函数对象 bind2nd 将 less 的第 2 操作数绑 定为指定值 n 。例如算法 partition的调用表达式如下： partition(start, end, bind2nd(less(), n); 其中 start 和 end 是分别指示序列容器中的第一个元素 和容器边界的循环子。,10.3.3 循环子（Iterators） 循环子是将容器和算法连接在一起的黏结剂。它提 供了一个抽象的数据概念，以便算法的编写者不需要 关注所操作的数据结构的具体细节。由于循环子提供 了访问数据的标准模块，从而避免了不同的容器必须 提供自己特定的访问操作集合。与循环子的实现机制 相似，内存管理器（Allocator）的使用将容器的实现和 内存分配的具体细节分离开。,循环子是一个纯抽象。循环子是指向序列中一个元 素的指针概念的抽象，它的关键操作概念是： - “the element currently pointed to“ (referencing, represented by operator *and -), - “point to next element“ (increment, represented by operator +), and - “equality“ (represented by operator =). 例如： int* p 可以作为数组 int 的“循环子”， list:iterator 是链表容器类 list 的循环子。,使用循环子操作的序列的概念被抽象描述为： “something where we can get from the beginning to the end by using a next-element operation:“ 例如：数组 array、向量 vector、单链表 singly-link lists、 双链表 doubly-link lists、树 trees、输入 cin 和输出 cout 流等序列。每种序列都有相应种类的循环子。 循环子类和相应函数都是定义在 namespace std 中的 模板，这些循环子类模板和函数模板的原型声明在头 文件 中。,elem0,elem1,elemn-1,begin(),end(),注意，循环子没有 “null iterator” 的概念。测试循环子 是否指向一个元素是通过比较循环子是否到达序列的 end 而不应比较循环子的当前值是否为 null。下列情况 之一都会引起使用循环子访问序列失效： 循环子未初始化； 循环子所指向的容器被显式或隐式地调整了大小； 循环子所指向的容器已经撤消； 循环子指向了序列的 end。 序列的 end 可以被认为循环子指向了一个不存在的假 设元素位置：one-past-the-last element of a sequence。下 表列出了循环子的操作和种类：,循环子的不同类型，即经常提及的循环子分类符合 下面的分等级顺序：,Input,Output,Forward,Bidirectional,Random access,不同的算法需要不同类型的循环子作为参数。相同 的算法有时可以使用不同类型的循环子达到不同效率 的实现。标准模板库提供了五种类型的循环子： struct input_iterator_tag; struct output_iterator_tag ; struct forward_iterator_tag ; struct bidirectional_iterator_tag ; struct random_access_iterator_tag;,10.4 STL 的应用实例 例10-4 是一个向量容器 vector 的简单应用。 该实例中用到了 vector 的下列功能： template class vector public: void push_back(const _T,void reserve(size_type _N); size_type max_size() const; void resize(size_type _N, _T _X = _T(); size_type capacity() const; size_type size() const; iterator insert(iterator it, const T ,例10-5 是一个堆栈容器 stack 的简单应用。 该实例中用到了 stack 的下列功能： template class stack public: size_type size() const; value_type,void push(const value_type ,例10-6 集合容器 set 的简单应用。 该实例中用到了 set 的下列功能： template class set public: const_iterator lower_bound(const _K,void swap(_Myt ,例10-7 一个算法 merge 的简单应用。其中用到了下列算法的原型： template void sort(RanIt first, RanIt last); template void sort(RanIt first, RanIt last, Pred pr); template inline OutputIterator merge( InputIterator1 first1, InputIterator1 last1, InputIterator2 first2, InputIterator2 last2 OutputIterator result );,template inline OutputIterator merge( InputIterator1 first1, InputIterator1 last1, InputIterator2 first2, InputIterator2 last2, OutputIterator result, Compare compare ) ; template struct greater : public binary_function bool operator() (const T,例10-8 一个算法 random_shuffle 的简单应用。其中用到了下列算法的原型： template inline void random_shuffle(RandomAccessIterator first, RandomAccessIterator last) ; template inline void random_shuffle(RandomAccessIterator first, RandomAccessIterator last, Predicate pred) ;,template class pointer_to_unary_function : public unary_function public: explicit pointer_to_unary_function(Result (*pf)(Arg); Result operator()(const Arg x) const; ;,例10-9 一个函数模板 accumulate 的简单应用。其中用到了下列模板函数的原型： template inline _TYPE accumulate(InputIterator first, InputIterator last, _TYPE init) ; template inline _TYPE accumulate(InputIterator first, InputIterator last, _TYPE init, BinaryOperator binary_op); template ostream_iterator(ostream_type,例10-10 使用 STL 提供的容器类模板 deque 派生一个自定义集合类 StuDeque 用于存放和管理自定义类 Student 对象描述的学生信息记录。,10.5 Java 的容器 Java 的容器是按照下图所示的抽象数据类型（接 口）层次体系进行设计的。,Collection,Map,作为 Java 接口，这些数据类型只包含了方法的声 明，而不包括这些方法的任何实现。Collection 接口把 容器看作是一组对象，它并不考虑容器中的对象是否 需要保证唯一性。该接口声明了类型为 List 和 Set 的所 有容器所共有的一些方法。它们包括： add、clear、isEmpty、iterator、remove、removeAll 等。 在 Collection 接口所声明的方法中有一个特别值得注 意的方法是 toArray 。由于所有类型为 Collection 的容器 都必须实现这个方法，因为这个方法可以为所有这类 容器创建一个数组版本。,Set 是一种特殊的 Collection 容器，类似 C+ 的 set。 一个 Set 容器中的每个元素都必须是独一无二的。可 以在元素类型中定义的 equals 方法测试元素的唯一 性，例如，e1 和 e2 是一个 Set 容器中的两个元素，则 e1.equals(e2) 的结果必须返回 false。 SortedSet 是 Set 的一种特殊形式。在这种容器中， 所有的元素保持有序状态，并且通常以一棵平衡二叉 树的形式存储。至于排序所需要的比较操作，如果元 素类型定义了 compareTo 方法（要求数据类型具有一 种自然顺序），则 SortedSet 可以使用该方法作为比较 操作。或者，也可以向 SortedSet 类的构造函数提供一 个 Comparator 对象，将它作为比较操作。,List 则是一种线性容器，类似 C+ 的 vector、deque 和 list 容器。因此， List 支持“下一元素”的操作，这个 操作可以对一个 List 容器进行遍历。 List 类型的容器 允许用户准确地控制新元素的插入位置。与 Set 不同， 在一个 List 容器中可以放置重复元素。 Map ，类似于 C+ 的 map，是用于存储 对的容器，它不允许出现重复的键。C+ 的 map 总是 要求它的 对根据键的顺序进行存储。Java 提供的 Map 的一种子类型 SortedMap，也具有相同的性 质。,上图所示类型都是接口，它们必须由容器类来实 现，以便为需要存储的数据创建物理存储。下面的表 格中显示了哪些类实现了哪个接口。除了推荐的实现 类（如实现了 List 接口的 ArrayList 和 LinkedList 类）之 外，还显示了传统容器类 Vector 和 Stack（它们已经更 新，成为 Java Collection Framework 的一部分)。 ArrayList 则是一种更为现代的容器，它可以替代传统 的 Vector 。类似地，对于 Map 接口，表格中列出了被 推荐的 HashMap 和 TreeMap 的同时也列出了传统的 HashTable。,这样的容器类层次体系带来了一些编程方面的便利， 例如，可以很方便地把一个容器的内容复制到另一个 容器。这是因为实现表中第一列所示的任何接口的容 器类都必须提供一个能接受 Collection 类型对象为参数 的构造函数，例如，容器类 ArrayList 实现了 List 接口， 它的 3 个构造函数之一如下：,ArrayList( Collection c ); 假如我们有一个 Set 容器，希望对该容器执行某种操 作，但这种操作是 List 容器定义的。由于 Set 对象同时 也是一个 Collection 对象，所以可以把这个 Set 容器的 所有元素复制到一个 ArrayList 容器中，方法是调用上 面所示的那个可以接受 Collection 参数的 ArrayList 的构 造函数，然后对复制到这个 ArrayList 容器中的元素执 行我们所希望的操作。此后，如果需要，还可以把这 些在 ArrayList 容器中已经处理过的元素复制回 Set 容 器，方法是调用可以接受 Collection 参数的 Set 的构造 函数。,