从C向C++17——常见算法

一.常见算法

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

二.常见遍历算法

1.for_each

函数原型：

for_each(iterator beg,iterator end,_func)；
1

遍历算法，用来遍历某个容器的元素：

• beg：开始迭代器
• end：结束迭代器
• func：普通函数或函数对象，遍历每个元素时需要执行的操作

案例练习：

#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
using namespace std;

class prin
{
public:
    void operator()(int val)
    {
        cout << val << " ";
    }
};

void print(int val)
{
    cout << val << " ";
}
void test01()
{
    vector<int> v;
    for (int i = 0; i < 10; i++)
    {
        v.push_back(i);
    }

    for_each(v.begin(), v.end(),print );         //普通函数
    for_each(v.begin(), v.end(), prin());         //仿函数
}


int main()
{
    test01();
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37

2.transform

用途：搬运容器的元素到另一个容器中

函数原型：

transform(iterator beg1,iterator end,iterator beg2,_func);
1

• beg1：源容器开始迭代器
• end：源容器结束迭代器
• beg2：目标容器开始迭代器、
• _func：普通函数或者函数对象，搬运每个元素时需要执行的操作

注意：虽然transform最后结果有点类似拷贝赋值，但是其搬运的目标容器必须有足够的容量接受数据，也就是是说要用resize设置目标容器的容量大小，提前开辟空间。

三.常用查找算法

1.find

用途：查找指定元素，找到返回指定元素的迭代器，找不到返回结束迭代器end()

函数原型：

find(iterator beg,iterator end,value)；
1

• beg：开始迭代器
• end：结束迭代器
• value：要查找的元素

这里的find查找在下，对应的迭代器是支持随机访问的，而向set和map容器这种不支持随机访问的，其find和count是成员函数，而这里的find是库的全局函数。

如果对于自定义数据类型的查找，需要重载==来实现find的判断。

2.finf_if

用途：按条件查找元素

函数原型：

find_if(iterator beg,iterator end,_pred);
1

按值查找元素，找到返回指定位置迭代器，找不到返回结束迭代器位置

• beg：开始迭代器
• end：结束迭代器
• _pred：普通函数或谓词(返回bool类型的仿函数)

3.adjacent_find

用法：查找相邻重复元素

函数原型：

adjacent_find(iterator beg,iterator end);
1

查找相邻重复元素，返回相邻元素的第一个位置的迭代器

• beg：开始迭代器
• end：结束迭代器

4.binary_search

用法：查找指定元素是否存在

函数原型：

bool binary_search(iterator beg,iterator end,value);
1

查找指定的元素，找到返回true，否则返回false

注意：该算法在无序序列中不可使用，还得是升序。

也就意味着你的带查找容器要么是关联式容器，要么是经过sort排序后的容器。

5.count

用法：统计元素个数

函数原型：

count(iterator beg,iterator end,value);
1

统计自定义数据类型的时候，需要搭配重载==来使用。

6.count_if

用法：按条件统计元素个数

函数原型：

count_if(iterator beg,iterator end,value);
1

按条件统计元素的个数

• beg：开始迭代器

• end：结束迭代器

• _pred：普通函数或谓词(返回bool类型的仿函数)

四.常用排序算法

1.sort

sort(iterator beg,iterator end,_pred);
1

sort是最常见的排序算法，可以通过后面的谓词实现升序或降序排列。

2.random_shuffle

用途：将指定范围内的数据随机排序，因此也叫洗牌算法。

random_shufffle(iteratorbeg,iterator end);
1

• beg：开始迭代器
• end：结束迭代器

该算法比较实用，但是使用时记得需要加上随机数的种子，不然每次随机都是一样的。

3.merge

用法：两个容器元素合并，并存储到另一容器中。

merge(iterator beg1,iterator end1,iteratpr beg2,iterator end3,iterator dest);
1

• beg1：容器1开始迭代器
• end1：容器1结束迭代器
• beg2：容器2开始迭代器
• end2：容器2结束迭代器
• dest：目标容器开始迭代器

注意：

• 两个源容器必须是有序的
• 目标容器需要提前开辟足够的空间
• 合并后的容器也是有序的，即把容器1和容器2的所有元素都进行了排序

4.reverse

用法：将容器内的数据元素进行反转

reverse(beg,end);
1

• 不只有list链表反转，其他容器也行
• 传入两个迭代器即可

五.常用拷贝和替换算法

1.copy

用法：将容器区间的元素拷贝到另一容器中

copy(iterator beg,iterator end,iterator dest);
1

• beg：开始迭代器
• end：结束迭代器
• dest：目标容器开始迭代器

利用copy算法进行拷贝时，记得目标容器也需要提前开辟足够的空间。

2.replace

用法：将容器内指定范围内的旧元素修改为新元素

replace(iterator beg,iterator end,oldvalue,newvalue);
1

• beg：开始迭代器
• end：结束迭代器
• oldvalue：旧元素
• newvalue：新元素

3.replace_if

用法：将区间内满足条件的元素替换成指定元素

replace_if(iterator beg,iterator end,_pred,newvalue);
1

• beg：开始迭代器
• end：结束迭代器
• _pred：谓词，告诉编译器什么条件
• newvalue：新元素

4.swap

用法：互换两个容器的所有元素

函数原型：

swap(container c1,container c2);
1

注意：交换的两个容器必须是同种类型的容器

六.常用算术生成算法

注意：算术生成算法属于小型算法，使用时包含的头文件为#include <numeric>

1.accumulate

用法：计算区间内元素值的总和

accumulate(iterator beg,iterator end,value);
1

• beg：开始迭代器
• end：结束迭代器
• value：起始累加值

2.fill

用法：后期向容器中填充指定的数据

函数原型：

fill(iterator beg,iterator end,value);
1

• beg：开始迭代器
• end：结束迭代器
• value：填充的值

该函数主要是用于后期填充数据，而我们知道resize的重载版本可以在设定前期填充数据。

七.常用集合算法

1.set_intersection

用法：求两个容器的交集，结果放在目标容器中

set_intersection(iterator beg1,iterator end1,iteraor beg2,iterator end2,iterator dest);
1

• beg1：容器1开始迭代器
• end1：容器1结束迭代器
• beg2：容器2开始迭代器
• end2：容器2结束迭代器
• dest：目标容器开始迭代器

注意：

• 两个容器不一定非得是set集合，但必须同类型
• 两个集合必须是有序序列
• 目标容器需要提前开辟空间（取两者大小中最小的一个）
• 遍历最后目标容器时一般不使用v.end()而使用set_intersection的返回迭代器

这里解释以下为什么最后不用v.end()而使用set_intersection的返回迭代器，是因为我们开辟目标容器时一般取特殊情况即二个源容器大小较小的那一个，而往往最后的交集结果比其要少，后面用默认值填充。

2.set_union

用法：求两个集合的并集，结果放在目标容器中

set_union(iterator beg1,iterator end1,iteraor beg2,iterator end2,iterator dest);
1

• beg1：容器1开始迭代器
• end1：容器1结束迭代器
• beg2：容器2开始迭代器
• end2：容器2结束迭代器
• dest：目标容器开始迭代器

注意：

• 两个容器不一定非得是set集合，但必须同类型
• 两个集合必须是有序序列
• 目标容器需要提前开辟空间（取两者大小相加）
• 遍历最后目标容器时一般不使用v.end()而使用set_intersection的返回迭代器

3.set_difference

用法：求两个集合的差集，结果放在目标容器中

set_difference(iterator beg1,iterator end1,iteraor beg2,iterator end2,iterator dest);
1

• beg1：容器1开始迭代器
• end1：容器1结束迭代器
• beg2：容器2开始迭代器
• end2：容器2结束迭代器
• dest：目标容器开始迭代器

注意：

• 两个容器不一定非得是set集合，但必须同类型
• 两个集合必须是有序序列
• 目标容器需要提前开辟空间（取两者最大的那一个）
• 遍历最后目标容器时一般不使用v.end()而使用set_intersection的返回迭代器

最后说一下差集的操作，求差集有顺序性，v1和v2的差集与v2和v1的差集是不一样的。比如v1：1、2、3、4、5；``v2：3、4、5、6、7；这两个集合，如果求v1和v2的差集那么就是v1减去v1和v2的交集，所以结果是1、2；而如果求v2和v1的差集那么就是v2减去v1和v2`的交集，所以结果是6、7。

最后：如无特殊说明，该算法的头文件均是 。