|
|
前言上一章节主要是详细介绍了C++STL迭代器，并且简单模拟了一下list中的容器，不清楚的可以回顾一下哦。本章节主要针对于C++算法做个详细介绍。STL中算法大致分为四类：
- 非可变序列算法：不修改容器内容的算法。
- 可变序列算法：修改容器内容的算法。
- 排序算法：排序合并搜索等内容的算法
- 数值算法：对容器内容进行数值计算。
C++STL中70+的算法，以下对稍微常用的算法进行细致分类并标明功能。
查找算法查找算法就是判断容器中是否包含某个值，主要的查找算法主要是有以下13个：
- adjacent_find : 查重复数，返回首个元素iter
- bianry_search: 二分查找
- count: 区间统计
- count_if: 范围查找统计个数
equal: 比较
- equal_range :区间元素比较
- find:区间查找元素
- find_if : 条件查找
- upper_bound:查找最后一个大于等于val的位置
- lower_bound: 查找第一个大于等于val的位置
- search:子序列查找位置
- search_n:子序列查找出现次数
部分函数的测试代码如下:
排序和通用算法排序和通用算法就是用来给容器排序，主要的排序算法主要是有以下14个：
- merge: 归并排序，存于新容器
- inpace_merge: 归并排序，覆盖原区间
- sort: 排序，更改原容器顺序
- stable_sort: 排序，保存原容器数据顺序
nth_element: 关键字排序
- partition:范围排序
- partial_sort:范围排序
- partial_sort_copy:范围排序外加复制操作
- stable_partition: 范围排序，保存原容器顺序
- random_shuffle: 随机排序
- reverse:逆序原容器
- reverse_copy: 逆序容器保存到新容器
- rotate:移动元素到容器末尾
- rotate_copy:移动元素到新容器
部分函数的测试代码如下:
对于排序，值得一说的是list是不能采用通用排序算法sort，只能使用内置的sort函数哦。
删除和替换算法删除和替换算法一般都会修改容器的存储现状，一般处理删除和替换的算法主要有以下的15种：
- copy: 拷贝函数
- copy_backward: 逆序拷贝
- iter_swap: 交换
- remove: 删除
remove_copy: 删除元素复制到新容器
- remove_if:条件删除
- remove_copy_if:条件删除拷贝到新容器
- replace:替换
- replace_copy: 替换，结果放到新容器
- replace_if: 条件替换
- replace_copy_if:条件替换，结果另存
- swap: 交换
- swap_range:区间交换
- unique:去重
unique_copy:去重，结果另存
部分函数的测试代码如下:
排列组合算法提供计算给定集合按一定顺序的所有可能排列组合 ，主要有以下两个:
next_permutation:下一个排序序列的组合
prev_permutation:上一个排序序列的组合
有意思的是这里所说的上一个和下一次是什么意思？所谓“下一个”和“上一个”，举了一个简单的例子：对序列 {a, b, c}，每一个元素都比后面的小，按照字典序列，固定a之后，a比bc都小，c比b大，它的下一个序列即为{a, c, b}，而{a, c, b}的上一个序列即为{a, b, c}，同理可以推出所有的六个序列为：{a, b, c}、{a, c, b}、{b, a, c}、{b, c, a}、{c, a, b}、{c, b, a}，其中{a, b, c}没有上一个元素，{c, b, a}没有下一个元素。接下来用代码简单测试下，如下测试代码:
算术算法算术运算算法主要用来做容器的算术运算，使用的时候加上numeric头文件，主要有以下4个：
accumulate:区间求和
partial_sum:相邻元素的和
inner_product:序列内积运算
adjacent_difference:相邻元素的差
部分函数测试代码：
生成和异变算法生成和一遍算法总共有以下6个下，相对于来说for_each用的相对于来说更多一些:
for_each:迭代访问
fill:填充方式初始容器
fill_n:指定长度填充容器
generate_n:填充前n个位置
transform:一元转换和二元转换
关系算法关系算法类似与条件表达式一样的作用，主要用来判断容器中元素是否相等等运算，主要有以下8个：
equal:两容器元素是否都相同
includes:是否是包含关系
lexicographical_compare:比较两个序列
max:求最大值
max_element:返回最大值的iterator
min:求最小值
min_element:求最小值的iterator
mismatch:找到第一个不同的位置
集合算法集合算法主要是集合上的一些运算，例如集合加法：并集，集合的减法：差集，还有交集。主要有以下4个：
set_union:差集
set_intersection:并集
set_difference:保存第一个中有第二个没有的元素
set_symmetric_difference:对称差集
部分函数测试代码如下:
堆算法堆算法，就是把容器当做堆去操作，主要算法函数只有以下4个：
make_heap:生成一个堆
pop_heap:出堆
push_heap:入堆
sort_heap:堆排序
测试代码如下:
尾言本章节到此结束，作业:使用一些算法，分析上述算法的运行结果。
如有侵权，请联系 support@oschina.cn 删除。
|
免责声明：
1. 本站所有资源来自网络搜集或用户上传，仅作为参考不担保其准确性！
2. 本站内容仅供学习和交流使用，版权归原作者所有！© 查看更多
3. 如有内容侵害到您，请联系我们尽快删除，邮箱：kf@codeae.com
|
编程语言
发布于：2021-08-06 11:31
|
阅读数：339
|
评论：0
QQ好友和群
QQ空间
