C---STL介绍.ppt

Click to edit Master title style,Click to edit Master text styles,Second level,Third level,Fourth level,Fifth level,*,*,C+Standard Template Library Introduction,1,STL,简介,STL,（,Standard Template Library,）是,C+,标准程序库的核心,STL,是泛型（,generic,）程序库，由一些可适应不同需求的集合类（,collection class,），以及在这些数据集合上操作的算法（,algorithm,）构成,STL,内的所有组件都由模板（,template,）构成，其元素可以是任意类型,STL,主要包括六大组件,容器,算法,迭代器,仿函数,配接器,内存配置器,2,组件关系,STL,基础组件关系,容器（,Container,）管理某类对象的集合,迭代器（,Iterator,）在对象集合上进行遍历,算法（,Algorithm,）处理集合内的元素,容器提供迭代器，算法使用迭代器，通过迭代器操作容器,里的元素。迭代器使得容器和算法相互独立。,容器,Container,算法,Algorithm,迭代器,Iterator,3,容器的概念,容器用来存储数据,map,set,list,deque,vector,4,容器的分类,序列式容器（,Sequence containers）,每个元素都有固定位置取决于插入时机和地点，和元素值无关。,vector、deque、list,关联式容器（,Associated containers）,元素没有固定位置，每个元素位置取决于容器自己特定,的排序规则，与键值有关，与插入顺序无关。,set、multiset、map、multimap,其它容器,H,ash_set,has_map,bitset,，,stack,queue,valarray,等等,5,序列容器,Vector,动态数组，支持随机存取，动态插入、删除。随意位置插入删除元素效率低，尾部插入删除效率高。,List,双向链表。不支持随机存取，任意位置插入和删除元素效率高。,Deque,双端队列，类似,vector,。但是支持高效的在首部插入和删除元素。,6,关联容器,Set(multiset),底层实现通常基于平衡二叉树,不支持直接存取元素,通过迭代器进行元素间接存取,Multiset,与,set,用法基本一致，但允许出现相同值的元素,Map(multimap),Map,是一种特殊的,set,，元素都是,pair,取用,+,将迭代器前进至下一元素,=,和,!=,判断两个迭代器是否指向同一位置,=,为迭代器赋值（将所指元素的位置赋值过去）,9,迭代器,迭代器（,iterator,）,所有容器都提供获得迭代器的函数,操作,效果,begin(),返回一个迭代器，指向第一个元素,end(),返回一个迭代器，指向最后一个元素之后,半开区间,beg,end),的好处：,1.,为遍历元素时循环的结束时机提供了简单的判断依据（只要未到达,end(),，循环就可以继续）,2.,不必对空区间采取特殊处理（空区间的,begin(),就等于,end(),）,begin(),end(),+,pos,10,迭代器,类别,说明,输入,从容器中读取元素。输入迭代器只能一次读入一个元素向前移动，输入迭代器只支持一遍算法，同一个输入迭代器不能两遍遍历一个序列,输出,向容器中写入元素。输出迭代器只能一次一个元素向前移动。输出迭代器只支持一遍算法，统一输出迭代器不能两次遍历一个序列,正向,组合输入迭代器和输出迭代器的功能，并保留在容器中的位置,双向,组合正向迭代器和逆向迭代器的功能，支持多遍算法,随机,组合双向迭代器的功能与直接访问容器中任何元素的功能，即可向前向后跳过任意个元素,容器,支持的迭代器类别,vector,随机访问,deque,随机访问,list,双向,set,双向,multiset,双向,map,双向,multimap,双向,stack,不支持,queue,不支持,11,STL,算法,STL,提供了一些标准算法来处理容器内的元素,搜寻、排序、拷贝、数值运算等等,STL,的算法是与容器相互独立,明确划分数据和操作,泛型函数式编程模式,算法通过迭代器作用于容器中的元素,12,STL,算法,区间（,range,）,所有算法都用来处理一个或多个区间内的元素。,区间可以但不一定涵盖容器内所有元素,为了操作元素的某个子集必须将区间的首尾（,iterator,）当作两个参数传递给算法,调用者必须确保区间有效性,从起点出发，逐一前进，能够到达终点。,区间首尾两个迭代器必须属于同一容器，且前后放置正确,无效区间可能会引起无限循环或者内存非法访问,所有算法处理的都是半开区间,begin,end),13,STL,算法,STL,算法分类,非变动性算法（,nonmodifying,algorithms,）,变动性算法（,modifying algorithms,）,移除性算法（,removing algorithms,）,变序性算法（,mutating algorithms,）,排序性算法（,sorting algorithms,）,已序区间算法（,sorted range algorithms,）,数值算法（,numeric algorithms,）,14,STL,算法,非变动性算法,既不改变元素次序也不改变元素值,名称,作用,count(),返回元素个数,count_if,(),返回满足某一条件的元素个数,min_element,(),返回最小元素（以迭代器表示）,max_element,(),返回最大元素（以迭代器表示）,find(),搜寻等于某值的第一个元素,find_if,(),搜寻满足某个准则的第一个元素,search_n,(),搜寻具有某种特性的第一段“,n,个连续元素”,search(),搜寻某个区间第一次出现的位置,15,STL,算法,变动性算法,直接改变元素值或者在复制到另一区间的过程中改变元素值,名称,作用,copy(),从第一个元素开始赋值某段区间,copy_backward,(),从最后一个元素开始赋值某段区间,transform(),变动（并复制）元素，将两个区间的元素合并,merge(),合并两个区间,swap_ranges,(),交换两个区间的元素,fill(),以给定值替换每个元素,fill_n,(),以给定值替换,n,个元素,generate(),以某想操作的结果替换每个元素,16,STL,算法,移除性算法,移除某区间内的元素或者在复制过程中移除元素值,名称,作用,remove(),将等于某个特定值的元素全部移除,remove_if,(),将满足某准则的元素全部移除,remove_copy,(),将不等于某特定值的元素全部复制到其他地方,remove_copy_if,(),将不满足某准则的元素全部复制到其他地方,unique(),移除相邻的重复元素,unique_copy,(),移除相邻的重复元素，并复制到其他地方,17,STL,算法,变序性算法,通过元素的赋值和交换改变元素顺序,名称,作用,reverse(),将元素的次序逆转,reverse_copy,(),复制的同时逆转元素次序,rotate(),旋转元素次序,rotate_copy,(),复制的同时旋转元素次序,random_shufle,(),将元素次序随机打乱,partion,(),改变元素次序使“符合某准则”的元素移到前面,stable_partion,(),与,partion,类似，但保持符合准则与不符合准则元素的相对位置,18,STL,算法,排序算法,需要动用随机存取迭代器,名称,作用,sort(),对所有元素排序,stable_sort,(),对所有元素排序，并保持相等元素间的相对次序,partial_sort,(),排序，知道前,n,个元素就位,nth_element,(),根据第,n,个位置排序,make_heap,(),将区间转换为,heap,push_heap,(),将一个元素加入,heap,pop_heap,(),从,heap,中移除一个元素,sort_heap,(),对,heap,进行排序（排序后不再是,heap,）,19,STL,算法,已序区间算法,所作用的区间以按某种准则排序,名称,作用,binary_serach,(),判断区间内是否包含某个元素,includes(),判断区间内的每个元素是否都包含在另一个区间中,lower_bound,(),搜寻第一个“小于等于给定值”的元素,upper_bound,(),搜寻最后一个,“,大于等于给定值”的元素,equal_range,(),返回“等于给定值,”,的元素构成的区间,merge(),将两个区间的元素合并,set_union,(),求两个区间的并集,set_intersection,(),求两个区间的交集,set_difference,(),求两个区间的差集,20,STL,算法,数值算法,以不同的方式组合数值元素,名称,作用,accumulate(),组合所有元素（求和，求积，,）,inner_product,(),组合两区间内的所有元素的内积,adjacent_difference,(),将每个元素和其前一元素组合,partial_sum,(),将每个元素和其先前所有元素组合,21,参考资料,一个,Joke,某同学拿着写了,25,页的关于,USB,技术的论文上去毕业答辩，老师开口就问：“请你用一句话介绍一下,USB,技术”，此同学立即怒曰：“一句话？一句话可以说清楚我写,25,页干嘛？一句话可以说清楚我站在这里干嘛？”整个答辩场集体沉默了,2,分钟,关于,STL,的参考资料非常多，推荐参考下面的三本书。,编写代码时参考,The C+Standard Library,，包含主要容器和算法的详细介绍和使用例子。,熟悉之后可以看看,Effetive,STL,更有效率地使用,STL,。,如果对内部实现感兴趣，可以看看,STL,源码剖析,。,几本书在服务器里可以找到,10.141.180.54publicgjybook,22,