C++从0到1 - 黑马程序员 课程学习笔记
课程链接:77 常用遍历算法-for_each_哔哩哔哩_bilibili
概 述:
- 算法主要是由头文件<algorithm><functional><numeric>组成。
- <algorithm>是所有STL头文件中最大的一个,范围涉及到比较、 交换、查找、遍历操作、复制、修改等等
- <numeric>体积很小,只包括几个在序列上面进行简单数学运算的模板函数
- <functional>定义了一些模板类,用以声明函数对象
1. 常用遍历算法
1.1 for_each
函数原型:
for_each(iterator beg, iterator end, _func);
- beg 开始迭代器
- end 结束迭代器
- _func 函数或者函数对象
// 普通函数
void myPrint(int val)
{
cout << val << endl;
}
// 仿函数
class MyPrint02
{
public:
void operator()(int val)
{
cout << val << endl;
}
}
vector<int> v;
// 普通函数 使用 函数名
for_each(v,begin(),v.end(),myPrint);
// 仿函数 使用 函数对象
for_each(v,begin(),v.end(),MyPrint02())
1.2 transform
功能描述:搬运容器到另一个容器中
函数原型:
transform(iterator beg1, iterator end1, iterator beg2, _func);
- beg1 源容器开始迭代器
- end1 源容器结束迭代器
- beg2 目标容器开始迭代器
- _func 函数或者函数对象
vector<int> v;
vector<int> vTarget;
// 提前给目标容器开辟空间
vTarget.resize(v.size());
transform(v.begin(),v.end(),vTarget.begin());
搬运的目标容器必须要提前开辟空间,否则无法正常搬运
2. 常用查找算法
2.1 find
功能描述:查找指定元素,找到返回指定元素的迭代器,找不到返回结束迭代器end()
函数原型:
find(iterator beg, iterator end, value);
- 按值查找元素,找到返回指定位置迭代器,找不到返回结束迭代器位置
- beg 开始迭代器
- end 结束迭代器
- value 查找的元素
2.2 find_if
功能描述:按条件查找元素
函数原型:
find_if(iterator beg, iterator end, _Pred);
- 按值查找元素,找到返回指定位置迭代器,找不到返回结束迭代器位置
- beg 开始迭代器
- end 结束迭代器
- _Pred 函数或者谓词(返回bool类型的仿函数)
2.3 adjacent_find
功能描述:查找相邻重复元素
函数原型:
adjacent_find(iterator beg, iterator end);
- 查找相邻重复元素,返回相邻元素的第一个位置的迭代器
- beg 开始迭代器
- end 结束迭代器
2.4 binary_search
功能描述:查找指定元素是否存在
函数原型:
bool binary_search(iterator beg, iterator end, value);
- 查找指定的元素,查到 返回true 否则false
- 注意: 在无序序列中不可用
- beg 开始迭代器
- end 结束迭代器
- value 查找的元素
二分查找法查找效率很高,值得注意的是查找的容器中元素必须是有序序列
2.5 count
功能描述:统计元素个数
函数原型:
count(iterator beg, iterator end, value);
- 统计元素出现次数
- beg 开始迭代器
- end 结束迭代器
- value 统计的元素
2.6 count_if
功能描述:按条件统计元素个数
函数原型:
count_if(iterator beg, iterator end, _Pred);
- 按条件统计元素出现次数
- beg 开始迭代器
- end 结束迭代器
- _Pred 谓词
3. 常用排序算法
- sort 对容器内元素进行排序
- random_shuffle 洗牌 指定范围内的元素随机调整次序
- merge 容器元素合并,并存储到另一容器中
- reverse 反转指定范围的元素
3.1 sort
功能描述:对容器内元素进行排序
函数原型:
sort(iterator beg, iterator end, _Pred);
- 按值查找元素,找到返回指定位置迭代器,找不到返回结束迭代器位置
- beg 开始迭代器
- end 结束迭代器
- _Pred 谓词
3.2 random_shuffle
功能描述:洗牌 指定范围内的元素随机调整次序
函数原型:
random_shuffle(iterator beg, iterator end);
- 指定范围内的元素随机调整次序
- beg 开始迭代器
- end 结束迭代器
random_shuffle洗牌算法比较实用,使用时记得加随机数种子
3.3 merge
功能描述:两个容器元素合并,并存储到另一容器中
函数原型:
merge(iterator beg1, iterator end1, iterator beg2, iterator end2, iterator dest);
- 容器元素合并,并存储到另一容器中
- 注意: 两个容器必须是有序的
- beg1 容器1开始迭代器
- end1 容器1结束迭代器
- beg2 容器2开始迭代器
- end2 容器2结束迭代器
- dest 目标容器开始迭代器
3.4 reverse
功能描述:将容器内元素进行反转
函数原型:
reverse(iterator beg, iterator end);
// 反转指定范围的元素
// beg 开始迭代器
// end 结束迭代器
4. 常用拷贝和替换算法
4.1 copy
功能描述:容器内指定范围的元素拷贝到另一容器中
函数原型:
- copy(iterator beg, iterator end, iterator dest);
- 按值查找元素,找到返回指定位置迭代器,找不到返回结束迭代器位置
- beg 开始迭代器
- end 结束迭代器
- dest 目标起始迭代器
利用copy算法在拷贝时,目标容器记得提前开辟空间
4.2 replace
功能描述:将容器内指定范围的旧元素修改为新元素
函数原型:
replace(iterator beg, iterator end, oldvalue, newvalue);
- 将区间内旧元素 替换成 新元素
- beg 开始迭代器
- end 结束迭代器
- oldvalue 旧元素
- newvalue 新元素
4.3 replace_if
功能描述:将区间内满足条件的元素,替换成指定元素
函数原型:
replace_if(iterator beg, iterator end, _pred, newvalue);
- 将区间内旧元素 替换成 新元素
- beg 开始迭代器
- end 结束迭代器
- _pred 谓词
- newvalue 替换的新元素
4.4 swap
功能描述:互换两个容器的元素
函数原型:
swap(container c1, container c2);
- 互换两个容器的元素
- c1容器1
- c2容器2
swap交换容器时,注意交换的容器要同种类型
5. 常用算术生成算法
算术生成算法属于小型算法,使用时包含的头文件为 #include <numeric>
5.1 accumulate
功能描述:计算区间内 容器元素累计总和
函数原型:
accumulate(iterator beg, iterator end, value);
- 计算容器元素累计总和
- beg 开始迭代器
- end 结束迭代器
- value 起始值
5.2 fill
功能描述:向容器中填充指定的元素
函数原型:
- fill(iterator beg, iterator end, value);
- 向容器中填充元素
- beg 开始迭代器
- end 结束迭代器
- value 填充的值
6. 常用集合算法
6.1 set_intersection
功能描述:求两个容器的交集
函数原型:
set_intersection(iterator beg1, iterator end1, iterator beg2, iterator end2, iterator dest);
- 注意:两个集合必须是有序序列
- beg1 容器1开始迭代器
- end1 容器1结束迭代器
- beg2 容器2开始迭代器
- end2 容器2结束迭代器
- dest 目标容器开始迭代器
目标容器开辟空间需要从两个容器中取小值
set_intersection返回值是交集中最后一个元素的位置
6.2 set_union
功能描述:求两个集合的并集
函数原型:
set_union(iterator beg1, iterator end1, iterator beg2, iterator end2, iterator dest);
- 注意:两个集合必须是有序序列
- beg1 容器1开始迭代器
- end1 容器1结束迭代器
- beg2 容器2开始迭代器
- end2 容器2结束迭代器
- dest 目标容器开始迭代器
目标容器开辟空间需要两个容器相加
set_intersection返回值是并集中最后一个元素的位置
6.3 set_diffrence
功能描述:求两个集合的差集
函数原型:
set_difference(iterator beg1, iterator end1, iterator beg2, iterator end2, iterator dest);
- 注意:两个集合必须是有序序列
- beg1 容器1开始迭代器
- end1 容器1结束迭代器
- beg2 容器2开始迭代器
- end2 容器2结束迭代器
- dest 目标容器开始迭代器
目标容器开辟空间需要从两个容器中取较大值
set_intersection返回值是差集中最后一个元素的位置。