【C++从0到1-黑马程序员】STL常用算法

​​​​​​C++从0到1 - 黑马程序员 课程学习笔记

课程链接：77 常用遍历算法-for_each_哔哩哔哩_bilibili

概 述：

• 算法主要是由头文件组成。
• 是所有STL头文件中最大的一个，范围涉及到比较、 交换、查找、遍历操作、复制、修改等等
• 体积很小，只包括几个在序列上面进行简单数学运算的模板函数
• 定义了一些模板类,用以声明函数对象

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

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返回值是差集中最后一个元素的位置。