好贷网好贷款

STL学习笔记之 算法(构造堆等)

发布时间:2016-12-4 9:55:00 编辑:www.fx114.net 分享查询网我要评论
本篇文章主要介绍了"STL学习笔记之 算法(构造堆等)",主要涉及到STL学习笔记之 算法(构造堆等)方面的内容,对于STL学习笔记之 算法(构造堆等)感兴趣的同学可以参考一下。

算法大致分为如下四类:         1、非可变序列算法:指不直接修改其所操作的数据元素的值或顺序的算法;         2、可变序列算法:指可以修改它们所操作的数据元素的值或顺序的算法;         3、排序算法:包括对序列进行排序和合并的算法、搜索算法以及有序序列上的集合操作;         4、数值算法:对容器的数据元素进行数值计算。 for_each()算法非常灵活,它可以以不同的方式存取、处理、修改每一个数据元素。 void print (int elem){    cout<< elem << ' ';} for_each (coll.begin(), coll.end(),   print);                //operation 非变异算法 序号 功能 函数名称 说       明 1 循环 for_each() 遍历容器元素,对每个元素都执行某操作 2 查询 find() 找出等于某个值的第一次出现的那个元素的位置 find_if() 找出符合某谓词的第一个元素的位置 find_first_of() 找出等于“某数个值之一”的第一次出现的元素 adjacent_find() 找出第一次相邻值相等的元素 find_end() 找出一子序列的最后一次出现的位置 search() 找出某一子区间第一次出现的位置 search_n 找出某特定值连续n次出现的位置 3 计数 count() 统计某个值出现的次数 count_if() 统计与某谓词(表达式)匹配的元素个数 4 比较 equal() 判断是否相等,即两个序列中的对应元素都相同时为真 mismatch() 找出两个序列第一个相异的元素 min_element() 返回最小值元素的位置 max_element() 返回最大值元素的位置  ilocation=search(v1.begin(),v1.end(),v2.begin(),v2.end());     表5-2  变异算法的划分 序号 功能 函数名称 说       明 1 复制 copy() 从序列的第一个元素起复制到另一序列指定的开始处区间内 copy_backward() 从序列的最后一个元素起复制某段区间 2 交换 swap() 交换两个元素 swap_ranges() 交换指定范围的元素 iter_swap() 交换由迭代器所指的两个元素 3 变换 transform() 变动(并复制)元素,将两个区间元素合并 4 替换 replace() 用一个给定值替换一些一些元素的值 replace_if() 替换满足谓词的一些元素 replace_copy() 复制序列时用一给定值替换元素 replace_copy_if() 复制序列时替换满足谓词的元素 5 填充 fill() 用一给定值取代所有元素 fill_n() 用一给定值取代前n个元素 6 生成 generate() 用一操作的结果取代所有元素 generate_n() 用一操作的结果取代前n个元素  排序算法 表5-3  STL中常用的排序和搜索算法 序号 功能 函数名称 说       明 1 排  序 Sort 以很好的平均效率排序 stable_sort 排序,并维持相同元素的原有顺序 partial_sort 将序列的前一部分排好序 partial_sort_copy 复制的同时将序列的前一部分排好序 2 第n个元素 nth_element 将第n各元素放到它的正确位置 3 二分检索   lower_bound 找到大于等于某值的第一次出现 upper_bound 找到大于某值的第一次出现 equal_range 找到(在不破坏顺序的前提下)可插入给定值的最大范围 binary_search 在有序序列中确定给定元素是否存在 4 归   并 Merge 归并两个有序序列 inplace_merge 归并两个接续的有序序列 5 序列结构上的集合操作   Includes 一序列为另一序列的子序列时为真 set_union 构造两个集合的有序并集 set_intersection 构造两个集合的有序交集 set_difference 构造两个集合的有序差集 set_symmetric_difference 构造两个集合的有序对称差集(并-交) 6 堆操作 make_heap 从序列构造堆/最大堆 pop_heap 从堆中弹出元素 push_heap 向堆中加入元素 sort_heap 给堆排序,堆被破坏 7 最大和最小 min 两个值中较小的 max 两个值中较大的 min_element 序列中的最小元素 max_element 序列中的最大元素 8 词典比较 lexicographical_compare 两个序列按字典序的第一个在前 9 排列生成器 next_permutation 按字典序的下一个排列 prev_permutation 按字典序的前一个排列 10 数值算法 accumulate 累积和 inner_product 内积 partial_sum 局部求和 adjacent_difference 临接差   堆操作:  vector<int> v; 例如 5 6 4 8 2 3 7 1 9  make_heap(v.begin(),v.end()); //创建堆,即将一个区间转换成一个heap   9 8 7 6 2 3 4 1 5  一般生成的是大根堆如果要生成最小堆,需要制定函数 int Little(int a, int b){ return a>b; }  make_heap(v.begin(), v.end(), Little); make_heap(v.begin(), v.end(), greater<int>()); 更为简单…… v.push_back(20);//向向量v尾部插入20,但尚未压入堆 9 8 7 6 2 3 4 1 5 20 push_heap(v.begin(),v.end());  //元素入堆(默认插入最后一个元素) 20 9 7 6 8 3 4 1 5  pop_heap(v.begin(),v.end());   //元素出堆(从heap中移除一个元素) 9 8 7 6 2 3 4 1 5 20 v.pop_back() ;  //把出堆元素物理删除 9 8 7 6 2 3 4 1 5  sort_heap(v.begin(),v.end());  //堆排序,输出排序的结果 1 2 3 4 5 6 7 8 9 不可以对list调用这些算法,因为list不支持随即存取迭代器。不过list提供了一个成员函数sort(),可以用来对自身元素进行排序。 数值算法 accumulate算法:   计算序列中所有元素的和。 inner_product:    对两个序列做内积(对应元素相乘,再求和),并将内积加到一个输入的初始值上。 partial_sum:    对序列中部分元素的值进行累加,并将结果保存在另一个序列中。 OutputIterator  partial_sum (InputIteratorsourceBeg,  InputIteratorsourceEed,   OutputIteratordestBeg); 形式一是计算:a1,  a1  + a2,  a1  +  a2  +  a3,  …; adjacent_difference:   计算序列中相邻元素的差,并将结果保存在另一个序列中。

上一篇:运用android的Matrix类来旋转图片
下一篇:makefile的选项CFLAGS、CPPFLAGS、LDFLAGS和LIBS的区别

相关文章

相关评论