C++电子课件(下)第十一章.ppt

第十一章 标准模板库（选读）,库（library）是一系列程序组件的集合，它们 可以在不同的程序中重复使用。 库函数设计的第一位的要求就是通用性，模板（template）为通用性带来了不可估量的前景。 标准模板库（Standard Template Library）是ANSI/ISO C+最有特色、最实用的部分之一。STL包含: 容器类（container） 迭代子（iterator） 算法（algorithm） 泛型算法（generic algorithm）和函数对象（function object）的概念与使用使算法摆脱了对不同类型数据个性操作的依赖。,标准模板库的引入：,11.1 标准模板库简介,11.3 顺序容器,11.2 迭代子类,11.6 容器适配器,11.4 泛型算法与函数对象,11.5 关联容器,第十一章 标准模板库（选读）,11.1 标准模板库简介,容器类（Container） 容器类是管理序列的类，是容纳一组对象或对象集的类。通过由容器类提供的成员函数，可以实现诸如向序列中插入元素，删除元素，查找元素等操作，这些成员函数通过返回迭代子来指定元素在序列中的位置。,容器分为三大类： 顺序容器（Sequence Container or Sequential Container） 关联容器（Associative Container） 容器适配器（Container Adopter） 参见表11.1。,11.1 标准模板库简介,顺序容器和关联容器称为第一类容器（first-class container）。,STL也使容器提供类似的接口。许多基本操作是所有容器都适用的，可以用有类似操作的新类来扩展STL。这些函数和运算符可通称为容器的接口。,表11.2 所有标准库容器共有的函数,11.1 标准模板库简介,(2) 泛型算法（Generic Algorithm）： 在模板中算法不依赖于具体的数据类型，而泛型算法更进一步不依赖于具体的容器。泛型算法中采用函数对象（Function Object）引入不同情况下同一算法的差异。它没有使用继承和多态，避免了虚函数的开销，使STL效率更高。,迭代子把算法与容器连接起来。注意算法只是间接通过迭代子操作容器元素，算法本身与容器无关。算法通常返回迭代子。,(3) 迭代子（Iterator）： 迭代子是指针概念的泛型化，它指向容器中的元素，它能象指针一样增减，轮流指示容器中每个元素。所以说迭代子是面向对象版本的指针。迭代子可以包括指针，但迭代子又不仅仅是一个指针。,11.2 迭代子类,迭代子属性： C+标准库中对普通类型迭代子按照基本访问功能分类，有五种四级（输入/输出为同一级）预定义迭代子，其功能最强最灵活的是随机访问迭代子。,表11.3 迭代子属性,表11.4 各种迭代子可执行的操作,【例11.1】寻找数组元素。 由本例演示可见，泛型算法不直接访问容器的元素，所以与容器无关。元素的全部访问和遍历都通过迭代子实现，并不需要预知容器类型。,11.3 顺序容器,顺序容器： vector，list和deque。vector类和deque类是以数组为基础的，list类是以双向链表为基础的。,11.3.1 矢量类,11.3.2 列表类,11.3.3 双端队列类,11.3. 1 矢量类,矢量类的概念： 矢量（vector）类提供了具有连续内存地址的数据结构。它可通过下标运算符 直接有效地访问矢量的任何元素。 与数组不同，vector的内存用尽时，vector自动分配更大的连续内存区，将原先的元素复制到新的内存区，并释放旧的内存区。这是矢量类的优点。 内存分配由分配子（Allocator）完成。分配子也是类，它运用了new和delete运算符，本教材不作进一步讨论。 矢量类的迭代子： 每个容器都有自己所支持的迭代子类型，迭代子决定了可采用哪种算法。vector支持随机访问迭代子，具有最强的功能。vector的迭代子通常实现为vector元素的指针。所谓选择容器类，实际上很大部分是选择所支持的迭代子。,11.3. 1 矢量类,矢量容器的声明： #include vector vi; /定义存放整形序列的向量容器对象vi，长度为0的空vector vector vf; /存放实型序列的向量容器 vector vch; /存放字符序列的向量容器 vectorvstr; /存放字符串序列的向量容器,11.3.1 矢量类,矢量容器的构造函数： vector(size_t n); /构造一个有n个元素的矢量， /每个元素都是由默认的构造函数所建立的 vector(size_t n,T /元素的初值由区间first,last)指定的序列中的元素复制而来 vector(vector& X) /复制构造函数 这些构造函数还可以显式给出分配子(allocator)对象。,【例11.2】寻找vector容器元素。,对矢量的操作包含了第六章在顺序表中所列出的操作，甚至更丰富。每种操作都是成员函数。对用户自定义的元素类，要重载“= =”和“”等比较运算符。,11.3.1 矢量类,特殊类型迭代子： *它们本身也具有五种四级迭代子属性之一 反转型迭代子（Reverse Iterator）： 它是把一切都颠倒过来。正向遍历一个第一类容器时，如果用了反转迭代子，实际上实现的是反向遍历。,begin()和end()，分别返回指向容器首元素和容器的末元素的后继的迭代子；而rbegin()和rend()，分别返回指向容器末元素和容器的首元素的前导的普通迭代子。后一对操作用于支持反转型迭代子。： vector veco; vector:reverse_iterator r_iter; for(r_iter=veco.rbegin(); /将r_iter指向到末元素 r_iter!=veco.rend(); /不等于首元素的前导 r_iter+) /实际上是递减 /循环体 如果需要把升序的序列改为降序的序列时，并不需要真正去逆序一个序列，只要使用反转迭代子就可以了。反转迭代子属性为随机迭代子。,11.3.1 矢量类,插入型迭代子（Insertion Iterator）： 当用普通输出迭代子来产生一个元素序列时，一旦添加一些元素就得完全重写。例如普通输出迭代子可以把一个矢量a的内容复制到另一个矢量b中，复制可以从矢量b任一元素开始，矢量b对应位置上的元素被覆盖，相当于改写。插入迭代子则可以添加元素，复制时它可以把矢量a插入到矢量b任一位置。同一个copy()算法用不同类型迭代子，结果是不同的。,有三种插入迭代子，属性均为输出迭代子： insert_iterator 用来将新元素插入到一个由迭代子（第二个参数Iter）指定的元素的前面（所谓插在a10之前，即在a9和a10之间添加）。 back_insert_iterator 用来将新元素添加到类型为Type的容器对象的末端； front_insert_iterator 用来将新元素添加到容器的前端（注意：新添加的元素以逆序方式结束于被控序列前端,即最后添加的元素放在最前面）。,11.3.1 矢量类,插入型迭代子使用方法： 标准库定义了一组（3个）插入型迭代子适配器函数。它们返回对应的插入迭代子： Inserter(Type&,Iter) 它使用容器的insert()插入操作符代替赋值操作符。inserter()函数要求两个实参：容器本身和它的一个指示起始插入位置的迭代子。标记起始插入位置的迭代子并不是保持不变，而是随每个被插入的元素而递增，这样每个元素就能顺序被插入。注意是“插入”而不是“改写”，back_inserter(Type&) 它使用容器的push_back()插入操作代替赋值操作符，将新元素添加到容器对象的末端。实参是容器本身。返回一个back_inserter迭代子。 front_inserter(Type&) 它使用容器的push_front()插入操作代替赋值操作符，将新元素添加到容器的前端，同样，新添加的元素以逆序方式结束于被控序列前端,即最后添加的元素放在最前面。实参也是容器本身。返回一个front_inserter迭代子。front_inserter不能用于矢量vector，因为vector没有成员函数push_front()。,11.3.1 矢量类,流迭代子(Stream Iterator)： 包括输入流迭代子（Istream_Iterator）和输出流迭代子（Ostream_Iterator）,输入流迭代子类支持在istream、ifstream等输入流类上的迭代子操作。istream_iterator声明方式为： istream_iterator迭代子标识符(istream /Type为已定义了输入操作的类型,实参可以是任意公有派生的 /istream的子 类型的对象 输出流也有对应的ostream_iterator类支持，其声明方式为： ostream_iterator迭代子标识符(ostream&) /实参同样可以是公有派生子类型对象 ostream_iterator迭代子标识符(ostream&,char*) /第二参数为C风格字符串,【例11.3】用istream_iterator从标准输入读入一个整数集到vector中。,11.3.2 列表类,列表类（list）的引入： 是由双向链表组成的。它有两个指针域，可以向前也可以向后进行访问，但不能随机访问，即支持的迭代子类型为双向迭代子。列表类不能使用下标运算符。它定义在头文件中。 列表类容器也有多种构造函数，与矢量类形式相同。,【例11.4】展示列表类怎样进行链表操作。,在本例中建立了两个已排序好的列表类对象，然后归并。全部用列表类的成员函数。不能使用泛型算法sort()对无序的列表类对象排序，因为sort()要求随机迭代子，list仅支持双向迭代子。,11.3.3 双端队列类,双端队列（Double-Ended Queue）类的引入： 双端队列允许在队列的两端进行操作。它以顺序表为基础，所以能利用下标提供有效的索引访问，它支持随机访问迭代子。,使用双端队列，必须包含头文件。 双端队列类容器也有多种构造函数，与矢量类或列表类形式相同。,【例11.5】双端队列类与矢量类一样，有一个成员函数insert()，注意不是插入迭代子适配器函数inserter()。本例演示该函数的使用，最后输出字符串：“STL功能强使用方便。”,deque类重载了多个成员函数insert()： insert (it,x); /在迭代子it指定元素前插入一个值为x的元素，返回指向新元素的迭代子 insert (it,n,x); /在迭代子it指定元素前插入n个值为x的元素 insert (it,first,last); /在迭代子it指定元素前插入由区间first,last)指定的序列,11.4 泛型算法与函数对象,算法表现为一系列的函数模板。它们完整定义在STL头文件中。使用者可以用很多方式来特化每一个模板函数，大大提高了它作为通用型程序组件的适用性。这些函数模板使用迭代子作为它的参数和返回值，以此在容器（序列）上进行各种操作。本节进一步讨论算法的通用性。,11.4.1 函数对象,11.4.2 泛型算法,11.4.1 函数对象,函数对象的基本概念： 每个泛型算法（Generic Algorithm）的实现都独立于容器类型，它消除了算法对类型的依赖性。 在STL的泛型算法中采用“函数对象”（Function Object）来解决该问题。函数对象是一个类，通常它仅有一个成员函数，该函数重载了函数调用操作符（operator()）。该操作符封装了应该被实现为一个函数的操作。典型情况下，函数对象被作为实参传递给泛型算法。 和“引用”一样，“函数对象”很少独立使用。函数对象亦称拟函数对象（Function_Like Object）和函子（Functor）。,11.4.1 函数对象,【例11.6】求和函数对象的定义和测试。 注意函数对象Sum能实例化为有限种类型，如：整型、实型、字符型等等，也能用于string类型，因为string重载了operator +。,函数对象的应用： 函数对象主要是作为泛型算法的实参使用，通常用来改变默认的操作，如： sort(vec.begin(),vec.end(),greater(); 这就是把整数的大于关系函数对象作为实参，得降序排列。如果是字符串，则有： 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; /负数符号重载 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 例中Comp为比较函数对象（类模板），对不同的数据类型，可以产生不同的比较函数，以实现泛型算法。,使用函数对象实现泛型算法：,11.4.1 函数对象,函数对象与函数指针相比较有三个优点：第一，函数指针是间接引用，不能作为内联函数，而函数对象可以，这样速度更快；第二，函数对象可以拥有任意数量的额外数据，用这些数据可以用来缓冲当前数据和结果，提高运行质量，当然多数情况下不一定使用，上例中res就是一个额外数据；第三，编译时对函数对象作类型检查。,函数对象来源： 1. 标准库预定义的一组算术，关系和逻辑函数对象； 2. 预定义的一组函数适配器，允许对预定义的函数对象进行特殊化或扩展； 3. 自定义函数对象。,函数对象的优点：,11.4.1 函数对象,预定义函数对象及其使用方法： 使用时要包含头文件： #include 算术函数对象： 加法：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) /对应“&” 逻辑或：logical_or(x,y) /对应“|” 逻辑非：logical_not(x) /对应“!”,关系函数对象： 它们的返回值为布尔量，两个参数，第一参数和第二参数相比： 等于：equal_to(x,y) /对应x=y 不等于：not_equal_to(x,y) /对应x!=y 大于：great(x,y) /对应xy 大于等于：great_equal(x,y) /对应x=y 小于：less(x,y) /对应x(x,y) /对应x=y,11.4.1 函数对象,返回布尔值的函数对象称为谓词（predicate），默认的二进制谓词是小于比较操作符“”，所以默认的排序方式都是升序排列，它采用小于比较形式。,函数适配器特化或扩展一元或二元函数对象： 绑定器（Binder）： 把二元函数对象中的一个参数固定（绑定），使之转为一元函数，C+标准库提供两种预定义的binder适配器：bind1st和bind2nd，分别绑定了第一或第二个参数。格式： bind2st(plus(x),3.0) /返回x+3.0 取反器（Negator）： 把函数对象的值翻转的适配器，如原来为小于，用了它后就变成了大于。C+标准库也提供了两种negator适配器：not1和not2。not1用于一元预定义函数对象；not2用于二元预定义函数对象。格式同绑定器。,11.4.2 泛型算法,范型算法分类为： (1)修改容器的算法，即变化序列算法（mutating-sequence algorithm），如copy()、remove()、replace()、swap()等； (2)不修改容器的算法，即非变化序列算法（non-mutating-sequence algorithm），如count()、find()等；以及数字型算法。,*在泛型算法中有一种习惯用语，不说满足某条件的元素，而讲满足指定二进制谓词规则的元素，因为谓词是返回布尔值的函数对象，满足则返回true，即与满足指定条件是同样意思。,泛型算法函数名后缀： _if 表示函数采用的操作是在元素上，而不是对元素的值本身进行操作。如find_if算法表示查找一些值满足函数指定条件的元素，而find查找特定的值。 _copy表示算法不仅操作元素的值，而且还把修改的值复制到一个目标范围中。reverser算法颠倒范围中元素的排列顺序，而reverse_copy算法同时把结果复制到目标范围中。 其它的后缀从英文意思上立即可以认出其意义。,11.4.2 泛型算法,泛型算法的构造与使用方法: 所有泛型算法的前两个实参是一对iterator，通常称为first和last，它们标出要操作的容器或内置数组中的元素范围。元素的范围，包括first，但不包含last的左闭合区间。即： first,last) 当first=last成立，则范围为空。 对iterator的属性，则要求在每个算法声明中指出，所声明的是最低要求。如find()最低要求为：InputIterator，可以传递更高级别的迭代子。如：ForwardIterator、BidirectonalIterator及RandomAccessInterator。但不能用OutputInterator。,11.4.2 泛型算法,泛型算法分类： 1查找算法：有13种查找算法用各种策略去判断容器中是否存在一个指定值。equal_range()、lower_bound()和upper_bound()提供对半查找形式。 2排序和通用整序算法：共有14种排序（sorting）和通用整序（ordering）算法，为容器中元素的排序提供各种处理方法。所谓整序，是按一定规律分类，如分割（partition）算法把容器分为两组，一组由满足某条件的元素组成，另一组由不满足某条件的元素组成。 3删除和代替算法：有15种删除和代替算法。 4排列组合算法：有2种算法。排列组合是指全排列。如：三个字符a，b，c组成的序列有6种可能的全排列：abc，acb，bac，bca，cab，cba；并且六种全排列按以上顺序排列，认为abc最小，cba最大，因为abc是全顺序（从小到大）而cba是全逆序（从大到小）。,11.4.2 泛型算法,5生成和改变算法：有6种，包含生成（generate），填充（fill）等等。 6关系算法：有7种关系算法，为比较两个容器提供了各种策略，包括相等（equal()），最大（max()），最小（min()）等等。 7集合算法：4种集合（set）算法提供了对任何容器类型的通用集合操作。包括并（union），交（intersection），差（difference）和对称差（symmetric difference）。,8. 堆算法：有4种堆算法。堆是以数组来表示二叉树的一种形式。标准库提供大根堆（max_heap），它的每个结点的关键字大于其子结点的关键字。 9. 算术算法：该类算法有4种，使用时要求包含头文件。,11.5 关联容器,关联容器(associative container)的引入： 它们能通过关键字（search key）直接访问(存储和读取元素)。四个关联容器为：集合（set），多重集合（multiset），映射（map）和多重映射（multimap）。,11.5.1 集合和多重集合类,11.5.2 映射和多重映射类,11.5.1 集合和多重集合类,集合和多重集合类引入： 它们提供了控制数值集合的操作，其中数值是关键字，即不必另有一组值与每个关键字相关联。集合与多重集合类的主要差别在于多重集合允许重复的关键字，而集合不允许重复的关键字。,集合和多重集合类提供了控制数值集合的操作，其中数值是关键字，即不必另有一组值与每个关键字相关联。 多重集合允许重复的关键字（key），而集合不允许。 元素的顺序由比较器函数对象（comparator function object）确定。如对整型multiset，只要用比较器函数对象less排序关键字，元素即可按升序排列。,set类模板声明为： template, typename A = allocator class set; /模板参数表中的非类型参数同样可有默认值,11.5.1 集合和多重集合类,set容器的构造函数： set (); /构造一个空的按默认次序排列的集合 set (pr); /构造一个空的按函数对象pr排序的集合 set (first,last); /构造一个默认次序排列的集合， /元素值由区间first,last)指定的序列复制 set (first,last,pr); /同上，但按函数对象pr排序 这些构造函数还可以显式给出分配子(Allocator)对象。,集合和多重集合类支持双向迭代子。 multiset和set通常实现为红黑二叉排序树。红黑二叉排序树是实现平衡二叉排序树的方法之一。,【例11.7】整型多重集合关联容器类,11.5.2 映射和多重映射类,映射和多重映射类引入： 它们提供了操作与关键字相关联的映射值（mapped value）的方法。映射和多重映射的主要差别在于多重映射允许存放与映射值相关联的重复关键字，而映射只允许存放与映射值一一对应的单一关键字。 多重映射和映射关联容器类用于快速存储和读取关键字与相关值（关键字/数值对，key/value pair）。如果保存学生的简明资料，要求按学号排序，使用映射关联容器（因为不会重号）是最合适的。如用姓名排序，因姓名可能重复，使用多重映射更为合适。使用时要用头文件。,11.5.2 映射和多重映射类,map类模板声明： template, typename A = allocator class map; map容器有多种构造函数： map (); /构造一个空的按默认次序排列的映射 map (pr); /构造一个空的按函数对象pr排序的映射 map (first,last); /构造按默认次序排列的映射， /元素值由区间first,last)指定的有序序列复制 map (first,last,pr); /同上，但按函数对象pr排序 这些构造函数还可以显式给出分配子(allocator)对象。,11.5.2 映射和多重映射类,映射的使用： 映射和多重映射类支持双向迭代子。 映射定义了成员操作符： T& operatorconst Key& key 这样映射的使用是非常方便的，就如同一个数组，关键字作为下标，相关值作为元素值。,【例11.8】我国部分省份与面积映射关联容器类的演示。,11.6 容器适配器,容器适配器（container adapter）： 栈，队列和优先级队。所谓适配器并不独立，它依附在一个顺序容器上。如要声明一个用矢量实现的字符型堆栈，声明如下： stack sk;,然后它可以象顺序容器一样使用。但它没有自己的构造和析构函数，它使用其实现类（如vector）的构造和析构函数。队列（queue）默认用deque为基础，栈（stack）可用vector或deque为基础。,11.5.1 栈类,11.5.2 队列类,11.5.3 优先级队列类,11.5.1 栈类,栈并不独立，它依附在一个顺序容器上。栈（stack）可用vector或deque为基础。 声明一个用矢量实现的字符型堆栈，格式如下： stack sk;,【例11.9】演示堆栈的压入和弹出。,栈类的引入：,11.5.2 队列类,队列（queue）： 默认以deque为基础,【例11.10】演示队列的入队和出队。,11.5.3 优先级队列类,优先级队列（priority_queue）适配器： 用以实现优先级队列。元素插入是自动按优先级顺序插入，使最高优先级元素首先从优先级队列中取出。常用矢量为基础容器。默认时priority_queue用vector为基础数据结构。,【例11.11】 优先级队列类演示，头文件用，优先级用数表示，数值越大优先级越高。,第十一章 标准模板库（选读）,课程全部结束,祝同学们有一个好成绩！,表11.1 标准库容器类,表11.2 所有标准库容器共有的函数（1）,表11.2 所有标准库容器共有的函数（2）,表11.2 所有标准库容器共有的函数（3）,表11.3 迭代子属性,输入 InputIterator 输出 OutputIterator 正向 ForwardIterator 双向Bidirectional Iterator 随机访问 Random AccessIterator,从容器中读取元素。输入迭代子只能一次一个元素地正向移动（即从容器开头到容器末尾，后移）。要重读必须从头开始。 向容器写入元素。输出迭代子只能一次一个元素地正向移动。输出迭代子要重写，必须从头开始。 组合输入迭代子和输出迭代子的功能，并保留在容器中的位置（作为状态信息），所以重新读写不必从头开始。 组合正向迭代子功能与逆向移动功能（即从容器序列末尾到容器序列开头）。 组合双向迭代子的功能，并能直接访问容器中的任意元素，即可向前或向后跳过任意个元素。,表11. 4 各种迭代子可执行的操作（1）,表11. 4 各种迭代子可执行的操作（2）,【例11.1】寻找数组元素,int main() int search_value,ia9=47,29,37,23,11,7,5,31,41; coutsearch_value; int* presult=find( ,【例11.2】寻找vector容器元素,int main() int i,search_value,ia9=47,29,37,23,11,7,5,31,41; vector vec(ia,ia+9); /数据填入vector vector:iterator iter; /iter是vector用的迭代子，自动建为随机访问迭代子 for(i=0;isearch_value; iter=find(vec.begin(),vec.end(),search_value); /使用vector成员函数赋迭代子初值 cout“数值“search_value ( iter=vec.end() ?“不存在“:“存在“)endl; return 0;,【例11.3】标准输入,#include #include #include #include #include using namespace std; int main() istream_iterator input(cin); istream_iterator end_of_stream; vector vec; copy(input,end_of_stream,inserter(vec,vec.begin(); /输入Z结束流 sort(vec.begin(),vec.end(),greater(); /降序排列 ostream_iteratoroutput(cout,“ “); unique_copy(vec.begin(),vec.end(),output); coutendl; return 0;,【例11.3】标准输入,首先，用一个istream_iterator迭代子input（其实参为cin，即标准输入）读入一个整数集到一个矢量类对象中，出现光标后，可输入： 41 3 9 5 7 23 17 19 13 11 37 31 23 29 41 39 Z,例中泛型算法copy()定义如下： template OutputIterator copy(InputIterator first,InputIterator last,OutputInterator x) for(;first!=last;+x,+first) *x=*first return (x); ,实参end_of_stream是指示文件（流）的结束位置，输入时必须在最后一个数字后加分隔符，然后加Ctrl-Z结束。复制算法要求提供一对iterator来指示文件（流）内部的开始和结束位置。第三个参数是标准函数inserter()返回的插入迭代子，它把流插入vec。,【例11.3】标准输入,泛型算法sort()为升序排序算法，声明如下 template void sort(RandomAccessIterator first, RandomAccessInterator last, Pr p); /第三参数为排序方式，greater()是预定义的“大于”函数对象，排序时用它来比较数值大小。默认时为“小于”，即升序排序。,例中用输出迭代子output来输出。其第二个参数“ “表示用空格分隔各数字。 泛型算法unique_copy（），复制一个序列，并删除序列中所有重复元素。本例中，复制到output迭代子，并用空格分隔各整数的标准输出。输出为： 41 39 37 31 29 23 19 17 13 11 9 7 5 3,【例11.4】列表类的链表操作,int main() int i; list list1,list2; list:iterator iter; /iter是list用的迭代子，自动建为双向访问迭代子 int arr1=5,7,17,19,23,43; int arr2=3,9,13,29,41; for(i=0;i6;i+) list1.push_back(arr1i); for(i=0;i5;i+) list2.push_front(arr2i); for(iter=list1.begin();iter!=list1.end();iter+) cout*itert; /输出5,7,17,19,23,43 coutendl; for(iter=list2.begin();iter!=list2.end();iter+) cout*itert; /输出41,29,13,9,3 coutendl; list2.reverse(); /反转为3,9,13,29,41 list1.merge(list2); /list2归并到list1,方式默认为升序 while(!list1.empty() /表空结束 coutlist1.front()t; /读第一项，输出3,5,7,9,13,17,19,23,29,41,43 list1.pop_front(); /从链表首删去一项 coutendl; return 0;,【例11.5】双端队列类成员函数insert() 操作,void print_string(char_deque deq) ostream_iteratoroutput(cout); cout“生成的字符串是：“; copy(deq.begin(),deq.end(),output); int main() char arr1=“功能强“,arr2=“使用方便。“; char_deque chdeq(arr1,arr1+6); print_string(chdeq); coutendl; chdeq.insert(chdeq.begin(),L); /逆序 chdeq.insert(chdeq.begin(),T); chdeq.insert(chdeq.begin(),S); print_string(chdeq); coutendl; chdeq.insert(chdeq.end(),arr2,arr2+10); print_string(chdeq); coutendl; return 0;,【例11.6】求和函数对象的定义和测试,templateclass Sum T res; public: Sum(T i=0):res(i) /构造函数,即Sum(T i=0)res=i; T operator()(T x) /累加，重载的调用操作符() res+=x; return res; ; template T Func1(FuncObject fob,const T ,【例11.6】求和函数对象的定义和测试,int main() Sum sum(10); /调用构造函数建立sum。res值为10 int i=5,j=10; cout(5),i)(),j)endl; / 0+j，输出：10 return 0;,输出：20 25 30 35 35 30 40 50 10 10 10 10 10 10,【例11.7】整型多重集合关联容器类,多重集合关联容器类，类模板声明: template, typename A = allocator class multiset; /模板参数表中的非类型参数同样可有默认值 #include #include /包含集合头文件 #include /包含算法头文件 using namespace std; /C+标准库名字空间域 typedef multisetINTMS; /特例取名INTMS，整型多重集合按升序排列,【例11.7】整型多重集合关联容器类,int main() const int size=16; int asize=17,11,29,89,73,53,61,37,41,29,3,47,31,59,5,2; INTMS intMultiset(a,a+size); /用a来初始化INTMS容器实例 ostream_iterator output(cout,“ “); /整型输出迭代子output，可通过cout输出用空格分隔的整数 cout“这里原来有“intMultiset.count(17) “个数值17“endl; /查找有几个关键字17 intMultiset.insert(17); /插入一个重复的数17 cout“输入后这里有“intMultiset.count(17)