第十章第十章 STL 简介简介增熊锯焉录怨玛爷世赠哲终眉直门啦骸绚潦事碳朴奠辟我队泻垂展胆瓦吱第十部分STL简介教学课件第十部分STL简介教学课件10.1 标准标准 C+ 库库 标准的 C+ 不仅包含了全部标准 C 运行库（在原有库的基础上做了一些必要的增补和修改，以便支持安全类型），而且还增加了一些 C+ 自己的库。这些新增的库比标准的 C 库功能更强，这些 C+ 库包括：1 输入输出流库。2 语言支持库：包含从 C 运行库继承的成分，例如： 在 和 头文件中声明了 C+ 库对 和 头文件中声明的 C 运行库所 增加的实现限制； 鱼八枕痰苏罐采拎郝历阁魁幼潮恢趣较嗜献戍轩腋彼感烟心湖摇剑泼淘斋第十部分STL简介教学课件第十部分STL简介教学课件 在 头文件中的声明了内存动态管理功能； 在 头文件中声明了支持异常处理的功 能，例如，terminate 和 unexpected 函数等； 在 头文件中声明了用于运行时类型识 别的 RTTI (Run-time type identification) 。3 诊断库 提供一些组件，使得 C+ 程序能够发现和 报告错误。在 中声明了标准异常类； 头文件与 C 运行库中的 的作用 相同支持断言诊断。粘贾巍俞颂岛碍帐矩筋畏卫赊抽凹负扮拣弟惋钱遂易撞倡赚釜锯例宅垣势第十部分STL简介教学课件第十部分STL简介教学课件4 通用的实用库：该库提供的库成员既可以在编程中 被使用，又被其他 C+ 库的成员使用。这些库成员 包括 !=、= 等运算符的模板化版本，带 有 tuple（元组）模板函数的 pair 模板类，支持 STL 的一套函数模板对象和与 STL 一起使用的内存管理 函数模板对象（能使我们可以容易地修改存储分配 机制）。贵汉歇兼蚁冠泣氓术琐吉馋口蜡腾胀眉讫姐魁懈轰溢邓捏立羚钞辛哟石惫第十部分STL简介教学课件第十部分STL简介教学课件5 字符串库：提供了字符串模板类 basic_string 可能是我们曾经见过的最完整的字符串处理工具。 我们在 C 中要用数行代码才能完成的工作都可以用 字符串类的一个成员函数来代替，这些函数包括 append、assign、remove、insert、replace、resize、 copy、find、 rfind、compare、substr、find_first_of、 find_last_of、find_first_not_of、find_last_not_of 等。 此外还重载了运算符 =、+=、 等使这些运算更直 观地用于字符串运算。支持国际字符集的 wstring 类 是实例化 basic_string 产生的。由于该字符串模板类 与 iostream 的无缝结合，甚至无需使用 strstream。崎岛老望拟偿蚜避曼深饿卞啡饵邪嫁羹氮闰雹段面胜煌几外拇侈颓昌肩盗第十部分STL简介教学课件第十部分STL简介教学课件6 本地化库：该库用来调整字符集以便使程序能在不 同国家使用，包括货币、数字、日期、时间等。7 容器库：主要由标准模板库 STL 的容器类组成。8 循环子库：包括用于访问 STL 容器类的工具流及流 缓冲区。9 算法库：所提供的算法都是模板函数，并使用循环 子来完成 STL 容器上的运算，例如： adjacent_find、random_shuffer、remove_copy、rotate、 remove、replace_copy、includes、search、sort、swap 等。渴佯氟百哲枢澜帛粹手邻怠酉敬膝似蒋镜杆宦弓误湃股谨役持蚤伙这琼畜第十部分STL简介教学课件第十部分STL简介教学课件10 数字运算库：该库的目的是允许编译器的实现者在 用数字运算时充分利用低层机器结构。使得高层的 数字运算库函数可以使用这些数字运算库，以便更 高效地实现函数的运算，并且不必为每种不同的机 器都编写数字运算的实现代码。这个数字库还包括 了以 float、double 和 long double 的形式实现的高层 数字运算类。蘸焦逐粥谰浇压峦郭殷阀缄棺彰淖先紧蘸除孟植歌冠裕就螺著蓑赵懊宰讹第十部分STL简介教学课件第十部分STL简介教学课件10.2 标准模板库标准模板库 STL第六章已经论述了 C+ 中模板的强大的功能以及为程序设计提供的重用机制和灵活性。模板是实现通用目的的编程工具，使用模板可以方便地解决能施加于不同类型数据的通用编程问题。C+ 的 STL 是一个功能强大的库，它是建立在模板机制上，能够满足用户对存储管理不同类型数据的通用容器和施加在这些容器上的通用算法的巨大需求，并且具有完全的可移植性。因此在寻求程序的解决方案时，应该首先在 STL 中寻求恰当的容器和算法。坯蛀疾竞旅浴艺跑术驻淡虑法皆肢婆泵菇甥滩巢坟搬澳酌蹋乾唐抡畏翌宦第十部分STL简介教学课件第十部分STL简介教学课件STL 是一个通用性极高的编程工具，这种通用性不仅表现在可以使用通用的容器存储和管理任意类型的数据，更重要的是可以对不同的容器施加统一通用的算法和操作。实现这种通用性的关键思想就是：通过引进一个间接层对象对不同结构的数据容器进行统一的访问操作，从而简化了对容器的操作，使得实现操作的算法和函数通用化。这种思想是 STL 的设计原则之一，也是软件设计中一个重要设计思想。 例例10-110-1 是一个使用间接类 istackIter 简化对整数堆栈类 istack 进行操作的实例。弦窒椒邹讽争煮啃锄谱吭絮暑穴吠胶宇舷绦茶愧验疯霖豆鄂轰址抬研况匿第十部分STL简介教学课件第十部分STL简介教学课件分析：其中的 istackIter 是一个循环子类，是堆栈类 istack 的友元类。我们可以把 istackIter 对象当作仅能与 istack 对象协同工作的超指针，它的功能是扫视 istack，并能在中取值。通过它简化了对整数堆栈 istack 的操作，并使对堆栈元素的访问独立于堆栈的结构。在 STL 中对容器访问的简化和独立就是通过循环子实现的，循环子可以无须依据某种特定容器的数据结构而完成对容器元素的访问，从而使得数据的存储结构与施加于数据的操作相互独立。眠铂初献与放踏条抗曾忌鞍诱屋嗽鞠默灰炭暮米巴胖尼绝串子喀术阂喘恿第十部分STL简介教学课件第十部分STL简介教学课件这种独立性的优点使我们能够在学会了使用 STL 中一种容器的基础上，就能很方便地掌握对 STL 的其他容器的使用。当然，熟悉使用 STL 中处理问题的思想和方法是需要花费一定时间的。幸运的是，使用 STL 处理问题的方法具有统一的模式，因此很容易从一种 STL 工具的使用推广到其他 STL 工具使用。例例10-210-2 是一个使用 int 数据类型将 STL 的 set 容器类实例化，并创建一个 intset 的实例。玲屹尾甫蛙络酪冉暴荤炼鸣投异猖独诉瘪索毡挺棵摧森葫茫旬源辐乙计卒第十部分STL简介教学课件第十部分STL简介教学课件分析： set 的第一个参数是包含在这个集合中的元素类型， 第二个参数产生一个运算，用于在使用整型堆栈的 成员函数 insert 插入元素时的排序算法。 copy 函数展示了使用循环子访问整型堆栈 intset 的 功能。set 的成员函数 begin 和 end 的返回值是循环 子值。copy 函数就是使用这两个值作为它运算的开 始点和结束点，并在由它们产生的边界之间简单移 动，从而把 intset 中的元素拷贝到由第三个参数 （也是一个循环子），指定的输入输出流的确定位 置上。这样就实现了将一个 int 对象序列放到了 cout 中，并在两个 int 对象之间加入行分隔符。毛茶描泉冬泵循楔擎努矛糜宛书财依草印企恃脚义丛喀搓兆因郝纫败筹茶第十部分STL简介教学课件第十部分STL简介教学课件 copy 函数实际上可用于任何场合，它只需要通过三 个循环子来访问和传输数据即可。STL 中的其他算 法和函数也都遵循了 copy 函数的这种形式，并只须 简单地管理循环子（额外的替代间接层）。例例10-310-3 是使用一个自定义类 Hstring 将 STL 的 set 容器类实例化，并创建一个文本文件中获取所有不重复的单词的实例。该实例与例10-2 的唯一的区别在于 set 的元素类型是 Hstring 而不是 int。被插入的词是从一个文本文件中读入的，并用 strtok() 函数完成单词分解。其他操作与对 intset 的操作完全一样。衡疾鬼你尝汐洪莱纶使禄麓恳骏尧列姜律钩薪欢灭钞答错锻逢箭釜箱捞学第十部分STL简介教学课件第十部分STL简介教学课件10.3 STL 的组成的组成标准模板库 STL 是由容器类模板，用于访问这些容器的循环子类模板和可以通过循环子在这些容器上实现的各种算法类模板以及函数类模板组成的。STL 为这种标准算法和函数（包括用户定义的函数）借助循环子在容器上实现的应用建立了统一的规则。10.3.1 标准容器标准容器（Standard Containers)标准库中定义了两种标准的容器：1 序列容器（Sequence）向量 vector、表 list 和双向队列 deque。腔委件止下椎羡捶烙榨漾皆衔府廓禹咳红葵努姻薯熄焚终惑烹杠值卷响意第十部分STL简介教学课件第十部分STL简介教学课件2 序列转接器容器（Sequence Adapter）序列转接器：堆栈 stack、队列 queue 和优先级队列priority_queue。3 关联容器 (Associative container)映射 map、multimap 和集合 set、multiset。4 预定义数组、字符串类 string、数值数组类 valarray 和位集合 bitset 均可以视为容器，但不是标准容器。标准容器的成员绝大部分都具有共同的成员名，下面的表格中分类列出这些共同的和几乎共同的成员名以及它们的意义。帽衙究姨组辐恍五毁娥玄毁港询儒渐秉桔诡馆孙愉腔舅论某散游苑舵勉夜第十部分STL简介教学课件第十部分STL简介教学课件类型成员value_type 元素类型allocator_type 内存管理器类型size_type 下标，元素计数类型difference_type 循环子之间差的类型iterator 循环子，相当于 value_type*const_iterator 常循环子，相当于 const value_type*reverse_iterator 逆序循环子，相当于 value_type*const_reverse_iterator 常逆序循环子，相当于 const value_type*reference 元素引用，相当于 value_type&const_reference 元素常引用，相当于 const value_type&key_type 关键字类型（只用于关联包容器）mapped_type 映射值类型（只用于关联包容器）key_compare 比较标准类型（只用于关联包容器）卯咏董猛疽饵凑镑浩她腑坤绸獭市洱棕顾昆焕单血姻苛阜漏彬猜宛妇牢旭第十部分STL简介教学课件第十部分STL简介教学课件循环子操作begin() 指向第一个元素end() 指向最后一个元素的后一个位置rbegin() 指向逆序的第一个元素rend() 指向逆序的最后一个元素的后一个位置访问元素操作front() 访问第一个元素back() 访问最后一个元素 无测试的下标访问（不用于 list）at() 有测试的下标访问（只用于 vector 和 deque）颈姿颊亩戳寻痪凡妹锨报脂企淘邀赞庚袜怎斑头粥濒踩剩靴糖屑蛤运腰刊第十部分STL简介教学课件第十部分STL简介教学课件堆栈和队列操作push_back() 将新元素加入到尾部pop_back() 移出最后一个元素push_front() 将新元素加入头部（只用于 list 和 deque）pop_front() 移出第一个元素（只用于 list 和 deque）表操作insert(p,x) 将元素 x 加入到 p 之前insert(p,n,x) 在 p 之前加入 n 个 x 的拷贝insert(p,first,last) 在 p 之前加入 区间 first, last) 中的序列erase(p) 删除 p 处的元素erase(first,last) 删除区间 first, last) 中的序列clear() 清除所有的元素敛战葡鹤精遂椿赤薪禹大诸端楼子需秧桂骤驯喂素挞幅隙捎匙痹宫但贝顷第十部分STL简介教学课件第十部分STL简介教学课件其他操作size() 获取元素个数empty() 测试包容器是否为空max_size() 最大可能的包容器的大小capacity() 为向量包容器分配的空间（只用于 vector）reserve() 为扩充向量包容器保留空间（只用于 vector）resize() 改变包容器的大小（只用于 vector, list 和 deque）swap() 交换两个包容器中的元素get_allocator() 获取包容器的内存管理器的副本= 测试两个包容器的内容是否相等!= 测试两个包容器的内容是否不同 测试一个包容器是否在另一个包容器字典序之前圾旨狈庭裸彬访疮貉虹栈使镶蕊慑翟述魂掺杂呢撑疟抉褒蜒震癣横睦弱厘第十部分STL简介教学课件第十部分STL简介教学课件构造函数，析构函数container() 构造一个空容器container(n) 用缺省值构造 n 个元素的容器（不能用于 关联包容器）container(n,x) 构造具有 n 个 x 拷贝的容器（不能用于关 联包容器）container(first,last) 初始化容器区间 first, last) 上的元素container(x) 容器拷贝构造函数container() 析构容器和它的全部元素葡负晨撑儒豪富藤借休于软不哪咀再堵啸知镶蕴缘茄旋嘱榜酬漾悠鸽秀埃第十部分STL简介教学课件第十部分STL简介教学课件分配操作operator=(x) 从容器 中 x 元素拷贝分配assign(n,x) 为容器分配 n 个 x 的拷贝（不用于关联容器）assign(first,last) 在容器的 first, last) 区间中分配关联操作operator(k) 访问带有关键字 k 的元素（用于具有唯一关 键字的包容器）find(k) 查找带有关键字 k 的元素lower_bound(k) 查找带有关键字 k 的第一个元素upper_bound(k) 查找带有大于 k 的关键字的第一个元素equal_range(k) 查找带有关键字 k 的元素的 lower_bound 和 upper_boundkey_comp() 获取关键字比较对象的拷贝value_comp() 获取映射值比较对象的拷贝休娥锣啥撰蜕唐冈掠浪痞钠尿墩育映留砾钧募宏饮鼻刮忿胶颊络撮截抹健第十部分STL简介教学课件第十部分STL简介教学课件标准容器的操作比较 操作 表操作 Front 操作 Back 操作 循环子vector const O(n)+ const+ Ranlist const const const Bideque const O(n) const const Ranstack constqueue const constpriority_queue O(log(n) O(log(n)map O(log(n) O(log(n)+ Bimultimap O(log(n)+ Biset O(log(n)+ Bimultiset O(log(n)+ Bistring const O(n)+ O(n)+ O(n)+ Ranarray const Ranvalarray const Ranbitset const Ran乖组坠费矮逢分精揉糠售郁赁凶渗喜买拖郎悯马翰距普来诛拴节湿苛纶莹第十部分STL简介教学课件第十部分STL简介教学课件表中各种容器所对应的表项的含义如下： 空表项 - 表示容器无此项操作。 const - 表示容器此项操作的时间复杂度为常量。 O(n) - 表示容器此项操作的时间复杂度与容器中元 素个数 n 的线性相关。 O(n)+ - 表示容器此项操作的时间复杂度与容器中 元素个数 n 线性相关并且还需要增加一些附加操作 时间花费。浸骄疡瞬肺巷俱蔫彻度柱妹默丫悲琉毡涯礁驮年蚀夹郭擒撼了雌柠箱澳担第十部分STL简介教学课件第十部分STL简介教学课件 O(log(n) - 表示容器此项操作的时间复杂度与容器 中元素个数 n 对数相关。 O(log(n)+ - 表示容器此项操作的时间复杂度与容器 中元素个数 n 对数相关并且还需要增加一些附加操 作时间花费。 Ran - 表示容器对应的循环子为随机访问循环子。 Bi - 表示容器对应的循环子为双向访问循环子。兵圆噎李袍园换雹吁颓痈牢菜幽垄怒绍赌圈乘干薯批吹蚤熏涉惦湃灯氦疽第十部分STL简介教学课件第十部分STL简介教学课件1vector该标准容器是一个定义在 namespace std 中的模板，该模板的原型声明在头文件 中。它的数据结构很像一个数组，所以与其他容器相比，vector 能非常方便和高效访问单个元素。因此，在 vector 中提供随机访问循环子。抽呸催李谢匪秦摘竭骡肚闽门也葬繁伯完了锤劲济裴根盲操青洁慧跺械袁第十部分STL简介教学课件第十部分STL简介教学课件2list该标准容器是一个定义在 namespace std 中的模板，该模板的原型声明在头文件 中。list 是一个对容器元素的插入和删除操作进行了优化的序列。但与 vector 和 deque 相比，对元素的下标访问操作的低效是不能容忍的，因此 list 不提供这类操作，即不提供随机访问循环子，而提供双向循环子。这意味着 list 是典型的通过使用双链表实现的序列结构。除了通用的序列操作外，list 还提供了一些特别适合 list 结构的管理操作： 场渴爷属拼桨超眷扶挑韶瞧夕庙幻廉闯挥艰晨颈蹦讲钳好契蘑孟例伸蜀炔第十部分STL简介教学课件第十部分STL简介教学课件template class T, class A = alloctor class listpublic: / list-specific operations: void splice(iterator pos, list& x); / move all elements from x to before pos in this list / without copying. (Note &x != this) void splice(iterator pos, list& x, iterator p);/ move *p from x to before pos in this list without / copying. (If pos=p|pos=+p, no change occurs.)尾滨杨娜雅奶诺糙昧坯杏瑟剃淳椿市岂券滇际噎箔茫殖栅季监痉弃乏瞬荚第十部分STL简介教学课件第十部分STL简介教学课件 void splice(iterator pos, list& x, iterator first, iterator last);/ move elements infirst,last) from x to before pos in / this list without copying. (If &x=this, the range first, / last) must not include the element pointed to by pos.) void merge(list&)/ merge sorted lists template void merge(list&, Cmp); void sort(); template void sort(Cmp);獭俞撒码鲍册孪柔养咖致隔妹遣酶袜幸老岛牵埔怀揉惜叫归戏敲玄贩蓟奸第十部分STL简介教学课件第十部分STL简介教学课件对于 list，front 操作和 back 操作都同样高效和方便。因此，如果希望使用 list 编写的代码演变为能应用于多种其他容器的通用代码，则使用更具广泛适用性的 back 操作是最好的选择。list 元素的插入和删除操作尤为高效，所以 list 更适合在插入和删除操作频繁的应用中使用。颗淫倡耪矫纳病豁茄瑶胞迂榨谁擦袒剐卸叙锥粥辽桶混膛呻两吻暮埃燎谩第十部分STL简介教学课件第十部分STL简介教学课件3deque该标准容器是一个定义在 namespace std 中的模板，该模板的原型声明在头文件 中。deque 是一个双向队列，也是一个优化序列。在 deque 两端的操作与 list 一样高效，对元素的下标操作的效率又与 vector 类似，而对容器元素的插入和删除操作的效率则介于 list 和 vector 之间。实刚伐足刨崩潘议误泪琐痒颓淘邀杏啡窝宙揉旷吼荷姚蓝涸阻肩炕虚妓灾第十部分STL简介教学课件第十部分STL简介教学课件4stack这个容器转接器是一个定义在 namespace std 中的模板，该模板的原型声明定义在头文件 中：template class T, class Cont = deque class stack public: typedef Cont:allocator_type alloctor_type; typedef Cont:value_type value_type; typedef Cont:size_type size_type; explicit stack(const allocator_type& al = allocator_type() const; 舷惮肆孝烘浑绳士胚第撕排储滇震均走查荤咖拦还难茨晌惯浇友骤班腑橙第十部分STL简介教学课件第十部分STL简介教学课件 bool empty() const; size_type size() const; allocator_type get_allocator() const; value_type& top(); const value_type& top() const; void push(const value_type& x); void pop();protected: Cont c; ; 柯轩蒸彪沪啡缀屹隅菜肉揉杏醒豌壹夫盈瘫伶潦亢此培忧嗡驰嗅铜雌惨敝第十部分STL简介教学课件第十部分STL简介教学课件5queue 这个容器转接器是一个定义在 namespace std 中的模板，该模板的原型声明定义在头文件 中：template class T, class Cont = deque class queue public: typedef Cont:allocator_type alloctor_type; typedef Cont:value_type value_type; typedef Cont:size_type size_type; explicit queue(const allocator_type& al = allocator_type() const; 孵弓夸愉季氨祭泼碍闪涨刚渤雷菠树宽车钙罕磨佃熔壳歧岿鱼申肃泊季屎第十部分STL简介教学课件第十部分STL简介教学课件 bool empty() const; size_type size() const; allocator_type get_allocator() const; value_type& top(); const value_type& top() const; void push(const value_type& x); void pop(); protected: Cont c; ;嫂闲毫第宜阳核帐小敖慑贬督庞涧也框匆洋刀汝采隅亩哇考济洒搏晋汹浑第十部分STL简介教学课件第十部分STL简介教学课件6priority_queue 该容器转接器是一个定义在 namespace std 中的模板，该模板的原型声明定义在头文件 中：template class T, class Cont = vector, class Pred = less class priority_queue public: typedef Cont:allocator_type alloctor_type; typedef Cont:value_type value_type; typedef Cont:size_type size_type; 禽钠角腮谊蓑守腥暇秀俗英钩落懦俐幕曳公涌笆裂淑和减段现础蜗懂挣窟第十部分STL简介教学课件第十部分STL简介教学课件 explicit priority_queue(const Pred& pr = Pred(), const allocator_type& al = allocator_type(); priority_queue(const value_type *first, const value_type *last, const Pred& pr = Pred(), const allocator_type& al = allocator_type(); bool empty() const; size_type size() const; allocator_type get_allocator() const; value_type& top(); const value_type& top() const; 锯灸椭夺廖谈睹轿铡垒冰辐娥描真揩辫饵眶玩臀簿荫移多根苗缮蒙隔橙外第十部分STL简介教学课件第十部分STL简介教学课件 void push(const value_type& x); void pop(); protected: Cont c; Pred comp; ;池概该触亨栽芋簿专群乃杉村铭署删兔富侍冯票熟雪炮觉印刑忿嘱和盈旧第十部分STL简介教学课件第十部分STL简介教学课件7map该标准关联容器是一个定义在 namespace std 中的模板，该模板的原型声明在头文件 中。 map 是一个元素对（关键字，映射值）序列，它提供了以关键字为基础的快速检索。map 中的每一个关键字必须是唯一的。map 提供双向循环子。该容器除提供通用的容器属性和操作外，还增加了一些与 map结构对应的特定属性和操作：辟醒孰视禹塘项拢夫情周暮分兼蜂匀戏味唬种沽逮晤椰赂虎瀑闷从姜瞒静第十部分STL简介教学课件第十部分STL简介教学课件template class Key, class T, class Pred = less, class A = allocator class map public: typedef Key key_type; typedef T referent_type; typedef Pred key_compare; typedef A allocator_type; typedef pair value_type; typedef A:size_type size_type; typedef A:difference_type difference_type; 曰旁捕童裕刨叛穆顺基留页蚊电甜晨左澄豢捕沫从豺邑胞篮汕危懒镶待娄第十部分STL简介教学课件第十部分STL简介教学课件 typedef A:rebind:other:reference reference; typedef A:rebind:other:const_reference const_reference; typedef T0 iterator; typedef T1 const_iterator; typedef reverse_bidirectional_iterator reverse_iterator; typedef reverse_bidirectional_iterator const_reverse_iterator; 沾荣立趁郸良侠掉糜湾令素顶缠琶笛圣闰汉丁婴抵痔酣铬刚哄泉蘑僚债验第十部分STL简介教学课件第十部分STL简介教学课件 / map operations: iterator find(const Key& key); const_iterator find(const Key& key) const; size_type count(const Key& key) const; iterator lower_bound(const Key& key); const_iterator lower_bound(const Key& key) const; iterator upper_bound(const Key& key); const_iterator upper_bound(const Key& key) const; pair equal_range(const Key& key); pairequal_range(const Key& key) const; ;征儒毯傻垮亚爽摄晓誊吨胡列靖谚叉纺嗓岩菌糊队哟琅夸曲链让枢嫉阅拒第十部分STL简介教学课件第十部分STL简介教学课件8multimap该标准关联容器是一个定义在 namespace std 中的模板，该模板的原型声明在头文件 中。multimap 除了元素对的关键字不必须唯一外，其他与 map 相同。湿附秘液设静夸驳滁噎丢件魏景巩滨扔谊艾与牙洁亚助醛爹姆抡洗诺搞蔽第十部分STL简介教学课件第十部分STL简介教学课件9set该标准关联容器是一个定义在 namespace std 中的模板，该模板的原型声明在头文件 中。 set 可以被视为只有关键字而没有相关的映射值的 map，因此 set 的用户接口也发生了微小的变化，即成员类型中没有：typedef Key value_type;typedef Cmp value_compare操作中没有元素的下标访问操作。烫邱鸭耕钵伙宪堵蝗飘蔼棵辰诅轻黔火帜熏淳影宜哲习脖造吊纶车嫌记颗第十部分STL简介教学课件第十部分STL简介教学课件10 multiset该标准关联容器是一个定义在 namespace std 中的模板，该模板的原型声明在头文件 中。multiset 除了元素不必须唯一外，与 set 相同。11 stringbasic_string 是一个定义在 namespace std 中的模板，该模板的原型声明在头文 中。basic_string 提供了下标访问操作、随机访问循环字和一个容器的几乎所有的符号工具。不过 basic_string 不提供选择字符以外的其他类型作为容器的元素类型的功能。冒砒碎疟几吼锅朗彭颓伍酌苛稼秸疤贤株仇没涉悯哨井侠跋墅射矾评脉宴第十部分STL简介教学课件第十部分STL简介教学课件12 valarrayvalarray 是一个定义在 namespace std 中的模板，该模板的原型声明在头文件 中。valarray 是一个用于优化数值计算的向量，但是不能试图将它作为一个通用容器。valarray 提供了许多有用的特定数值操作，然而对于标准的容器通用操作，它只提供了 size 和下标访问操作。用于 valarray 的循环子是随机访问循环子。轨查踪距剿微哗伍职小判项逊萨化墟枣娠刨动卓兜岗俩狸窘愁锋胺枣比堪第十部分STL简介教学课件第十部分STL简介教学课件13 bitsetbitset 是一个定义在 namespace std 中的模板，该模板的原型声明在头文件 中。在系统中经常用一个标志集合（这些标志指示一些如 good/bad, true/false 和 on/off 等双态值）来表示状态。bitset 通过产生一个 N 位的小集合和大量的相应的位操作为实现上述需求提供高效、方便的工具。bitset 提供了三个版本的构造函数：桑从流该综贝街确涎判闲扫捧薪松嫡帧潜闽晌掐忌淆朗柔昭芋经郡仔出酥第十部分STL简介教学课件第十部分STL简介教学课件template class bitset public: / constructor: bitset(); / N zero-bits bitset(unsigned long val); / bits from val template / T is a character trait explicit bitset(const string& str, stringsize_type pos = 0,stringsize_type n = string:npos); / bits from str ;磐豪兹汪谣侦返徽媚塔泌狮墒咸垣哭兼涌通帘榨绅罩寨紊变贯橱斜淘屎骤第十部分STL简介教学课件第十部分STL简介教学课件bitset b1;/ 0000000000bitset b2 = 0xaaaa;/ 1010101010101010bitset b3 = 0xaaaa;/ 00000000000000001010101010101010bitset b4(1010101010); / 1010101010bitset b5(10110111011110,4);/ 0111011110bitset b6(10110111011110,2,8);/ 0011011101bitset b7(n0g00d);/ invalid_argument thrownbitset b8 = n0g00d;/ error: no char* to bitset conversionbitset 提供的操作有两类,一类是对整个集合操作而另一类是位操作：驶盟晋星昭鄙猪郸能涛侧鳞庶恼旷泥臭忿餐鸯溶箱赊正避保葡她殷狭梁堡第十部分STL简介教学课件第十部分STL简介教学课件template class bitset public: class reference; reference operator(size_t pos); / bi bool operator(size_t pos) const; reference at(size_t pos); bool at(size_t pos) const; bitset& operator&=(const bitset& rhs);/ and 琢京认驻婿疑愉帧币逆蚁醋返谐宋玖孺毯捡居伞篙晒抄噪减图沸归忧穗究第十部分STL简介教学课件第十部分STL简介教学课件 bitset& operator|=(const bitset& rhs); / or bitset& operator=(const bitset& rhs); / exclusive or bitset& operator=(const bitset& pos); / logic left shift (fill with 0s) bitset& operator=(const bitset& pos); / logic right shift (fill with 0s) bitset& set(); / set every bit to 1 bitset& set(size_t pos, bool val = true); / bpos = val bitset& reset(); / set every bit to 0 bitset& reset(size_t pos); / bpos = 0; 乓询走贪洱绸何著颠货锻蔷拼币助荫甚唱六荡朝丸房硅悬虎奶锭找请时复第十部分STL简介教学课件第十部分STL简介教学课件 bitset& flip(); / change the value of every bit bitset& flip(size_t pos); / change the value of bpos bitset operator(size_t pos) const;/ make shifted set bitset operator(size_t pos) const;/ make shifted set bitset operator(); / make complement set ;其中用于实现 bitset 集合中每个位元素的位操作的引用类 reference 的定义如下：捣该狂貌浓小皖炊止烃曙讲停饿搅碰找生打窥陋蒙莎姜烂衅碌沤寓陕素巡第十部分STL简介教学课件第十部分STL简介教学课件class reference / reference to single bit friend class bitset;reference();/ bi refer to the (i+1)th bitpublic: reference();reference& operator=(bool b); / for bi = b;reference& operator=(const reference& x); / for bi = bj;bool operator() const; / return bi;operator bool() const; / for x = bi;reference& flip();/ bi.flip();碰泊钒椽予闹仅抛甩命怒铃拙勃梗后杭渔超愿恒拟帖铸氓受瞅是吕跪础茵第十部分STL简介教学课件第十部分STL简介教学课件10.3.2 算算 法法 和和 函函 数数(Algorithm and Function Object)容器只有被诸如获取容器大小、循环访问、复制、排序和搜寻等基本操作支持才是真正有效的。标准模板库提供的算法用于能满足用户对使用容器的通用和基本的需要。函数对象提供了一种机制，通过这种机制用户可以定制标准算法的行为。函数对象为使用一个算法完成对用户数据的操作提供所需要的关键信息。因此，重要的是如何定义和使用这些函数对象。能鸡彪谜陡填如雹晶炔聚夏晌昏婴倒燕乏甚轴偏蔑讹香即氓苦敏淫涝匿诗第十部分STL简介教学课件第十部分STL简介教学课件标准模板库中的算法覆盖了大多数在容器上的操作，例如，往返移动、排序、搜寻以及插入和删除元素等。标准算法都是定义在 namespace std 中的模板,所有的算法模板的原型声明在头文件 中。下面的 7 个表中列出了各种算法模板的功能：表1 中所列的操作用于从序列中提取元素信息或在序列中寻找元素位置，而不修改元素值。此佐汽就殆雀爹鸽俗箩农冶芳糕虑恶撩蹄茵盗癣帐捕析疼银狐疲庆魏梧搬第十部分STL简介教学课件第十部分STL简介教学课件不修改序列的操作（表1）for_each 对序列中的每一个元素进行操作。find 在序列中寻找第一个等于指定值元素。find_if 在序列中寻找指定断言的第一个匹配。find_first_of 从一个序列中寻找另一个序列中的值。adjacent_find 在序列中寻找与断言匹配的元素的相邻对。count 在序列中计算指定元素出现的次数。count_if 在序列中计算与断言匹配的元素出现次数。mismatch 寻找两个序列中第一个不相同的元素。equal 如果两个序列中元素两两相等，则返回真search 寻找序列中第一个指定字串。find_end 寻找序列中最后一个指定字串。search_n 寻找序列中第n个等于指定值的元素。舞需秆震莲岩等代沤嘴品翘锈处绸前案思俐舜刷卯单盈遂退摊涤读忠矿拓第十部分STL简介教学课件第十部分STL简介教学课件表2 中所列出的操作均可以用于修改序列中的元素值。修改序列的操作（表2）transform 对序列中的每一个元素施加一个操作。copy 从序列的第一个元素开始复制整个序列。copy_backward 从序列最后一个元素开始复制整个序列。swap 交换两个元素。iter_swap 交换两个由循环子指定的元素。swap_ranges 交换两个序列中的元素。 replace 用指定值替换序列中具有指定值的元素。replace_if 用指定值替换序列中与断言匹配的元素。replace_copy 复制序列并对副本执行 replace 操作。replace_copy_if 复制序列并对副本执行 replace_if 操作。fill 用指定值替换序列中的每一个元素值。fill_n 用指定值替换序列中前 n 个元素值。尼孽晚旁乳对退借宣炯诞埋串胆悲许乎墒琵荔翰续白箱按淌乃履罐钨怂奶第十部分STL简介教学课件第十部分STL简介教学课件修改序列的操作（续表2）generate 用指定操作结果设置序列中每一个元素值。generate_n 用指定操作结果设置序列中前 n 个元素值。remove 删除序列中具有指定值的元素。 remove_if 删除序列中与指定断言匹配的元素。remove_copy 复制序列并删除副本中具有指定值的元素。remove_copy_if 复制序列并删除副本中与断言匹配的元素。unique 删除序列中相等的相邻元素。unique_copy 复制序列并删除副本中相等的相邻元素。reverse 倒置序列中的元素顺序。reverse_copy 复制序列并将副本的元素顺序倒置。rotate 旋转序列中的元素。rotate_copy 复制序列并旋转副本中的元素。random_shuffle 移动序列中元素到一个统一的分布状态。至火恤癸畔谤家矣救差撩豁粮蛤胳讽事洲鉴蝇最英裂测蟹购酷柏碧乐寺涉第十部分STL简介教学课件第十部分STL简介教学课件表3 中所列出的操作用于序列中元素的排序、搜索和基于有序序列的管理。序列排序操作（表3）sort 具有平均效率的排序。stable_sort 排序中顺序无须改变的元素不移动。partial_sort 使序列的前半部分有序的部分排序。partial_sort_copy 部分排序并复制有序的前半部分。nth_element 序列中第 n 个元素之前的部分排序。lower_bound 在有序序列中获取小于指定值的子序列。upper_bound 在有序序列中获取大于指定值的子序列。equal_range 寻找有序序列中插入指定值的最大范围。binary_search 二分法搜索有序序列中的指定值元素。merge 合并两个有序序列。inplace_merge 合并序列中的两个连续的有序部分。即蝴瞥谷您抑没亏费颤器笼侥蕊趴鳞巩潭供第邦蜕阉撮澄景晦纺渭刹桥映第十部分STL简介教学课件第十部分STL简介教学课件序列排序操作（续表3）partition 将符合断言的元素排序并置于序列起始部分。stable_partition 将符合断言的元素排序并置于序列起始部分， 但排序中顺序无须改变的元素不移动。集合算法（表4）includes 检测序列是否是另一个序列的子序列。set_union 创建有序并集。set_intersection 创建有序交集。set_difference 在第一个序列中创建两个序列的有序差集。set_symmetric_difference 创建两个序列元素的有序差集。亩祭漂双舅皱服扼吼韦趾截至满满壁赵在甸给泄巷怂烽电藻神狗渝康隋嗜第十部分STL简介教学课件第十部分STL简介教学课件表5 中所列出了将序列按照堆结构的操作。堆操作在状态上仍然保持为一个序列，使得在需要的时候能够使用序列的操作对堆的元素进行相应的操作。堆操作算法（表5）make_heap 使序列作为一个堆来使用。push_heap 增加元素到堆中。pop_heap 从堆中删除元素。sort_heap 堆中元素排序。缆熊灿拖深贯眯孕滇秀苯支会唐傀龚让揽芍速吧稠日闻洋病扎楷垮脚辛齿第十部分STL简介教学课件第十部分STL简介教学课件表6 中的操作用于建立在比较操作上的选取序列元素。表7 中的两种置换操作均返回布尔标志，表示序列是否已经按字典顺序或逆序排列。最小和最大算法（表6）min 获取两个元素值中的较小值。max 获取两个元素值中的较大值。min_element 获取序列中的最小值。max_element 获取序列中的最大值。lexicographical_compare 判别两序列的字典顺序哪个在前。置换算法（表7）next_permutation 逆字典顺序对序列进行一次置换prev_permutation 按字典顺序对序列进行一次置换前倡匙易状藤赴铃绽蒲远哆谆征妇限绞固密桓跋扳龟缘悔挛献吐灼惦声距第十部分STL简介教学课件第十部分STL简介教学课件标准函数对象也是定义在 namespace std 中的模板，所有函数对象的原型声明在头文件 中。下面的 3 个表中列出了各种函数对象的功能：断言函数对象（表1）函数对象名 运算目数 运算表达式equal_to Binary arg1 = arg2not_equal_to Binary arg1 != arg2greater Binary arg1 arg2less Binary arg1 = arg2less_equal Binary arg1 = arg2logic_and Binary arg1 & arg2logic_or Binary arg1 | arg2logic_not Unary ! arg隶洪正杭笨萌柑莱夸哨壹隅舔搂男权道撼沫唤景了辰涤傍丽兼询堆钵牟嫌第十部分STL简介教学课件第十部分STL简介教学课件依据表1 和表2 所列出的标准函数对象，用户可以为自定义类定义断言运算和算术运算，并在容器的算法中使用这些运算。算术操作函数对象（表2）函数对象名 运算目数 运算表达式plus Binary arg1 + arg2minus Binary arg1 - arg2multiplies Binary arg1 * arg2divides Binary arg1 / arg2modulus Binary arg1 % arg2negate Unary - arg 巳惑傅烁量衡疑是网仓炽纹莫薄车媳觉芜肮缄函慢铆绘演截吹笼婶精粪兜第十部分STL简介教学课件第十部分STL简介教学课件标准模板库提供了一些函数对象用于构造定制的函数对象： Binder 类函数对象允许通过将一个参数绑定为值， 使一个双目函数对象作为单目函数对象使用。 成员函数的 Adapter 类函数对象允许将一个成员函 数作为一个算法的参数。 成员函数指针的 Adapter 类函数对象允许将一个指 向成员函数的指针作为一个算法的参数。 Negate 类函数对象允许用户表达一个断言函数的相 反含义。屁贱省客群贱龟阅屑妒硬悲麻艾哟茸追燎辛诧柜嘴酉万坐剪腻矫卑闽赘魄第十部分STL简介教学课件第十部分STL简介教学课件Binders、Adapters 和 Negaters 类函数对象函数对象名 返回类型 功能bind2nd(y) binder2nd 调用y为2nd参数的双目函数bind1st(x) binder1st 调用x为1st参数的双目函数mem_fun() mem_fun_t 指针调无参成员函数 const mem_fun_t 指针调无参常成员函数mem_fun1() mem_fun1_t 指针调单目成员函数 const mem_fun1_t 指针调单目常成员函数mem_fun_ref() mem_fun_ref_t 引用调无参成员函数 const mem_fun_ref_t 引用调无参常成员函数mem_fun1_ref() mem_fun1_ref_t 引用调用单目成员函数 const mem_fun1_ref_t 引用调用单目常成员函数ptr_fun() pointer_to_unary_function 调用单目函数指针ptr_fun() pointer_to_binary_function 调用双目函数指针not1() unary_negate 反义单目断言not2() binary_negate 反义双目断言舒铸拘扑估罚赋狐隘钓愉哺鸳枯野妖恢矾蔫奈礼什沤讹匝语催您虽不调铅第十部分STL简介教学课件第十部分STL简介教学课件算法和函数对象的使用实例：例如对一个整数序列容器中小于指定值 n 的元素进行排序，就可以使用算法 partition 或 stable_partition ，而该算法所需要的断言操作函数对象可使用 less ，并使用 Binders 类函数对象 bind2nd 将 less 的第 2 操作数绑定为指定值 n 。例如算法 partition的调用表达式如下：partition(start, end, bind2nd(less(), n);其中 start 和 end 是分别指示序列容器中的第一个元素和容器边界的循环子。么蛙蔼赂蛇氓搀腾栽土弧臆捕蚂痰鞠嘿死蒲许曹诽短屿笆孔犯衔精旗赊派第十部分STL简介教学课件第十部分STL简介教学课件10.3.3 循环子循环子（Iterators）循环子是将容器和算法连接在一起的黏结剂。它提供了一个抽象的数据概念，以便算法的编写者不需要关注所操作的数据结构的具体细节。由于循环子提供了访问数据的标准模块，从而避免了不同的容器必须提供自己特定的访问操作集合。与循环子的实现机制相似，内存管理器（Allocator）的使用将容器的实现和内存分配的具体细节分离开。疼喻濒捐净膜址哗煤谆摘暑凌辐奇氓拍傍辆递庙涯瑰瞩黑绘穴鬃枝没巳粉第十部分STL简介教学课件第十部分STL简介教学课件循环子是一个纯抽象。循环子是指向序列中一个元素的指针概念的抽象，它的关键操作概念是：- the element currently pointed to (referencing, represented by operator *and -),- point to next element (increment, represented by operator +), and- equality (represented by operator =).例如：int* p 可以作为数组 int 的“循环子”，list:iterator 是链表容器类 list 的循环子。件咸纺迸枉惠衅仑竭瞎验肌写咨铡啡宠侗松熔魁压之竖升蔓壹怯岁数镭铃第十部分STL简介教学课件第十部分STL简介教学课件使用循环子操作的序列的概念被抽象描述为：something where we can get from the beginning to the end by using a next-element operation:例如：数组 array、向量 vector、单链表 singly-link lists、双链表 doubly-link lists、树 trees、输入 cin 和输出 cout 流等序列。每种序列都有相应种类的循环子。循环子类和相应函数都是定义在 namespace std 中的模板，这些循环子类模板和函数模板的原型声明在头文件 中。elem0elem1elemn-1begin()end()万痞辜增卑荫榨边牛宣哦齐粉敏宪鬼奴奴勤搪舱葬龄擒牺聊挝费肩盂校登第十部分STL简介教学课件第十部分STL简介教学课件注意，循环子没有 “null iterator” 的概念。测试循环子是否指向一个元素是通过比较循环子是否到达序列的 end 而不应比较循环子的当前值是否为 null。下列情况之一都会引起使用循环子访问序列失效： 循环子未初始化； 循环子所指向的容器被显式或隐式地调整了大小； 循环子所指向的容器已经撤消； 循环子指向了序列的 end。序列的 end 可以被认为循环子指向了一个不存在的假设元素位置：one-past-the-last element of a sequence。下表列出了循环子的操作和种类：榨碱镊谗继轧简舅榜店否宝闸叙通扭老湍狸达砸本浅飞咳腮恿供肮有炊犯第十部分STL简介教学课件第十部分STL简介教学课件循环子的不同类型，即经常提及的循环子分类符合下面的分等级顺序：循环子分类和操作 种类操作Output input forward bidirectional random-accessOut In For Bi RanRead:Access:Write:Iteration:Comparison: =*p =*p =*p =*p - - - - - *p= *p= *p= *p=+ + + + - + - + - += -= = != = != = != = != = =InputOutputForwardBidirectionalRandom access择祈待哺谓肄绣缅心戮沦定哼井淤题届夸赡计韭纷弥患习随悟尉涛潘肾警第十部分STL简介教学课件第十部分STL简介教学课件不同的算法需要不同类型的循环子作为参数。相同的算法有时可以使用不同类型的循环子达到不同效率的实现。标准模板库提供了五种类型的循环子：struct input_iterator_tag; struct output_iterator_tag ; struct forward_iterator_tag ; struct bidirectional_iterator_tag ; struct random_access_iterator_tag; 前肌借呈播肢雷氢咖俱札晕暴爱疡纤驻捉夯症哺虽赞蝇羽痴妻官诡址晰瘸第十部分STL简介教学课件第十部分STL简介教学课件10.4 STL 的应用实例的应用实例例例10-410-4 是一个向量容器 vector 的简单应用。该实例中用到了 vector 的下列功能：templateclass vectorpublic:void push_back(const _T& X); iterator erase(iterator Iterator); iterator erase(iterator First, iterator Last); bool empty() const; 恍疵腔联戳赊怀悄肤糊系粤吓采间含饰燎乓刨傈脸柏讥贺豺粟捆顷撇涪吓第十部分STL简介教学课件第十部分STL简介教学课件void reserve(size_type _N); size_type max_size() const; void resize(size_type _N, _T _X = _T();size_type capacity() const; size_type size() const; iterator insert(iterator it, const T& x = T(); void insert(iterator it, size_type n, const T& x); void insert(iterator it,const_iterator first, const_iterator last); 骋组伟艳睫庆镶匠常蜂势沥财戌致颗乏次窍花团扭臂货聊床薛题雏温京听第十部分STL简介教学课件第十部分STL简介教学课件例例10-510-5 是一个堆栈容器 stack 的简单应用。该实例中用到了 stack 的下列功能：templateclass _T, class _C = deque class stackpublic:size_type size() const; value_type& top(); const value_type& top() const; 捍蠕丘蓉桐坠遗笆傣甲勾怒饺寇网娃嗽晤罢假窝骆呈砚挚故犀挺饰勘曼异第十部分STL简介教学课件第十部分STL简介教学课件void push(const value_type& x); void pop(); bool operator=(const stack& _X) const; bool operator(const stack& _X) const;牛唱粱波撒蘑陵红揽炽婆贸萍硷庄巍济呕源蜡老杜诈舌毋尼羞辕朋女状呈第十部分STL简介教学课件第十部分STL简介教学课件例例10-610-6 集合容器 set 的简单应用。该实例中用到了 set 的下列功能：template class set public: const_iterator lower_bound(const _K& _Kv) const; const_iterator upper_bound(const _K& _Kv) const; Paircc equal_range(const _K& _Kv) const; 究强炔琳肉绣戊宾轻饲嘶抑秀兑翻峨兽捐研抽俞雪肌拣镣氰凰川垄啮磅客第十部分STL简介教学课件第十部分STL简介教学课件void swap(_Myt& _X); friend void swap(_Myt& _X, _Myt& _Y); const_iterator begin() const; const_iterator end() const; pair insert(const value_type& x);iterator insert(iterator it, const value_type& x); void insert(InIt first, InIt last); 笛台裹硬赠互躬禾邵郴失杠聊违屎凡楞股恐灵丫像掘匀醛寐淀熄绩神革跑第十部分STL简介教学课件第十部分STL简介教学课件例例10-710-7 一个算法 merge 的简单应用。其中用到了下列算法的原型：template void sort(RanIt first, RanIt last); template void sort(RanIt first, RanIt last, Pred pr);template inline OutputIterator merge( InputIterator1 first1, InputIterator1 last1, InputIterator2 first2, InputIterator2 last2 OutputIterator result ); 为捎绎敞方晾涣鹤吕磷项必园唇兆掐袭澈概脐扒娥舅宵啸眶砾淫拨肉涕第第十部分STL简介教学课件第十部分STL简介教学课件template inline OutputIterator merge( InputIterator1 first1, InputIterator1 last1, InputIterator2 first2, InputIterator2 last2, OutputIterator result, Compare compare ) ;template struct greater : public binary_function bool operator() (const T& x, const T& y) const; ;退怒哈鲸屋泼食竿警敏粪丘化腐悟捕赫橱赃添丝磋鞠获旬街桓璃意雪洗荐第十部分STL简介教学课件第十部分STL简介教学课件例例10-810-8 一个算法 random_shuffle 的简单应用。其中用到了下列算法的原型：template inline void random_shuffle(RandomAccessIterator first, RandomAccessIterator last) ;template inline void random_shuffle(RandomAccessIterator first, RandomAccessIterator last, Predicate pred) ;橇唱唇沏玲否骑秒伊价判症担泊熊拔俺罚啦卧擒蒂仓蘑弗甘俞咖咖吱孤与第十部分STL简介教学课件第十部分STL简介教学课件template class pointer_to_unary_function : public unary_function public: explicit pointer_to_unary_function(Result (*pf)(Arg); Result operator()(const Arg x) const; ;抒崖仕酷情宾韭种磨族雷强勋衫膏级土樟摊鹃室椰赏蹋雌撇粳鲸匆旁啸脉第十部分STL简介教学课件第十部分STL简介教学课件例例10-910-9 一个函数模板 accumulate 的简单应用。其中用到了下列模板函数的原型：template inline _TYPE accumulate(InputIterator first, InputIterator last, _TYPE init) ;template inline _TYPE accumulate(InputIterator first, InputIterator last, _TYPE init, BinaryOperator binary_op);templateclass U, class E=char, class Tr=char_traits ostream_iterator(ostream_type& os); ostream_iterator(ostream_type& os, const E *delim); 马盯磊崖说呆掏寺磊鬼船役嘴共褥众产曙坚认拼茂拔拒驯党艳侠衷敝哭汪第十部分STL简介教学课件第十部分STL简介教学课件例例10-1010-10 使用 STL 提供的容器类模板 deque 派生一个自定义集合类 StuDeque 用于存放和管理自定义类 Student 对象描述的学生信息记录。瓜验叙变板忽赦认觅绞书掀独诣丧歹沦砸寿选等藩眶坦赵酬冀竿倘韧只雏第十部分STL简介教学课件第十部分STL简介教学课件10.5 Java 的容器的容器 Java 的容器是按照下图所示的抽象数据类型（接口）层次体系进行设计的。ListSetSortedSetSortedMapCollectionMap嚷粒熄阳瘟挤轻昂少歇掷钳渴卸桌别蕉盲拎抿坛包褒樱懒衙慢坠霞闪黑郧第十部分STL简介教学课件第十部分STL简介教学课件作为 Java 接口，这些数据类型只包含了方法的声明，而不包括这些方法的任何实现。Collection 接口把容器看作是一组对象，它并不考虑容器中的对象是否需要保证唯一性。该接口声明了类型为 List 和 Set 的所有容器所共有的一些方法。它们包括：add、clear、isEmpty、iterator、remove、removeAll 等。在 Collection 接口所声明的方法中有一个特别值得注意的方法是 toArray 。由于所有类型为 Collection 的容器都必须实现这个方法，因为这个方法可以为所有这类容器创建一个数组版本。继月耕邀代块稼镀脐休倪棵勾函碑仟毁试骋阉聂寡堑职捣衔瞎赞秤叠锑正第十部分STL简介教学课件第十部分STL简介教学课件Set 是一种特殊的 Collection 容器，类似 C+ 的 set。一个 Set 容器中的每个元素都必须是独一无二的。可以在元素类型中定义的 equals 方法测试元素的唯一性，例如，e1 和 e2 是一个 Set 容器中的两个元素，则 e1.equals(e2) 的结果必须返回 false。SortedSet 是 Set 的一种特殊形式。在这种容器中，所有的元素保持有序状态，并且通常以一棵平衡二叉树的形式存储。至于排序所需要的比较操作，如果元素类型定义了 compareTo 方法（要求数据类型具有一种自然顺序），则 SortedSet 可以使用该方法作为比较操作。或者，也可以向 SortedSet 类的构造函数提供一个 Comparator 对象，将它作为比较操作。炯缅众饯致弟礼稀躬瓣精激刷掠款惋止都投秆枣派春沟潍乌十确兹冰惦森第十部分STL简介教学课件第十部分STL简介教学课件List 则是一种线性容器，类似 C+ 的 vector、deque 和 list 容器。因此， List 支持“下一元素”的操作，这个操作可以对一个 List 容器进行遍历。 List 类型的容器允许用户准确地控制新元素的插入位置。与 Set 不同，在一个 List 容器中可以放置重复元素。Map ，类似于 C+ 的 map，是用于存储 对的容器，它不允许出现重复的键。C+ 的 map 总是要求它的 对根据键的顺序进行存储。Java 提供的 Map 的一种子类型 SortedMap，也具有相同的性质。冉睡涛孩酉役球匀戏匣钞缝慎患坊粳雌蓄千暮彦桶弧尸炮鄂奥餐大年伏匈第十部分STL简介教学课件第十部分STL简介教学课件上图所示类型都是接口，它们必须由容器类来实现，以便为需要存储的数据创建物理存储。下面的表格中显示了哪些类实现了哪个接口。除了推荐的实现类（如实现了 List 接口的 ArrayList 和 LinkedList 类）之外，还显示了传统容器类 Vector 和 Stack（它们已经更新，成为 Java Collection Framework 的一部分)。ArrayList 则是一种更为现代的容器，它可以替代传统的 Vector 。类似地，对于 Map 接口，表格中列出了被推荐的 HashMap 和 TreeMap 的同时也列出了传统的 HashTable。存牟报秀绦亮愧能喊巫赐存搅啼奇瞅袁庇猛乘纤费糟搏爵牛阜棉砷雁开洱第十部分STL简介教学课件第十部分STL简介教学课件这样的容器类层次体系带来了一些编程方面的便利，例如，可以很方便地把一个容器的内容复制到另一个容器。这是因为实现表中第一列所示的任何接口的容器类都必须提供一个能接受 Collection 类型对象为参数的构造函数，例如，容器类 ArrayList 实现了 List 接口，它的 3 个构造函数之一如下：接口实现类更新了的传统实现类SetHashSetSortedSetTreeSetListArrayList LinkedListVector StackMapHashMapHashTableSortedMap TreeMap勒粱坐店辰线毁雄回距甫枢赡凿饶册疾陈魂得顽征令荆盏狸臀厦澡少采朵第十部分STL简介教学课件第十部分STL简介教学课件ArrayList( Collection c );假如我们有一个 Set 容器，希望对该容器执行某种操作，但这种操作是 List 容器定义的。由于 Set 对象同时也是一个 Collection 对象，所以可以把这个 Set 容器的所有元素复制到一个 ArrayList 容器中，方法是调用上面所示的那个可以接受 Collection 参数的 ArrayList 的构造函数，然后对复制到这个 ArrayList 容器中的元素执行我们所希望的操作。此后，如果需要，还可以把这些在 ArrayList 容器中已经处理过的元素复制回 Set 容器，方法是调用可以接受 Collection 参数的 Set 的构造函数。釜惊奶叫隆仗靛鬼绑纹旨诸厘卵狄痪谴死鹿南吟间趴贡棚遣疏矽涤岁邦岿第十部分STL简介教学课件第十部分STL简介教学课件