第13讲 STL

1、 STL标准模板库 主要内容主要内容泛型程序设计与标准模板库有关的概念和术语C+标准模板库中的容器迭代器标准C+库中的算法 STL标准模板库 泛型程序设计泛型程序设计 将程序写得尽可能通用 将算法从特定的数据结构中抽象出来，成为通用的 C+的模板为泛型程序设计奠定了关键的基础 STL标准模板库 什么是什么是STL2-1STL（Standard Template Library），即标准模板库，是一个高效的C+程序库。 被容纳于被容纳于C+标准程序库（标准程序库（C+ Standard Library）中，是中，是ANSI/ISO C+标准中最新的也是极具革命标准中最新的也是极具革命性的一部分。

2、性的一部分。 包含了诸多在计算机科学领域里常用的基本数据结包含了诸多在计算机科学领域里常用的基本数据结构和基本算法，为广大构和基本算法，为广大C+程序员们提供了一个可程序员们提供了一个可扩展的应用框架，高度体现了软件的可复用性。扩展的应用框架，高度体现了软件的可复用性。 STL标准模板库 什么是什么是STL2-2从逻辑层次来看，在STL中体现了泛型化程序设计的思想（generic programming） 在这种思想里，大部分基本算法被抽象，被泛化，独立于与之对应的数据结构，用于以相同或相近的方式处理各种不同情形。从实现层次看，整个STL是以一种类型参数化（type parameterized

3、）的方式实现的 基于模板(template) STL标准模板库 STL的历史的历史1971 : David R. Musser 开始倡导Generic Programming 概念1979 : Alexander Stepanov 创造STL1987 : Alex 和Musser 开发出一套Ada library? : Alex 先后在AT&T 及HP实验室以C 及C+实验大量的体系结构和算法形式。1992 : Meng Lee 加入称为另一位主要贡献者1993/11 : Alex 于ANSI/ISO C+ 会议展示1994 夏: STL 被纳入C+标准 STL标准模板库 STL组件组件Con

4、tainer(容器) 各种基本数据结构Adapter(适配器) 可改变containers或function object接口的一种组件Algorithm(算法) 各种基本算法如sort、search等Iterator(迭代器)* 连接containers和algorithmsFunction object(函数对象) *Allocator(分配器)* STL标准模板库 容器容器容器类是容纳、包含一组元素或元素集合的对象u异类容器类与同类容器类u顺序容器与关联容器七种基本容器： 向量（vector）、双端队列（deque）、列表（list）、集合（set）、多重集合（multiset）、映射（

5、map）和多重映射（multimap）标准容器的成员绝大部分都具有共同的名称 STL标准模板库 类型成员类型成员value_type元素类型allocator_type内存管理器类型size_type下标，元素计数类型difference_type循环子之间差的类型iterator循环子，相当于 value_type*const_iterator常循环子，相当于 const value_type* STL标准模板库 类型成员类型成员reverse_iterator逆序循环子，相当于 value_type*const_reverse_iterator 常逆序循环子，相当于 const value

6、_type*reference元素引用，相当于 value_type&const_reference元素常引用，相当于 const value_type&key_type关键字类型（只用于关联包容器）mapped_type映射值类型（只用于关联包容器）key_compare比较标准类型（只用于关联包容器） STL标准模板库 循环子操作循环子操作begin()指向第一个元素end()指向最后一个元素的后一个位置rbegin()指向逆序的第一个元素rend()指向逆序的最后一个元素的后一个位置访问元素操作front()访问第一个元素back()访问最后一个元素 无测试的下标访问（不用于 list）

7、at()有测试的下标访问（只用于 vector 和 deque） STL标准模板库 堆栈和队列操作堆栈和队列操作堆栈和队列操作push_back()将新元素加入到尾部pop_back()移出最后一个元素push_front()将新元素加入头部（只用于 list 和 deque）pop_front()移出第一个元素（只用于 list 和 deque） STL标准模板库 表操作表操作clear()清除所有的元素insert(p,x)将元素x加入到 p 之前insert(p,n,x)在 p 之前加入 n 个 x 的拷贝insert(p,first,last) 在 p 之前加入 区间 first:la

8、st) 中的序列erase(p)删除p处的元素erase(first,last)删除区间first, last)中的序列 STL标准模板库 其它操作其它操作size()获取元素个数empty()测试包容器是否为空max_size()最大可能的包容器的大小capacity()为向量包容器分配的空间（只用于 vector）reserve()为扩充向量包容器保留空间（只用于 vector）resize()改变包容器的大小（只用于 vector, list 和 deque） STL标准模板库 其他操作其他操作swap()交换两个包容器中的元素get_allocator()获取包容器的内存管理器的副本=

9、测试两个包容器的内容是否相等!=测试两个包容器的内容是否不同- Write:*p=*p=*p=*p=Iteration:+ -+ - + - += -=Comparison:= != != != != = = STL标准模板库 算法算法C+标准模板库中包括70多个算法 其中包括查找算法，排序算法，消除算法，记数算法，比较算法，变换算法，置换算法和容器管理等等这些算法的一个最重要的特性就是它们的统一性，并且可以广泛用于不同的对象和内置的数据类型 STL标准模板库 顺序容器顺序容器顺序容器的接口 插入方法 push_front()，push_back()，insert()，运算符“=” 删除方法

10、pop() ，erase()，clear() 迭代访问方法 使用迭代器 其他顺序容器访问方法（不修改访问方法） front()，back()，下标运算符 STL标准模板库 顺序容器顺序容器向量向量(vector)向量属于顺序容器，用于容纳不定长线性序列（即线性群体），提供对序列的快速随机访问（也称直接访问）。向量是动态结构，它的大小不固定，可以在程序运行时增加或减少。数据结构很像一个数组，所以与其他容器相比，vector 能非常方便和高效访问单个元素。头文件：#include STL标准模板库 vector的使用的使用2-1#include #include #include /包含向量容器头

11、文件using namespace std ;void main() vector A(10);int n;int primecount = 0, i, j;cout=2 as upper limit: ;cin n;Aprimecount+ = 2; STL标准模板库 vector的使用的使用2-2for(i = 3; i n; i+) if (primecount = A.size()A.resize(primecount + 10); if (i % 2 = 0)continue;j = 3; while (j i/2) Aprimecount+ = i;for (i = 0; ipri

12、mecount; i+)/输出质数coutsetw(5)Ai; if (i+1) % 10 = 0) /每输出10个数换行一次cout endl; coutendl; STL标准模板库 顺序容器顺序容器双端队列双端队列 (deque)双端队列是一种放松了访问权限的队列。元素可以从队列的两端入队和出队，也支持通过下标操作符“”进行直接访问与向量的对比： 功能上：和向量没有多少区别，功能上：和向量没有多少区别， 性能上：在双端队列起点上的插入和删除操性能上：在双端队列起点上的插入和删除操作快作快头文件：#include STL标准模板库 顺序容器顺序容器列表列表 (list)头文件：头文件：#in

13、clude 列表主要用于存放双向链表，可以从任意一端开始遍历。列表还提供了拼接（splicing）操作，将一个序列中的元素从插入到另一个序列中对比： 元素的插入和删除操作对 list 而言尤为高效 与 vector 和 deque 相比，对元素的下标访问操作的低效是不能容忍的，因此 list 不提供这类操作 STL标准模板库 list的使用的使用2-1#include #include using namespace std ;void main()list Link;/构造一个列表用于存放整数链表int i, key, item; for(i=0;i item;Link.push_front

14、(item);cout“List: ”; / 输出链表list:iterator p=Link.begin(); STL标准模板库 list的使用的使用2-2while(p!=Link.end() /输出各节点数据，直到链表尾cout *p ;p+; /使P指向下一个节点cout endl;cout key;Link.remove(key); cout List: ; / 输出链表p=Link.begin();/ 使P重新指向表头while(p!=Link.end() cout *p ;p+; / 使P指向下一个节点cout endl; STL标准模板库 如何选择顺序容器如何选择顺序容器三种成

15、员中的任何一种都无法在所有操作的性能上优于其他两种需要频繁在序列内部位置上进行插入和/或删除操作且不需要过多地在序列内部进行长距离跳转，应该选择？链表仅仅出于可动态改变大小的原因，应该选择？向量和双端队列 STL标准模板库 关联容器关联容器通过保存在数据项中的索引项，尽可能快速检索数据项STL标准库中只包含有序关联容器set、multiset、map、multimapset, multiset：数据项就是索引项。 multiset允许出现重复的索引项。map, multimap：数据项是由索引项和其他某种类型的数据组成的一对数据。 multimap允许出现重复的索引项。 STL标准模板库 关联

16、容器关联容器map增加和删除节点对迭代器的影响很小。对于迭代器来说，可以修改实值，而不能修改key自动建立Key value的对应。key 和 value可以是任意你需要的类型。 根据key值快速查找记录，查找的复杂度基本是Log(N)，如果有1000个记录，最多查找10次，1,000,000个记录，最多查找20次。 STL标准模板库 map的构造函数的构造函数使用map得包含map类所在的头文件#include map对象是模板类，需要关键字和存储对象两个模板参数：map personnel;/用int作为索引,存储string对象 STL标准模板库 map的成员函数的成员函数map类已经对

17、操作符进行了重载插入2时,先在enumMap中查找主键为2的项，没发现，然后将一个新的对象插入enumMap，键是2，值是一个空字符串，插入完成后，将字符串赋为“Two”;但是该方法会将每个值都赋为缺省值，然后再赋为显示的值，如果元素是类对象，则开销比较大。可以用以下insert()来避免开销 STL标准模板库 map注意事项注意事项u下标操作符给出了获得一个值的最简单方法： CString tmp = enumMap2;u但是,只有当map中有这个键的实例时才对，否则会自动插入一个实例，值为初始化值。u我们可以使用Find()和Count()方法来发现一个键是否存在。u查找map中是否包含某

18、个关键字条目用find()方法，传入的参数是要查找的keyu通过map对象的方法获取的iterator数据类型是一个std:pair对象，包括两个数据 iterator-first 和 iterator-second 分别代表关键字和存储的数据 STL标准模板库 从从map中删除元素中删除元素移除某个map中某个条目用erase() 该成员方法的定义如下iterator erase(iterator it); /通过一个条目对象删除iterator erase(iterator first, iterator last);/删除一个范围size_type erase(const Key& ke

19、y); /通过关键字删除enumMap.erase(1); /删掉关键字“1”对应的条目enumMap.erase(enumMap.begin(); /删掉第一个条目enumMap.erase(enumMap.begin(), enumMap.begin() + 2); /删掉起始的两个条目clear()就相当于 enumMap.erase(enumMap.begin(), enumMap.end(); STL标准模板库 map的使用的使用2-1#include #include #include using namespace std;void main()map trans_map;typ

20、edef map:value_type valType;trans_map.insert( valType( 001, grateful );trans_map.insert( valType( 002, them ); STL标准模板库 trans_map.insert( valType( 003, because );trans_map.insert( valType( 004, no );trans_map.insert( valType( 005, says );trans_map.insert( valType( 006, thanks );trans_map.insert( val

21、Type( 007, was );trans_map.insert( valType( 008, suppose ); STL标准模板库 map的使用的使用2-2map:iterator it;cout Here is our transformation map: nn;for(it=trans_map.begin();it!=trans_map.end();+it)coutkey: (*it).firsttvalue: (*it).secondn;coutFind Key:005endl;it=trans_map.find(105);if (it=trans_map.end()coutno

22、t foundendl;elsecoutkey: (*it).first tvalue: (*it).secondn; STL标准模板库 关联容器关联容器multimap multimap 除了元素对应的关键字不是唯一外，与 map 相似。 头文件：#include STL标准模板库 关联容器关联容器setset 可以被视为只有关键字而没有相关的元素值的 map，因此 set 的用户接口也发生了微小的变化：成员类型中没有： typedef Key value_type; typedef Cmp value_compare 操作中没有元素的下标访问操作头文件：#include STL标准模板库

23、关联容器关联容器multisetmultiset 除了关键字不是唯一外，与 set 相似头文件：#include STL标准模板库 标准标准C+库中的算法库中的算法算法本身是一种函数模板不可变序列算法（non-mutating algorithms）不直接修改所操作的容器内容的算法可变序列算法（mutating algorithms）可以修改它们所操作的容器的元素。算法部分主要由头文件，和组成 STL标准模板库 相关头文件相关头文件是所有STL头文件中最大的一个，它是由一大堆模版函数组成的，可以认为每个函数在很大程度上都是独立的，其中常用到的功能范围涉及到比较、交换、查找、遍历操作、复制、修改

24、、移除、反转、排序、合并等等。体积很小，只包括几个在序列上面进行简单数学运算的模板函数，包括加法和乘法在序列上的一些操作。中则定义了一些模板类，用以声明函数对象。 STL标准模板库 STL算法算法61不修改序列的操作（查找算法）for_each()对序列中的每一个元素进行操作find()在序列中寻找第一个等于指定值元素find_if()在序列中寻找指定断言的第一个匹配find_first_of()从一个序列中寻找另一个序列中的值adjacent_find()在序列中寻找与断言匹配的元素值的相邻对count()在序列中计算指定元素出现的次数count_if()在序列中计算与断言匹配的元素出现的次

25、数mismatch()寻找两个序列中第一个不相同的元素equal()如果两个序列中元素两两相等，则返回真search()寻找序列中第一个指定字串find_end()寻找序列中最后一个指定字串search_n()寻找序列中第n个等于指定值的元素 STL标准模板库 STL算法算法62修改序列的操作transform()对序列中的每一个元素施加一个操作copy()从序列的第一个元素开始复制整个序列copy_backward()从序列的最后一个元素开始复制整个序列swap()交换两个元素iter_swap()交换两个由循环子指定的元素swap_ranges()交换两个序列中的元素replace()用指

26、定新值替换序列中具有指定原值的元素replace_if()用指定新值替换序列中与指定断言匹配的元素replace_copy()复制序列并对副本执行replace操作replace_copy_if()复制序列并对副本执行replace_if操作fill()用指定值替换序列中的每一个元素值fill_n()用指定值替换序列中前n个元素值generate()用指定操作的结果替换序列中的每一个元素值 STL标准模板库 STL算法算法63修改序列的操作generate_n()用指定操作的结果替换序列中前n个元素值remove()删除序列中具有指定值的元素remove_if()删除序列中与指定断言匹配的元素

27、remove_copy()复制序列并删除副本中具有指定值的元素remove_copy_if()复制序列并删除副本中与指定断言匹配的元素unique()删除序列中相等的相邻元素unique_copy()复制序列并删除副本中相等的相邻元素reverse()倒置序列中的元素顺序reverse_copy()复制序列并将副本的元素顺序倒置rotate()旋转序列中的元素rotate_copy()复制序列并旋转副本中的元素random_shuffle()移动序列中元素到一个统一的分布状态 STL标准模板库 STL算法算法64序列排序操作sort()具有好的平均效率的排序stable_sort()维持相等元

28、素顺序的排序partial_sort()获取序列已经有序的前半部分partial_sort_copy()复制获取的序列已经有序的前半部分nth_element()将第n个元素放置在序列中适当的位置lower_bound()在序列中寻找指定值的第一次出现upper_bound()在序列中寻找第一个大于指定值的元素equal_range()在序列中寻找带有指定值的子序列binary_search()一个有序序列中是否包含具有指定值的元素merge()合并两个有序序列inplace_merge()合并两个连续的有序序列partition()将与指定断言匹配的元素放置在前面stable_partiti

29、on()将与指定断言匹配的元素放置在前面，并保留相关的顺序 STL标准模板库 STL算法算法65集合算法includes()检测一个序列是否是另一个序列的子序列set_union()创建一个有序并集set_intersection()创建一个有序的交集set_difference()在第一个序列中创建一个有序的差集 ，而不是在第二个序列中set_symmetric_difference从两个序列中创建（互不在两个序列中）元素的有序序列堆操作算法make_heap()使序列作为一个堆来使用push_heap()增加元素到堆中pop_heap()从堆中删除元素sort_heap()堆中元素排序 S

30、TL标准模板库 STL算法算法66最小和最大算法min()获取两个元素值中的较小值max()获取两个元素值中的较大值min_element()获取序列中的最小值max_element()获取序列中的最大值lexicographical_compare()判别两个序列中哪个的字典顺序在前置换算法next_permutation()逆字典顺序对序列进行一次置换prev_permutation()按字典顺序对序列进行一次置换 STL标准模板库 函数对象函数对象一个行为类似函数的对象，它可以没有参数，也可以带有若干参数，其功能是获取一个值，或者改变操作的状态。任何普通的函数和任何重载了调用运算符ope

31、rator()的类的对象都满足函数对象的特征STL中也定义了一些标准的函数对象，如果以功能划分，可以分为算术运算、关系运算、逻辑运算三大类。为了调用这些标准函数对象，需要包含头文件。 STL标准模板库 STL提供的函数对象提供的函数对象断言函数对象equal_toBinaryarg1=arg2not_equal_toBinaryarg1!=arg2greaterBinaryarg1arg2lessBinaryarg1=arg2less_equalBinaryarg1=arg2logic_andBinaryarg1&arg2logic_orBinaryarg1|arg2logic_notUnar

32、y!arg算术操作函数对象plusBinaryarg1+arg2minusBinaryarg1-arg2multipliesBinaryarg1*arg2dividesBinaryarg1/arg2modulusBinaryarg1%arg2negateUnary-arg可以自己编写一个函数作可以自己编写一个函数作为算法的参数为算法的参数 STL标准模板库 算法例子算法例子3-1#include #include #include #include #include #include using namespace std;int main()int ia = 1, 2, 3, 4, 5, 7, 9, 11 ;vector iv(ia, ia+8);/