STL 中级使用培训

中级使用培训STL中算法algorithm1.查找算法为判断容器中是否包含某一个值提供adjacent_find()寻找两个相邻的元素binary_search()二分查找count()统计匹配项的个数count_if()统计满足某种匹配条件的项个数equal_range()返回匹配值的游标范围find()查找匹配值，返回其游标位置find_end()查找一批数值的匹配，返回其匹配的游标首位置find_first_of()查找匹配一个条件的数据的游标位置find_if()查找满足一定条件的匹配值，返回其游标位置lower_bound()返回匹配值的区间下限的游标位置upper_bound()返回匹配值的区间上限的游标位置search()一个序列中找另一个序列的第一次出现的位置search_n()一个序列中找另一个序列的出现n次第一次出现的位置STL中算法algorithm2.排序(sorting)和通用(ordering)算法提供元素的排序策略。其中stable算法保证相等元素的原来顺序不变。inplace_merge()合并一个中前后两段分别有序的序列，merge()合并两个有序的sequencenth_element()将序列中第n个元素分区，小于它的在之前，否则在其后partial_sort()制定middle进行部分排序，比middle小的排序partial_sort_copy()制定middle进行部分排序，比middle小的排序，并复制到目标序列中partition()使得符合某个条件的元素放在前面random_shuffle()将序列中的元素顺序随机化reverse()将序列中元素反序reverse_copy()将序列中元素反序，并复制到目标容器中rotate()对序列中元素做旋转轮换rotate_copy()对序列中元素做旋转轮换，并复制到目标容器中sort()对给定区间所有元素进行排序stable_sort()对给定区间所有元素进行稳定排序stable_partition()相对稳定的使得符合某个条件的元素放在前面STL中算法algorithm3.删除和替换算法copy()复制序列到目标容器中copy_backwards()反向复制序列到目标容器中iter_swap()游标互换（就是对置两个游标）remove()从序列中删除某个游标指向的值remove_copy()从序列中删除某个游标指向的值，并复制到目标容器中remove_if()从序列中删除满足某个条件的值remove_copy_if()从序列中删除满足某个条件的值，并复制到目标容器中replace()替换序列中值replace_copy()替换序列中值，并复制到目标容器中replace_if()替换序列中满足某个条件的值replace_copy_if()替换序列中满足某个条件的值，并复制到目标容器中swap()互换两个容器中的值swap_range()互换两个容器中制定范围内的值unique()唯一化容器中的值unique_copy()唯一化容器中的值，并复制到目标容器中。STL中算法algorithm4.排列组合算法提供计算给定集合按一定顺序的所有可能的排列组合。next_permutation()计算一组数据的全排列，取其当前计算结果prev_permutation()计算一组数据的全排列，取其前一个计算结果STL中算法algorithm5.算术算法accumulate()对容器中元素累加，可以指定累加元素时初始化的处理办法partial_sum()对容器内部分元素累加inner_product()对两个容器求内积（两个序列间元素相乘后累加）adjacent_difference()求邻接差（序列中两个元素之间的差）STL中算法algorithm6.生成和异变算法fill()在容器指定范围内用某值填充fill_n()在容器某个位置用某值填充n项for_each()对容器内每个元素进行相同的处理generate()按照一定算法生成值填充容器中的项generate_n()按照一定算法生成值填充容器中的项，从某个位置填充n次transform()对容器内一定范围内数据进行变形（算法）处理STL中算法algorithm7.关系算法equal()判断是否相等includes()判断是否包含lexicographical_compare()判断哪一个容器小一些max()求最大值max_element()求容器指定范围内的最大元素值min()求最小值min_element()求容器指定范围内的最小元素值mismatch()求容器指定范围内、指定条件下不匹配的第一个值STL中算法algorithm8.集合算法set_union()并集set_intersection()交集set_difference()差集set_symmetric_difference()异或集STL中算法algorithm9.堆算法make_heap()创建一个最大堆pop_heap()首尾元素交换重置堆push_heap()尾部加入元素重置堆sort_heap()堆排序1、第一种写法：使用全局函数std::vectorintvctSrc;voiddouble_fun(int&i){i1;}std::for_each(vctSrc.begin(),vctSrc.end(),double_fun);2、第二种写法：使用类中静态函数std::vectorintvctSrc;ClassCCC{Public:Staticvoiddouble_fun(int&i){i1;}voidsome_fun(){std::for_each(vctSrc.begin(),vctSrc.end(),double_fun);}};3、第三种写法：重载操作符()，写一个算子(functor)classCCC{templateclassTclassDouble_functor{public:voidoperator()(typenameT&i){i*=2;}};voidsome_fun(){std::for_each(vctSrc.begin(),vctSrc.end(),Double_functorint());}std::vectorintvctSrc;};STL中函数对象functor（也就是算子）STL中提供了一元和二元函数的两种Functor,通过unary_function和binary_function提供了这两种不同参数数量的Functor的基本结构,在这两个类型中,分别内嵌定义一元和二元函数操作在模版推演的时候需要用到的typedef.如一元函数的定义为templateclass_A,class_Rstructunary_function{typedef_Aargument_type;typedef_Rresult_type;};//二元函数的定义为templateclass_A1,class_A2,class_Rstructbinary_function{typedef_A1first_argument_type;typedef_A2second_argument_type;typedef_Rresult_type;};STL中函数对象functor（也就是算子）1、关系算子equal_toT==（相等）not_equal_toT!=（不相等）greaterT（大于）greater_equalT=（大于等于）lessT（小于）less_equalT=（小于等于）2、计算算子plusT+（加）minusT-（减）multipliesT*（乘）dividesT/（除）modulusT%（求模）negateT-(符号取反)3、逻辑算子logical_andT&(与)logical_notT!（非）logical_orT|（或）STL中函数对象functoradapterBind1st绑定第一个参数（当容器是二元素）bind2nd绑定第二个参数（当容器是二元素）not1对于一元函数对象取反not2对于二元函数对象取反ptr_fun是指将现有的函数转换为Functor的功能.在STL中提供了这个功能的Functor,就是pointer_to_unary_function指向一元函数的函数指针对象pointer_to_binary_function指向二元函数的函数指针对象STL内存分配机制STL中引入了allocator这个东西，提供给各个组件进行统一的内存管理。stl的内存管理主要分为2级进行配置：1级配置，用于处理大块的内存分配，直接使用malloc和free来进行处理。（128bytes）2级配置，使用了一个内存池，对小量的内存分配和释放进行优化。这里主要说说STL内存池实现的方法。STL的内存池是一种比较简单的内存池实现，和apache的内存池相比就非常简单了，总体思路就是一个：打包。对于小容量的内存分配和释放，尽量采用一次分配，在程序退出时自动释放。当然这里有一个极端的理论情况就是，某个程序一口气进行了非常多次的小量内存（申请单元的大小128字节）的申请，导致这个内存池占用的内存越来越大，而等到对这些单元进行回收时，内存池的大小确不会改变的情况，呵呵，似乎有点杞人忧天。实现上也是非常精妙的，使用了一个链表数组，对于16个链表，每个链表上都挂着若干个已分配好的连续小块内存单元。使用的时候直接从链表里拿走，归还的时候会把这个内存块重新插入到链表的头部。只有当该链表的空闲内存块不够用的时候，才会进行一次内存分配。一方面减少了系统调用的次数，提高了性能，又可以有效的避免系统的内存碎片。(链表中每个内存对象大小是8bytes倍数)内存池，实际上就是由用户程序取代操作系统，自己管理内存空间，操作系统自己的内存管理机制就可以看成是一个最大的内存池，熟悉操作系统的人不会觉得有多么神奇。STL内存分配templateclassmalloc_allocator{public:typedefTvalue_type;typedefvalue_type*pointer;typedefconstvalue_type*const_pointer;typedefvalue_type&reference;typedefconstvalue_type&const_reference;typedefstd::size_tsize_type;typedefstd::ptrdiff_tdifference_type;public:pointeraddress(referencex)const；const_pointeraddress(const_referencex)const；pointerallocate(size_typen,const_pointer=0)；voiddeallocate(pointerp,size_type）；};1、聚合使用std::vectorstd::vectorintvctAggregate;std::vectorstd::mapint,intvctAggregate;std::vectorstd::mapint,std::vectorintvctAggregate;2、组合使用std::mapint,classXXXmapXXX;classXXX{public:std::listint::iteratorm_iter;};std::listintlistXXX;将一个int插入到listXXX同时，以int值为key，listXXX插入元素所在位置的游标赋予classＸＸＸ中的ｍ_iter属性，将key，和classXXX对象插入mapXXX。这样查找的时候可以用key（int）迅速找到到对应的list的对象的iterator，也可以利用list