《C++电子课件(下)第十一章》由会员分享，可在线阅读，更多相关《C++电子课件(下)第十一章（63页珍藏版）》请在金锄头文库上搜索。
1、第十一章 标准模板库（选读）库（library）是一系列程序组件的集合，它们 可以在不同的程序中重复使用。库函数设计的第一位的要求就是通用性，模板（ template）为通用性带来了不可估量的前景。标准模板库（Standard Template Library）是 ANSI/ISO C+最有特色、最实用的部分之一。STL包含: 容器类（container） 迭代子（iterator） 算法（algorithm）泛型算法（generic algorithm）和函数对象（ function object）的概念与使用使算法摆脱了对不同类 型数据个性操作的依赖。 标准模板库的引入：11.1 标准模板
2、库简介 11.3 顺序容器 11.2 迭代子类 11.6 容器适配器 11.4 泛型算法与函数对象 11.5 关联容器 第十一章 标准模板库（选读）11.1 标准模板库简介(1)容器类（Container） 容器类是管理序列的类，是容纳一组对象或对象集的类。通过 由容器类提供的成员函数，可以实现诸如向序列中插入元素 ，删除元素，查找元素等操作，这些成员函数通过返回迭代 子来指定元素在序列中的位置。容器分为三大类： 顺序容器（Sequence Container or Sequential Container） 关联容器（Associative Container） 容器适配器（Containe
3、r Adopter） 参见表11.1。11.1 标准模板库简介顺序容器和关联容器称为第一类容器（first-class container）。STL也使容器提供类似的接口。许多基本操作是所有容 器都适用的，可以用有类似操作的新类来扩展STL。这 些函数和运算符可通称为容器的接口。表11.2 所有标准库容器共有的函数11.1 标准模板库简介(2) 泛型算法（Generic Algorithm）： 在模板中算法不依赖于具体的数据类型，而泛型算法更进一步 不依赖于具体的容器。泛型算法中采用函数对象（Function Object）引入不同情况下同一算法的差异。它没有使用继承和 多态，避免了虚函数的开
4、销，使STL效率更高。 迭代子把算法与容器连接起来。注意算法只是间接通过迭代子 操作容器元素，算法本身与容器无关。算法通常返回迭代子。 (3) 迭代子（Iterator）： 迭代子是指针概念的泛型化，它指向容器中的元素，它能象指 针一样增减，轮流指示容器中每个元素。所以说迭代子是面向 对象版本的指针。迭代子可以包括指针，但迭代子又不仅仅是 一个指针。11.2 迭代子类迭代子属性：C+标准库中对普通类型迭代子按照基本访问功能分类， 有五种四级（输入/输出为同一级）预定义迭代子，其功能最 强最灵活的是随机访问迭代子。 表11.3 迭代子属性表11.4 各种迭代子可执行的操作【例11.1】寻找数组元
5、素。 由本例演示可见，泛型算法不直接访问容器的元素，所 以与容器无关。元素的全部访问和遍历都通过迭代子实 现，并不需要预知容器类型。11.3 顺序容器顺序容器： vector，list和deque。vector类和deque 类是以数组为基础的，list类是以双向链表 为基础的。11.3.1 矢量类11.3.2 列表类11.3.3 双端队列类11.3. 1 矢量类矢量类的概念：矢量（vector）类提供了具有连续内存地址的数据结构。 它可通过下标运算符 直接有效地访问矢量的任何元素。与数组不同，vector的内存用尽时，vector自动分配更大 的连续内存区，将原先的元素复制到新的内存区，并释
6、放旧的 内存区。这是矢量类的优点。内存分配由分配子（Allocator）完成。分配子也是类， 它运用了new和delete运算符，本教材不作进一步讨论。 矢量类的迭代子： 每个容器都有自己所支持的迭代子类型，迭代子决定了可采用 哪种算法。vector支持随机访问迭代子，具有最强的功能。 vector的迭代子通常实现为vector元素的指针。所谓选择容器 类，实际上很大部分是选择所支持的迭代子。11.3. 1 矢量类矢量容器的声明： #include vector vi; /定义存放整形序列的向量容器对象vi，长度为0的空vector vector vf;/存放实型序列的向量容器 vector
7、vch; /存放字符序列的向量容器 vectorvstr; /存放字符串序列的向量容器11.3.1 矢量类矢量容器的构造函数： vector(size_t n); /构造一个有n个元素的矢量， /每个元素都是由默认的构造函数所建立的 vector(size_t n,T /T表示矢量的基本类型，如int； /为每个元素用同一个对象V来赋初值 vector(first,last); /元素的初值由区间first,last)指定的序列中的元素复制而来 vector(vector vector:reverse_iterator r_iter; for(r_iter=veco.rbegin(); /将r
8、_iter指向到末元素 r_iter!=veco.rend(); /不等于首元素的前导 r_iter+) /实际上是递减 /循环体 如果需要把升序的序列改为降序的序列时，并不需要真正去逆序一个序列， 只要使用反转迭代子就可以了。反转迭代子属性为随机迭代子。11.3.1 矢量类 插入型迭代子（Insertion Iterator）： 当用普通输出迭代子来产生一个元素序列时，一旦添加一些元素就得完全重 写。例如普通输出迭代子可以把一个矢量a的内容复制到另一个矢量b中， 复制可以从矢量b任一元素开始，矢量b对应位置上的元素被覆盖，相当于 改写。插入迭代子则可以添加元素，复制时它可以把矢量a插入到矢量
9、b任 一位置。同一个copy()算法用不同类型迭代子，结果是不同的。 有三种插入迭代子，属性均为输出迭代子： insert_iterator 用来将新元素插入到一个由迭代子（第二个参数Iter）指定的元素 的前面（所谓插在a10之前，即在a9和a10之间添加）。 back_insert_iterator 用来将新元素添加到类型为Type的容器对象的末端； front_insert_iterator 用来将新元素添加到容器的前端（注意：新添加的元素以逆序方式 结束于被控序列前端,即最后添加的元素放在最前面）。 11.3.1 矢量类 插入型迭代子使用方法： 标准库定义了一组（3个）插入型迭代子适配
10、器函数。它们返回对应的插入 迭代子： Inserter(Type /Type为已定义了输入操作的类型,实参可以是任意公有派生的 /istream的子 类型的对象 输出流也有对应的ostream_iterator类支持，其声明方式为： ostream_iterator迭代子标识符(ostream /在迭代子it指定元素前插入一个值为x的元素，返回指向新元素的迭代子 insert (it,n,x); /在迭代子it指定元素前插入n个值为x的元素 insert (it,first,last); /在迭代子it指定元素前插入由区间first,last)指定的序列11.4 泛型算法与函数对象算法表现为一
11、系列的函数模板。它们完整定义在STL头文 件中。使用者可以用很多方式来特化每一个模板函数，大大提 高了它作为通用型程序组件的适用性。这些函数模板使用迭代 子作为它的参数和返回值，以此在容器（序列）上进行各种操 作。本节进一步讨论算法的通用性。11.4.1 函数对象 11.4.2 泛型算法 11.4.1 函数对象函数对象的基本概念：每个泛型算法（Generic Algorithm）的实现都独立于容器类 型，它消除了算法对类型的依赖性。在STL的泛型算法中采用“函数对象”（Function Object）来解 决该问题。函数对象是一个类，通常它仅有一个成员函数，该 函数重载了函数调用操作符（ope
12、rator()）。该操作符封装了 应该被实现为一个函数的操作。典型情况下，函数对象被作为 实参传递给泛型算法。和“引用”一样，“函数对象”很少独立使用。函数对象亦称拟函 数对象（Function_Like Object）和函子（Functor）。 11.4.1 函数对象【例11.6】求和函数对象的定义和测试。 注意函数对象Sum能实例化为有限种类型，如：整型、实型、字符型等等 ，也能用于string类型，因为string重载了operator +。函数对象的应用： 函数对象主要是作为泛型算法的实参使用，通常用来改变默认 的操作，如： sort(vec.begin(),vec.end(),gre
13、ater(); 这就是把整数的大于关系函数对象作为实参，得降序排列。如 果是字符串，则有： sort(svec.begin(),svec.end(),greater(); 只要改一下参数就又可用于字符串的排序。 greater中所包含的比较算法实际上在内置类型int，字 符串类string中定义。由此可见函数对象并没有新东西，只是 一个固定格式，用起来更方便。 11.4.1 函数对象例如，自定义整数类Int，其中重载了比较算法“”运算符： class Int public:Int(int ival=0):_val(ival)int operator-()return -_val; /负数符号重
14、载int operator%(int ival)return _val%ival; /求余符号重载bool operator(int ival)return _valival; /大于符号重载bool operator!()return _val=0; /逻辑非符号重载 private:int _val; ; Int类可以作为类型参数传递给函数对象greater()，同时把 重载的运算符也传递过去了。11.4.1 函数对象以函数对象作为求序列中最小值的函数模板的“数值比 较算法”参数： template const Type/最小元素下标初值为0,即设0号元素最小for(int i=1;i 算
15、术函数对象： 加法：plus(x,y) /返回x+y,可用于string、复数和浮点数等 减法：minus(x,y) /返回x-y,不能用串,可用于复数和浮点数等 乘法：multiplies(x,y)/返回x*y,不能用串,可用于复数和浮点数等 除法：divides(x,y) /返回x/y,不能用串,可用于复数和浮点数等 求余：modulus(x,y) /返回x%y,只能用于整数 取反：negate(x) /返回-x,补码,只能用于整数11.4.1 函数对象逻辑函数对象： 这里Type必须支持逻辑运算，有两个参数。 逻辑与：logical_and(x,y) /对应“ /模板参数表中的非类型参数同样可有默认值11.5.1 集合和多重集合类set容器的构造函数： set (); /构造一个空的按默认次序排列的集合 set (pr); /构造一个空的按函数对象pr排序的集合 set (first,last); /构造一个默认次序排列的集合，/元素值由区间first,last)指定的序列复制 set (first,last,pr); /同上，但按函数对象pr排序 这些构造函数还可以显式给出分配子(Allocator)对象。集
