C++语言程序设计8第八讲——C++标准模板库

第十章 C+标准模板库,C+语言程序设计,主要内容,泛型程序设计 与标准模板库有关的概念和术语 C+标准模板库中的容器 迭代器 适配器 算法 函数对象,为何需要STL,编程的数据需要存放、组织、管理。不需要每个程序员都从头自行设计。将已有的经典的优秀的成果标准化、规范化、模块化，是提高软件生产率，实现产业化的趋势； “为了建立数据结构和算法的一套标准，降低其间的耦合关系，以提升各自的独立性、弹性、交互操作性（相互合作性），C+社群里诞生了STL.” 侯捷,STL (Standard Templatr Library),1993年C+标准化委员会接受了Alexandar Stepenov的提案，为C+增加了STL； 可以用来创建动态增减的数据结构； 可用于基本数据类型和扩展类型，还可以用于指针、引用。这对于那些必须使用类层次结构来构造程序的语言来说是无法比拟的。,STL，虽然是一套程序库(Library)，却不只是一般印象中的程序库，而是一个有着划时代意义，背后拥有先进技术与深厚理论的产品。说它是产品也可以，说它是规格也可以，说它是软件组件技术发展史上一个大突破，也当之无愧。 长久以来，软件界一直希望建立一种可重复运用的东西，以及一种得以制造出“可重复运用的东西”的方法，让工程师/程序员的心血不至于随时间的迁移、人事异动而烟消云散。从子程序(subroutines)、程序(procedures)、函数(functions)、类别(classes)，到函数库(function libraries )、类别库(class libraries )、各种组件(components)，从结构化设计、模块化设计、面向对象设计，到样式(patterns)的归纳整理，无一不是软件工程的漫漫奋斗史。为的就是复用性(reusebility)的提升。 摘自STL源码剖析,STL的价值,提了一套极具实用价值的零部件，以及一个整合的极好的组织结构； 以泛型思维为基础提供了高层次的、系统化的、条理分明的“软件组织分类学”实践； 是类型无关的，故具有很高的可复用性； 是编译时而非运行时数据类型检查，可保证数据安全； 与平台无关，于是保证了可移植性；,观念的颠覆,在STL被纳入C+之前，是“根据功能需要自己动手制作适当的类，这表现了初步的开发功力” ； 在STL被纳入C+之后，情况变成“根据功能需要在标准库中挑选适当的类，来完成所需要的功能。这才表现成熟的开发功力” ；,STL的六大组件,标准模板库(Standard Template Library)包括: 容器(containers) 迭代器(iterators) 算法（algorithms） 函数对象（function object） 空间配置器（allocator） 适配器（adapters） 等内容；,C+语言与标准模板库,标准模板库STL是C+语言的外延，也是面向对象语言的高级形态，甚至超越了面向对象的设计思想，是基本概念的升华； C+是多范型(multiparadigm)语言,它同时支持面向过程的设计、面向对象的设计及泛型设计等多种编程风格(范型)；,泛型程序设计,( Generic Programming ) 是采用各种技术，将程序写得尽可能通用 ； 目的：将算法从特定的数据结构中抽象出来，成为通用的、公用的； 作用：C+的模板技术为泛型程序设计奠定了关键的基础； STL是泛型程序设计的一个优秀范例 ，是每个程序员的学习楷模。,曾使用过的泛型程序设计技术 是经历，也是比较,带参宏；其缺点是显然的 ； 使用 void * ,如 malloc()；繁琐且不安全； 使用通用的根类和虚函数，如Java的object 和继承；致使系统庞大，代价也大； 使用模板技术；类型安全，无开销 。,容器,容器,函数对象,迭代器,迭代器,迭代器,取出,放入,选用,STL的关键组件,算法,C+ STL 主要组件的关系,函数对象,容器,算法,迭代子,数据,适配子,适配子,适配子,扩建,新刀具,技师,STL的容器元素是动态分配和释放的，而不同的硬件平台操作系统对内存的管理和使用互不相同，若把分配空间管理内存交由用户程序完成，是不符合“与平台无关性”要求的。甚至有的应用，其数据不一定保存在内存中，可能在数据库或磁盘文件中，所有对容器的使用都应该是透明的。为此，STL为容器类定义了专门负责存储管理的类allocator类（但效率不佳。参见STL源码剖析P48）。每个容器均定义了自己的分配器。 allocator类是模版，它是对new运算的更高层次的抽象。即隐藏了内存细节，为IO流、string类、容器类、用户自定义类型、类库等提供了独立于硬件和OS的接口。,STL的分配器,address() 返回一个指向指定引用的指针 allocate() 分配内存 deallocate() 释放内存 max_size() 返回能够分配的对象个数 construct() 构造对象 destroy() 销毁对象 另外还有 = 和 != 。 每个容器默认的分配器是allocator 类的对象。它已经足以应付大多数需求，再不满意，用户可以自定义分配器。,分配器提供的函数,容器,容器类是容纳、包含一组元素对象或元素集合的类。 可分为异类容器类与同类容器类； 七种基本容器： 向量（vector）、双端队列（deque）、列表（list）、集合（set）、多重集合（multiset）、映射（map）和多重映射（multimap） 注意：容器不像数组，它可以是空容器！Why?,概念和术语,容器的分类,栈,双端队列,顺序容器,向量,列表,集合,多重集,映射,多重映射,关联容器,队,优先队,适配器,序列容器,关联容器,C+内建,非标准,适配器,非标准,非标准,非标准,非标准,非标准,适配器,容器中元素的底层组织,容器名 可选底层存储结构 访问方式 排序否 底层 上层 vector - 顺序/ 随机 顺序/ 随机 否 list - 顺序 顺序 否 queue list/ deque - - 否 deque list/ vector 顺序/ 随机 顺序/ 随机 否 stack vector/list/deque - - 否 set vector/list/tree 顺序 顺序/ 随机 是 / multiset map vector/list/tree 顺序 顺序/ 随机 是 / multimap,所有容器的通用接口 1,“接口”是指容器的外观界面，其实是公有成员函数。包括： 通用运算符函数： =，!=，=，=，= 方法（函数） 默认构造函数：将容器对象初始化为空 拷贝构造函数：拷贝产生新容器对象 析构函数 ：释放容器对象 empty() ：测试容器是否为空 max_size() ：容器可容纳元素的最大个数 size() ：容器中现有的元素个数,概念和术语,所有容器的通用接口 2,swap(c1) ：交换当前容器和c1容器中的元素 begin() ：返回容器的第一个元素的迭代器值 end() ：返回容器最后元素外的迭代器值 rbegin()：返回反向迭代的起始元素的迭代器值 rend() ：返回反向迭代的终止迭代器值 insert(pos,ele) ：在当前容器的pos位置插入元 素ele erase(begin,end) ：删除当前容器从begin到end间的所有元素 clear() ：清空当前容器的所有元素 (以上是所有容器至少具备的共性的，另外还有个性的函数们),概念和术语,顺序容器,顺序容器：其中的元素被视为逻辑上线性排列的，有头有尾，有前导有后继，可以用索引值即位置值来随机地访问其中任意一个元素。 STL 提供三个基本顺序容器： vector list deque STL 还提供三个容器适配器： stack queue priority_queue 此外，STL 还提供四个“近容器”（类似容器但没有容器的全部功能）： string bitset valarray 数组,容 器,顺序容器的通用接口,迭代方法： begin()，end()，rbegin()，rend() 插入方法 push_front()，push_back()，insert()， 迭代访问方法 使用迭代器( 对于顺序容器的元素排序是徒劳的。因此，没有提供 find()函数。) 删除方法 pop_front()，pop_back () ，erase()，clear() 其它顺序容器访问方法（只读访问） front()，back()，下标运算符,概念和术语,顺序容器向量,向量属于顺序容器，用于容纳不定长线性序列（即线性群体），提供对序列的快速随机访问（也称直接访问） 向量是动态结构，它的大小不固定，可以在程序运行时增加或减少。 P334-335 给出了向量的部分接口。 定要区分“容器对象”和“元素对象”两个不同的概念。容器对象是容纳元素对象的，它们是聚集关系。元素对象如何组织是命名容器的依据。,容 器,向量的定义,template class vector 其中：T是所能容纳的元素对象的类型； allocator是默认的分配器。 vector的构造函数有： explicit vector(const Allocator ,vector ve,26,向量的模型,_first,_last,_end,接口函数： begin() end() push_back() pop_back() resize() back() clear() empty() insert() swap() erase() size()：目前得到的容器中的元素个数 capacity() ：不再分新空间时的额定空间大小 max_size()：可得到的最大空间大小(系统定的),这块叫 size,预留空间,这块叫 capacity,这块不叫 maxsize,/ 使用vector 的例子 #include #include using namespace std; void main() int temp3 = 4,5,6; vector container1(3); vector container2(temp,temp+3); container10 = 1; container11 = 2; container12 = 3; cout “Data in Container-1 :“ container10 container11 container12 “n“;,29,创建了有三个元素的向量对象,创建了由数组初始化的向量对象,问：temp数组使用了什么空间？ 向量对象呢？,cout “Data in Container-2 :“ container20 container21 container22 “n“; cout “After do container1 = container2 “n“; container1 = container2; cout “Data in Container-1 :“ container10 container11 container12 “n“; cout “Data in Container-2 :“ container20 container21 container22 “n“; container20 = 10; container21 = 20; container22 = 30; cout “Data in array :” temp0 “ “temp1 “ “temp2 “n“; / 显示数组的值，以区别于使用数组的容器2,30,运行结果： Data in Container-1 : 1 2 3 Data in Container-2 : 4 5 6 After do container1 = container2 Data in Container-1 : 4 5 6 Data in Container-2 : 4 5 6 Data in array : 4 5 6,31,size()返回的是目前容器得到的元素个数 。resize会在容器的尾部添加或删除一些元素来改变容器，以达到指定的大小。 size()测得的是 resize()的结果。此两个函数只用于vector、list、deque。 capacity()返回的是：当目前容器容纳到多少元素(包括已有的和尚未分配的)时才会导致新分配空间。reserve会在必要时扩充容量，以确保你所指出的空间要求得到满足。请注意，这里用的字眼是“.扩充容量”，而非“.添加或删除一些元素”。意思是并没创建元素对象，仅仅扩大了容量。 capacity()测得的是 reserve()的结果。此两个函数只用于vector。,32,size()与capacity()的区别：,/例10-1 p336 求范围2N中的质数，N在程序运行时由键盘输入。 #include #include #include /包含向量容器头文件 using namespace std ; void main(void) vector A(10); /创建一个向量对象 int n; int primecount = 0, i, j; cout=2 as upper limit: “; cin n; Aprimecount+ = 2; /对象调 函数访问元素,33,for(i = 3; i i/2) Aprimecount+ = i; /此时能确定i是个质数 for (i = 0; iprimecount; i+)/输出质数 coutsetw(5)Ai; if (i+1) % 10 = 0) /每输出10个数换行一次 cout endl; coutendl; ,34,找出以上哪些语句使用了向量的接口？,此处size()是10，不可使用capacity() ，因为capacity() 表示的总是前次空间大小的倍数,resize会创建新的元素对象。,/ 使用vector 的又一例子 #include #include #include #include using namespace std; void main() vector StrVector;/为字符串创建空的向量 StrVector.reserve(5);/为五个元素分配向量存储空间 /将字符串压入向量容器 StrVector.push_back(“Hello,“); StrVector.push_back(“What“); StrVector.push_back(“is“); StrVector.push_back(“This“); StrVector.push_back(“?“); /输出向量容器中的元素，通过空格隔开 copy (StrVector.begin(), StrVector.end(),ostream_iterator(cout,“ “);,35,copy是“算法”中的通用函数。,这仅是预定了向量存储空间，并没创建元素对象。,/输出向量容器的信息： cout (cout,“ “); /输出向量容器的信息： cout “n max_size(): “ StrVector.max_size() “n size(): “ StrVector.size() “n capacity(): “ StrVector.capacity() endl; ,36,这不是向量的成员函数，而是算法的函数。(看调用即可知),运行结果： Hello ，What is This ? max_size(): 268435455 size(): 5 capacity(): 5 Hello ， This is What there ！ max_size(): 268435455 size(): 6 capacity(): 10,37,此值会因机器而异,vector类模板也像Array类支持下标遍历，但更多的是用迭代子遍历向量元素； vector类模板也像Array类支持“向现有的向量元素赋值”，另外还支持“可动态增长”的概念，但只向尾部增长，而且所谓增长的事实是：1寻觅更大的空间，2复制原来的数据，3释放原空间。频繁的增长将付出高昂的代价，这就是vector 要预留空间的道理； vector不搞大而全。该类只是提供了一个最小操作集，更多的操作依靠的是“通用的泛型化算法”所提供的社会化服务。可见STL是个强大的群体，其中的各组成部分互为后盾，发挥的是群体优势，而非string那样搞大而全、万事不求人。,38,vector与Array类模板的区别：,该函数并没有将对象从容器中物理地删除，只是将已死亡的对象移到了容器的尾部 ，返回一个指向死亡对象的iterator。若没有对象被删除，则返回指向end()的iterator。 若有一个vector v,含有9个元素： 1 2 3 1 2 3 1 2 3。 执行过 remove( v.begin(), v.end(), 3); 之后的结果为： 1 2 1 2 1 2 ？ ？ ？。 此时，容器的大小没变， 真正删除容器中为3的元素的操作为： v.erase ( remove( v.begin(), v.end(), 3 ), v.end() ) ;,39,关于remove(),返回的迭代子指向这儿,请注意，这种表示是在指明一个区间，而不是整个容器。因此不存在对区间“删除元素”。所以元素没有真正删除掉。这正是算法函数 “只认迭代器不认容器”的操作特点。,请注意，这remove是算法函数不是容器类的成员,reserve是预定的意思， 该函数实际影响的是capacity()的值，不影响size()。它不创建新对象。 若 n 小于capacity()的当前值，则对容器没有任何影响；否则该函数会申请额外内存空间。若成功，则capacity()会的值会大于或等于n，此时的iterator将失效，但元素不受影响。 使用理由：一次要足，免得零碎要影响效率。,40,关于reserve(size_t n),在下面的函数中，下标和at()函数，即A行和 B行有何区别？ void fun ( vector /B 调用成员函数 ,41,vector的深度探讨 1,若vr非空，则A行和 B行无任何区别； 但若vr空， B行会抛出一个std:out_of_range异常，而A行的行为，则不可预料。因为vector:operator 是否进行下标越界检查，是否能抛出异常，C+98标准没给出明确规定，全在于各厂商自行处理。at()是要进行下标越界检查的.,vector v; v.reserve(2); if( v.capacity() = 2 ) v0 = 10; / 是不创建对象的，那么. v1 = 20; for(vector:iterator it=v.begin();itv.end(); +it) cout *it endl; cout v0 endl; v. reserve(100);/只会对正式成员搬家，不管黑户。 cout v0 endl;,42,vector的深度探讨 2,保证vector的容量至少为2(很可能大于2)，但不是创建元素对象。,仅验证vector的容量是否为2以上。,此时vector中一个元素对象都没有，把值赋给谁？,尽量使用!= 而不用。因为是随机迭代器，而 !=对任何迭代器都有效。,此句可能显示10。但请记住，它是用了不可靠的内存。,此句可能显示0，也可能显示其它值。,下面的函数做了什么？ void fun ( vector 课堂练习：每个人都画出内存映像图。,43,vector的深度探讨 3,strVect,44,“探讨3”的内存映像图,_first,_last,_end,char*p0,char*p1,char*p9,heap,“0”,“H0”,“HHHHHHHHH0”,heap,此区域由容器释放,此区域由用户释放,顺序容器双端队列,双端队列是一种两端皆可存取访问的连续线性空间。元素可以从队列的两端入队和出队，也支持通过下标操作符“”进行直接访问。 不要被deque名字所迷惑，其实它就是个数组，是两头开放的数组。 两头皆可增删元素，是与vector的不同之处。vector是仅一头开放的数组。 deque没有容量的概念，它是动态地以分段连续空间组合而成，不会有空间不足要重新配置更大空间的事情发生。它的迭代器不是普通指针，其复杂度远高于vector的迭代器，尽管也是随机迭代器。,容 器,46,双端队列的内存模型,512B,T *map,缓冲区,中控器(指针数组),这是deque的存储主体,first,cur,node,last,deque的迭代器:start 和finish,/10_2.cpp 使用双端队列容器保存双精度数值序列 #include #include /包含双端队列容器头文件 #include /包含算法头文件 using namespace std; void main() deque values;/声明一个双精度deque序列容器 ostream_iterator output( cout, “ “ ); values.push_front( 2.2 ); /应用函数push_front在deque容器开头插入元素 values.push_front( 3.5 );,47,values.push_back( 1.1 ); /应用函数push_back在 deque容器结尾插入元素 cout “values contains: “; for ( int i = 0; i values.size(); +i ) cout values i ; values.pop_front(); /应用函数push_front从deque容 器中删除第一个元素 cout “nAfter pop_front values contains: “; copy ( values.begin(), values.end(), output ); values 1 = 5.4; /应用操作符来重新赋值 cout “nAfter values 1 = 5.4 values contains: “; copy ( values.begin(), values.end(), output ); cout endl; ,48,运行结果： values contains: 3.5 2.2 1.1 After pop_front values contains: 2.2 1.1 After values1 =5.4 values contains: 2.2 5.4,49,顺序容器列表,列表主要用于存放双向链表，可以从任意一端开始遍历。列表还提供了拼接（splicing）操作，能将一个序列中的元素插入到另一个序列中。 p338-339 给出了列表的部分接口. 例10-3 改写例9-7 从键盘输入10个整数，用这些整数值作为结点数据，生成一个链表，按顺序输出链表中结点的数值。然后从键盘输入一个待查找整数，在链表中查找该整数，若找到则删除该整数所在的结点（如果出现多次，全部删除），然后输出删除结点以后的链表。在程序结束之前清空链表。,容 器,list ls,51,列表的模型,_head,size,heap,接口函数： begin() end() rbegin() rend() front() back() clear() size() empty() insert() splic() remove(),.,ls.begin(),ls.end(),/10_3.cpp #include #include using namespace std ; void main(void) list Link; /构造一个列表用于存放整数链表 int i, key, item; coutitem; Link.push_front(item); cout“List: “; / 输出链表,52,list:iterator p=Link.begin(); /此句何意？ while(p!=Link.end() /输出各节点数据，直到链表尾 cout key; Link.remove(key); cout “List: “; / 输出链表 p=Link.begin(); / 使P重新指向表头 while(p!=Link.end() cout *p “ “; p+; / 使P指向下一个节点 cout endl; ,53,声明了一个list类的迭代器p,并指向链表头。,将迭代器p当指针用。,运行结果： 输入10个整数依次插入表头: 4 3 6 7 8 9 0 3 6 4 4 6 3 0 9 8 7 6 3 4 请输入一个需要删除的整数: 4 6 3 0 9 8 7 6 3,54,产生容器对象的方式,产生空容器： 如 list slist; 又如：vector ivec; 生成特定大小的容器： 如 list ilist (1024); 又如：vector svec(32); 生成指定大小和初值的容器 如 list ilist (10，-1); 又如：vector svec(20，NULL);,用迭代器生成指定大小和初值的容器 若有 int ia8 = 1,1,2,3,5,8,13,21 ; 则：vector fib(ia，ia+8); 用已有容器生成新容器 若有 list slist1; 则 list slist2 (slist1);,可作容器元素的对象,不是任何类的对象都能作容器元素。容器的操作特性对该类有门槛要求： 1 可默认（无参的）构造的; 2 可拷贝构造的； 3 可赋值的； 4 对含有指针或引用的类，必须具有公有的、有深拷贝操作的、显式定义过的拷贝构造函数，以及类似的赋值函数，还要有相应的析构函数。,引用不可作容器元素,1 引用在创建时必须初始化为一个对象，而容器不能满足这一要求； 2 引用没有构造函数、析构函数和赋值函数的语义，即容器只支持对象语义，不支持引用语义。 下面的两个对象定义都是错误的： std:list ld(10); 或当 typedef Object ,关联容器,关联容器：容器是元素的集合，其中的元素逻辑上不再是线性排列的，即无序。但提供值或映射关系。 STL 提供四个关联容器： set : 元素的值不得重复，可快速查找； multiset : 元素的值允许重复，可快速查找； map : 一对一映射，元素的值不得重复，可基于关键字快速查找； multimap : 一对多映射，元素的值可重复，可基于关键字快速查找； 关联容器不需要预留空间，也不存在内存的再分配 关联容器一般采用平衡二叉搜索树作为底层存储结构。,容 器,set容器是顺序容器，它会将杂乱无章的元素按序放入set。它的元素值是单一的，既是索引，又是值本身。并且不得重复。特别适用于具有不重复特性的应用场合。若要剔除某篇文章中的某些词汇，则可首先建立“剔除集”容纳这些词汇，然后从文章中逐个读入单词，与set 比较： #include #include . set word_exclusion; . cintword; if ( !word_exclusion.count(tword) words tword + ; set中的元素应是升序排列的；可以用begin() 和 end()定位。,set容器,set st,61,set 的模型,heap,st. end(),st.begin(),set的元素组织采用了r-b tree. （也可以是vector）,空白,#include #include #include using namespace std; void main() double a5 = 4.4, 2.2, 3.3, 5.5, 16.6 ; set doubleSet( a,a + 5 ); cout ( cout, “ “ ) ); pair :const_iterator, bool p; p = doubleSet.insert( 13.8 ); /向集合容器中插入13.8 cout n *( p.first ) ( p.second ? “ was“ : “ was not“ ) “ inserted“; cout “ndoubleSet contains: “;,62,这叫“模板的显式实例化”。亦可用template class 。,copy( doubleSet.begin(), doubleSet.end(), ostream_iterator ( cout, “ “ ) ); p = doubleSet.insert( 5.5 ); / 向集合容器中插入已经存在的5.5 cout ( cout, “ “ ) ); cout “nlower_bound(3.5): “ *doubleSet.lower_bound(3.5) endl; cout “upper_bound(3.5): “ *doubleSet.upper_bound(3.5) endl; cout“equal_range(3.5):“*doubleSet.equal_range(3.5).first “ “*doubleSet.equal_range(3.5).second endl; cout“lower_bound(9.5):“*doubleSet.lower_bound(6.5) endl; cout“upper_bound(9.5):“*doubleSet.upper_bound(6.5) endl; cout“equal_range(9.5):“*doubleSet.equal_range(6.5).first “ “ *doubleSet.equal_range(9.5).second endl; ,63,lower_bound()：在有序区间内，按二分查找法，找出第一个与给定的元素相等的元素的位置，返回其迭代器。若没找到，返回其后边界。,upper_bound()：在有序区间内，按二分查找法，找出最后一个与给定的元素相等的元素的位置，返回其迭代器。若没找到，返回其后边界。,equal_range()：在有序区间内，按二分法查找是否存在一个与给定的元素相等的元素，若存在则返回其迭代器。若没找到，返回其后边界。,运行结果： doubleSet contains: 2.2 3.3 4.4 5.5 16.6 13.8 was inserted doubleSet contains: 2.2 3.3 4.4 5.5 13.8 16.6 5.5 was not inserted doubleSet contains: 2.2 3.3 4.4 5.5 13.8 16.6 lower_bound(3.5): 4.4 upper_bound(3.5): 4.4 equal_range(3.5): 4.4 4.4 lower_bound(9.5): 13.8 upper_bound(9.5) : 13.8 equal_range(3.5): 13.8 13.8,64,set容器是关联容器的典型代表，须从概念模型和实现方式两个方面来理解它。 概念上set的元素是杂乱无章的，各元素间没有次序，元素也不需要按值的大小排列，这是集合的本性。但在物理实现上，从简单性和效率上考虑，关联容器必须是有序的且是升序的。只不过对于用户是透明的，即不必让用户知道内幕。平衡二叉搜索树恰能满足这个要求。 可以用find()定位元素的位置；可以用 insert() 和erase()不指定位置只知道元素值即可操作。 关联容器对元素默认使用“排序(即所谓默认谓词)。,如何理解set,关联容器的实现是采用二叉树的存储结构，这就决定了底层的访问仍然是顺序的。 关联容器在实现上必须维持元素的有序性，这就决定了不能企图修改其中的元素对象。为此，set把 iterator 强制声明为 const_iterator；同理map 把 pair 中的 key强制声明为 const key ，但可以修改 pair 中的 value值。即,不可直接对关联容器的元素对象赋新值或调用它们的non-const方法。,为何要对iterator使用const,map容器的元素是一个个的key/value对pair对象，key通常是字符串,承担着索引职责，不可重复出现； value是数值，取值没有限制。 关联容器的find() 和 operator 方法反映了它在应用层面的“随机访问”性，但从底层实现看，仍然是顺序访问。所谓随机只是模拟随机。 字典就是典型的map的实例。,map容器,map mp,68,map 的模型,heap,mp. end(),mp.begin(),map中的每个元素 ，都是pair类的一个对象。pair类 是STL的一员。 此图是按vector组织的。其实map常用的组织形式是采用了R-B tree，也可以用数组。,first,size,second,value,key,69,map 的成员,size：集合中的元素个数。每个元素是个pair对象。 first： pair对象的第一项：索引(key)。 second： pair对象的第二项：值(value)。 find()：以key为查询依据，若找到则返回指向那个对 (pair)的iterator,否则返回end()。 begin()：返回指向集合的首元素的iterator。 end() ：返回指向集合的尾元素之外的iterator。 count() ：返回key在集合中出现的次数。 operator () ：返回key所对应的value。不存在则加 入，加入后其value为0。可以为右值，亦可左值。,70,map 的一个例子,请说出下面容器的含义： map table;,该容器的第一项(索引)是整数、第二项是 double型的set 的一个映射表table。即每个整数值都对应着一棵树的一个映射容器。,例如：要对某篇文章中的单词做统计，map是合适的工具： #include #include . map words;/用map保存单词名及出现次数 输入要计数的单词，并对每个单词出现次数计数: words “stutent” = 0; . 然后处理每个单词： while(cintword) / 读入单词在tword中 words tword + ; 显示结果: map:iterator it = word.begin(); for ( ; it !=words.end() ; +it ) coutfirst secondendl;,又如： #include #include #include using namespace std; void main() map stocks; /创建空的映射容器：键值为字符型，数值为浮点型 stocks“AAA“ = 363.50; stocks“BBB“ = 523.50; /向容器插入元素 map:iterator pos;/声明指向映射容器的迭代器 for (pos = stocks.begin(); pos != stocks.end(); +pos) coutfirstsecond endl; ,72,for (pos = stocks.begin();pos != stocks.end();+pos) pos-second *= 2; /price加倍 for (pos = stocks.begin();pos != stocks.end();+pos) cout first second first second endl; ,73,因为容器中没有”VVV” 元素,因此首先建立一个新对象，把“BBB”的value给新对象。,运行结果： stock: AAA price: 363.5 stock: BBB price: 523.5 stock: AAA price: 727 stock: BBB price: 1047 stock: AAA price: 727 stock: VVV price: 1047,74,75,方法一： int count = 0; if(!(count = words“student”) 这样，count会得到words中key为student的那个元素的值value。副作用是，一旦words中不存在key为student的元素，这段代码会自以为是的将其加入到words中，这可能并非是作者的本意，本意是想返回个0。,查询map中是否存在某个key,76,方法二： int count = 0; map:iterator it; it = words.find(“student”)； if( it != words.end() count = it -second; 此法使用了迭代子、 second域、 find()函数和end()函数。这样虽不如方法一快捷，可是不会有副作用。,方法三： int count = 0; string search_word(“student”)； if( words.count(search_word) count = wordssearch_word; 此法使用了count()函数和operator ()。也无副作用。,使用容器的要点,对于存放于容器的元素，如果是指向元素的指针，切记要对用完的对象析构，别指望容器会析构它们。 因为容器仅限于对所容纳的东西释放。当所容纳的是指针时，所指的对象并不在容器中。容器当然不知道它们的存在。 不要过高的要求容器。它的目标是“泛化和效率并举”，其他的都置之不顾。,适配器是一种接口类，是对原有类的“二次封装”。其存在的理由就是改造别的类，改造的手段是使用组合或聚集。 为已有的类保留适用的接口，去掉不适用的接口，提供新的接口。 目的是简化、约束、使之安全、隐藏或改变被修改类提供的服务集合。 事实上是一种设计模式：“将一个class的接口转换为另将一个class的接口，是原本因接口不兼容而不能合作的classes，可以一起运作”。,适配器,适配器,容器适配器 用来扩展7种基本容器，它们和顺序容器相结合构成栈、队列和优先队列三个新容器。 迭代器适配器 （详见后） 函数对象适配器 （详见后）,适配器,三种适配器,容器适配器,容器适配器是用来扩展7种基本容器和调整改造基本容器的类。 就是用另一个容器作为底层存储机制，用组合、聚集的方式，在内层容器外面又套了一层类，对外提供不同于内层容器的新接口。又称为“ 二次封装”。 由于是二次封装，它们都没有迭代器，也不支持随机访问和遍历。,适配器,容器适配器,栈容器 用适配器与一种基础容器结合，实现先进后出数据结构 例10-4：用标准库中的deque顺序容器生成一个整型栈stack。 队列容器 用适配器与一种基础容器结合，实现先进先出数据结构 例10-5：用标准库中的deque顺序容器生成一个整型标准队列Queue。 优先队列容器 用适配器与一种基础容器结合，实现按权重先出算法的数据结构,适配器,如： template class stack public: / . T ,82,模参带默认值,组合,使用stack： #include #include #include #include using namespace std; template /用于输出元素的函数 void popElements( T / 以容器List实现栈,83,创建三种stack,for ( int i = 0; i 10; +i ) iDequeStack.push( i ); iVectorStack.push( i ); iListStack.push( i ); cout “Popping from iDequeStack: “; popElements( iDequeStack ); cout “nPopping from iVectorStack: “; popElements( iVectorStack ); cout “nPopping from iListStack: “; popElements( iListStack ); return 0; ,84,三次调用“显示、出栈”函数,为三个栈放入数据,使用queue： #include #include using namespace std; int main() queue q; /创建空的队列容器 q.push( 3.2 ); q.push( 9.8 ); q.push( 5.4 ); /向空的队列容器添加元素 cout “Popping from q: “; while ( !q.empty() ) /输出元素后移除元素 cout q.front() ; q.pop(); return 0; ,85,使用priority_queue ： #include #include #include using namespace std; void main() priority_queue pq; /创建空的优先队列容器 pq.push( 3.2 ); /向空的优先队列容器添加元素 pq.push(