《数据结构课件stl》由会员分享，可在线阅读，更多相关《数据结构课件stl（72页珍藏版）》请在金锄头文库上搜索。
1、C+模板与STL库介绍提纲o 1. 概论 o 2. 模板机制的介绍 o 3. STL中的基本概念 o 4. 容器概述 o 5. 迭代器 o 6. 算法简介概论o C+ 语言的核心优势之一就是便于软件的重用o C+中有两个方面体现重用： n 1. 面向对象的思想：继承和多态，标准类库n 2. 泛型程序设计(generic programming) 的思想：模板 机制，以及标准模板库 STL泛型程序设计o 泛型程序设计，简单地说就是使用模板的程序设计法。 n将一些常用的数据结构（比如链表，数组，二叉树）和算法（ 比如排序，查找）写成模板，以后则不论数据结构里放的是什 么对象，算法针对什么样的对象，
2、则都不必重新实现数据结构 ，重新编写算法。 o 标准模板库 (Standard Template Library) 就是一些常用数 据结构和算法的模板的集合。主要由 Alex Stepanov 开 发，于1998年被添加进C+标准o 有了STL，不必再从头开始编写繁多的标准数据结构和 算法，并且一样可获得非常高的性能。模板引子1.假如设计一个求两参数最大值的函数，在实践中我们可 能需要定义四个函数： int max ( int a , int b ) return ( a b ) ? a , b ; long max ( long a , long b ) return ( a b ) ? a
3、 , b ; double max ( double a , double b ) return ( a b)? a , b ; char max ( char a , char b ) return ( a b ) ? a , b ;2.这些函数几乎相同，唯一的区别就是形参类型不同3.需要事先知道有哪些类型会使用这些函数，对于未知类 型这些函数不起作用模板的概念1. 所谓模板是一种使用无类型参数来产生一系 列函数或类的机制。 2. 若一个程序的功能是对某种特定的数据类型 进行处理，则可以将所处理的数据类型说明为 参数，以便在其他数据类型的情况下使用，这 就是模板的由来。 3. 模板是以一种完
4、全通用的方法来设计函数或 类而不必预先说明将被使用的每个对象的类型 。 4. 通过模板可以产生类或函数的集合，使它们 操作不同的数据类型，从而避免需要为每一种 数据类型产生一个单独的类或函数。 模板分类o 函数模板(function template) n 是独立于类型的函数 n 可产生函数的特定版本 o 类模板(class template) n 跟类相关的模板，如vector n 可产生类对特定类型的版本，如vector7求最大值模板函数实现1.求两个数最大值，使用模板 template T max(T a , T b) return ( a b ) ? a , b; 2.template
5、 （模板函数形参表） /函数定义体 8模板工作方式o 函数模板只是说明，不能直接执行，需要实例 化为模板函数后才能执行o 在说明了一个函数模板后，当编译系统发现有 一个对应的函数调用时，将根据实参中的类型 来确认是否匹配函数模板中对应的形参，然后 生成一个重载函数。该重载函数的定义体与函 数模板的函数定义体相同，它称之为模板函数9#include template T min(T a,int n) int i; T minv=a0; for( i = 1;i ai)minv=ai; return minv; 编写一个对具有n个元素的数组a 求最小值的程序，要求 将求最小值的函数设计成函数模板。
6、void main() ina a=1,3,0,2,7,6,4,5,2;double b=1.2,-3.4,6.8,9,8;cout实际上就是个动态数组。随机存取任何元素都能在常数 时间完成。在尾端增删元素具有较佳的性能。2) deque 头文件 也是个动态数组，随机存取任何元素都能在常数时间完 成(但性能次于vector)。在两端增删元素具有较佳的性 能。3) list 头文件 双向链表，在任何位置增删元素都能在常数时间完成。 不支持随机存取。上述三种容器称为顺序容器，是因为元素的插入位置同 元素的值无关。关联容器简介o 关联式容器内的元素是排序的，插入任何元素，都按相 应的排序准则来确定其
7、位置。关联式容器的特点是在查 找时具有非常好的性能。 1) set/multiset: 头文件 set 即集合。set中不允许相同元素，multiset中允许存在相 同的元素。 2) map/multimap: 头文件 map与set的不同在于map中存放的是成对的key/value。并根据key对元素进行排序，可快速地根据key来检索元素map同multimap的不同在于是否允许多个元素有相同的 key值。上述4种容器通常以平衡二叉树方式实现，插入和检索的 时间都是 O(logN)容器适配器简介1) stack :头文件 栈。是项的有限序列，并满足序列中被删除、 检索和修改的项只能是最近插入
8、序列的项。即 按照后进先出的原则 2) queue :头文件 队列。插入只可以在尾部进行，删除、检索和修 改只允许从头部进行。按照先进先出的原则。 3）priority_queue :头文件 优先级队列。最高优先级元素总是第一个出列容器的共有成员函数1) 所有标准库容器共有的成员函数： n 相当于按词典顺序比较两个容器大小的运算符： =, , =, = , != n empty : 判断容器中是否有元素 n max_size: 容器中最多能装多少元素 n size: 容器中元素个数 n swap: 交换两个容器的内容比较两个容器的例子19比较两个容器的例子： #include #include
9、 int main() std:vector v1; std:vector v2; v1.push_back (5); v1.push_back (1); v2.push_back (1);v2.push_back (2); v2.push_back (3); std:cout #include using namespace std; int main() vector v; /一个存放int元素的向量，一开始里面没有元素 v.push_back(1); v.push_back(2); v.push_back(3); v.push_back(4); vector:const_iterator
10、 i; /常量迭代器 for( i = v.begin();i != v.end();i + ) cout :reverse_iterator r; /反向迭代器 for( r = v.rbegin();r != v.rend();r+ ) cout :iterator j; /非常量迭代器 for( j = v.begin();j != v.end();j + ) * j = 100; for( i = v.begin();i != v.end();i+ ) cout p1, p= p1容器所支持的迭代器类别容器迭代器类别 vector随机 deque随机 list 双向 set/multi
11、set双向 map/multimap双向 stack不支持迭代器 queue不支持迭代器 priority_queue不支持迭代器例如，vector的迭代器是随机迭代器，所以遍历 vector 可以有以下 几种做法： vector v(100); vector:value_type i; /等效于写 int i； for(i = 0;i :const_iterator ii; for( ii = v.begin(); ii != v.end ();ii + ) cout v; list:const_iterator ii; for( ii = v.begin(); ii ！ v.end ();
12、ii + ) cout 中定义o 此外还有其他算法，比如中的算法算法示例：find()template InIt find(InIt first, InIt last, const T o first 和 last 这两个参数都是容器的迭代器，它 们给出了容器中的查找区间起点和终点。 n 这个区间是个左闭右开的区间，即区间的起点是位 于查找范围之中的，而终点不是 o val参数是要查找的元素的值 o 函数返回值是一个迭代器。如果找到，则该迭 代器指向被找到的元素。如果找不到，则该迭 代器指向查找区间终点。#include #include #include using namespace st
13、d; main() int array10 = 10,20,30,40; vector v; v.push_back(1);v.push_back(2); v.push_back(3);v.push_back(4); vector:iterator p; p = find(v.begin(),v.end(),3); if( p != v.end() cout , n list:reference 实际上就是 double int a5 = 1,2,3,4,5 ; vector v(5); cout v2(a,a+5); /构造函数 v2.insert( v2.begin() + 2, 13 )
14、; /在begin()+2位置插入 13 for( i = 0;i v (a,a+5); /构造函数 try v.at(100) = 7; catch( out_of_range e) cout output(cout ,“*“); copy (v.begin(),v.end(),output); v.erase( v.begin(),v.end(); /等效于 v.clear();if( v.empty () cout subscript 1,5 2*3*4*5*empty 1*2*3*4*5*算法解释o ostream_iterator output(cout ,“*“); n定义了一个
15、ostream_iterator 对象，可以通过cout输出以 * 分隔 的一个个整数 o copy (v.begin(),v.end(),output); n导致v的内容在 cout上输出 o copy 函数模板(算法）： template OutIt copy(InIt first, InIt last, OutIt x); n本函数对每个在区间0, last - first)中的N执行一次 *(x+N) = * ( first + N) ，返回 x + N o 对于copy (v.begin(),v.end(),output); nfirst 和 last 的类型是 vector:const_iterator noutput 的类型是 ostream_iterator 关于 ostream_iterator, istream_iterator的例子 int main() istream_iterator inputInt(cin); int n1,n2; n1 = * inputInt; /读入 n1 inputInt +; n2 = * inputInt; /读入 n2 cout outputInt(cout); * outputInt = n1 + n2; cout , class A = allocator class set 插入set中已有的元素时，插入不成功
