【万字总结篇】C++STL常用算法详解(错等年系列)
2021/11/29 20:40:00
本文主要是介绍【万字总结篇】C++STL常用算法详解(错等年系列),对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
写在前面
- 本小菜鸟是一名热爱编程的大二在校生,目前主要精力放在学习C++、数据结构和算法上。
- 我最近两个月才开始学算法(鬼知道我大一干嘛去了),被算法折磨的死去活来(太难了吧…),这两个月来在力扣刷了200多题,还是能感觉到一些进步的,继续保持,争取在年末刷到500题!这是我的力扣主页—>我的力扣主页
- 回到正题,目前C++这个专栏的博客我已经总结完了C++常用的容器、内置函数对象(仿函数)、还有此篇常用的内置算法,都是一些C++STL的内容,因为这部分内容不难,并且需要记忆的内容偏多(也就是需要多看多运用),所以就先总结出来了。之后我还会总结一些C++基础知识和C++面向对象的内容,也会有一些C++项目实战分析总结。
- 欢迎小伙伴们关注我,私信和我交流讨论关于C/C++和算法的一些东西呀。知无不答!
以下是正文部分,若有笔误,还请大佬批评指出。
目录索引
- 写在前面
- STL常用算法
- 最大值/最小值
- 常用遍历算法
- for_each
- transform
- 常用查找算法
- find
- find_if
- adjacent_find
- binary_find
- count
- count_if
- 常用排序算法
- sort
- random_shuffle
- merge
- reverse
- 常用的替换算法
- swap
- replace
- replace_if
- 常用集合算法
- set_intersection
- set_ union
- set_ difference
- 常用的算术生成算法
- accumulate
- fill
- 结束语
STL常用算法
C++STL中的内置算法主要在头文件<algorithm>
、<functional>
、<numeric>
中
<algorithm>
是所有STL头文件中最大的一个,也是包含算法最多,最常用的一个头文件,其中包含比较、交换、查找、遍历、复制、修改等算法<numeric>
体积很小,只包括几个在序列上面进行简单数学运算的模板函数<functional>
定义了一些模板类,用以声明函数对象(仿函数)
注意:本文除了最后的两个算术生成算法在头文件#include<numeric>
中以外,其余算法都在头文件#include<algorithm>
中
下面将详细介绍一些常用的内置算法,以及会用一些简单的实例帮助大家理解其如何使用。
最大值/最小值
我们先来看两个非常简单并且使用起来非常方便算法
max(a,b)
返回a
,b
中较大的数min(a,b)
返回a
,b
中较小的数
注意:
- 使用这两个函数时,不能使用与其同名的变量(
max
、min
),比如max = max(a, b)
、min = min(min, b)
等。 - 这两个算法只能比较两个数的大小,如果想比较两个以上数的大小可以嵌套使用,比如求三个数中的最大值
m = max(a, max(b, c))
示例:
#include<iostream> #include<algorithm> using namespace std; int main() { int arr[10] = { 5,8,2,4,6,9,7,0,1,3 }; int m1=arr[0]; int m2 = arr[0]; for (int i = 0; i < 10; ++i) { m1 = max(m1, arr[i]); m2 = min(m2, arr[i]); } cout << "最大值为: " << m1 << "\n最小值为: " << m2 << endl; }
输出如下:
最大值为: 9
最小值为: 0
头文件基本就是例子中那几个,此后的例子中如果没有特殊的头文件需要包含,就省去这一部分了
常用遍历算法
for_each
功能: 遍历容器,进行某种自定义操作。
这个自定义操作就是自己写的一个函数,具体你想干啥自己决定。
函数原型:
for_each(iterator beg,iterator end,_func);
遍历容器
- 第一个参数
beg
可以传入容器的起始迭代器,也可以传入数组内第一个元素的地址 - 第二个参数
end
可以传入容器的结束迭代器,或者传入数组最后一个元素的下一个位置的地址 - 最后一个参数
_func
可以传入一个函数或者函数对象
有一点必须要强调一下,对于一个数组而言,数组内第一个元素的地址相当于起始迭代器,数组最后一个元素的下一个位置的地址相当于结束迭代器,之后的例子中传入容器迭代器的参数部分(beg
,end
),有时也会传入数组的地址,不必惊讶,这就是这方面的运用。
transform
功能: 按照某种自定义规则搬运容器(或数组)内元素到另一个容器(或数组)中。
函数原型:
transform(iterator beg1,iterator end1,iterator beg2,_func);
beg1
传入原容器的起始迭代器,或数组的首地址end1
传入原容器的结束迭代器,或者数组最后一个元素的下一个位置的地址beg2
传入目标容器的起始迭代器,或者目标数组的首地址_func
传入搬运规则函数或函数对象
下面同过一个简单的例子,练习一下这两种遍历算法的使用:
void printArr(int val)//自定义操作:打印 { cout << val << " "; } int targetArr(int val)//搬运规则函数,在原数据基础上加100 { return val + 100; } int main() { int arr[10] = { 0,1,2,3,4,5,6,7,8,9 };//原数组 int target[15];//目标数组,目标数组的长度必须不小于原数组 transform(arr, arr + 10, target, targetArr); cout << "原数组打印:"; for_each(arr, arr + 10, printArr); cout << "\n目标数组打印:"; for_each(target, target + 10, printArr); }
输出如下:
原数组打印:0 1 2 3 4 5 6 7 8 9
目标数组打印:100 101 102 103 104 105 106 107 108 109
常用查找算法
简介:
find
查找元素find_if
按条件查找元素adjacent_find
查找相邻重复元素binary_find
二分查找法查找元素count
统计元素个数count_if
按条件统计元素个数
find
功能: 按值查找元素
函数原型:
find(iterator beg,iterator end,value);
-
beg
起始迭代器 -
end
结束迭代器 -
value
是要查找的元素,如果其是自定义数据类型,如类的对象、结构体类型的元素,查找时需要重载==运算符 -
找到返回指定位置的迭代器,找不到返回结束迭代器
下面通过两个例子练习find
的使用
对于内置数据类型的使用:
#include<iostream> #include<vector> #include<algorithm> using namespace std; int main() { vector<int> v; for (int i = 0; i < 10; ++i) { v.push_back(i); } auto it = find(v.begin(), v.end(), 5);//查找元素5 if (it != v.end()) { cout << "找到元素" << *it << endl; } else { cout << "未找到元素"; } }
输出如下:
找到元素5
对于自定义数据类型的使用:
class Person { public: string m_name; int m_age; Person(string name,int age):m_name(name),m_age(age){} //重载==运算符,否则find不知道按什么规则比较 bool operator==(const Person& p) { if (m_name == p.m_name && m_age == p.m_age) { return true; } return false; } }; int main() { vector<Person> v; v.push_back(Person("张三", 20)); v.push_back(Person("李四", 25)); v.push_back(Person("王五", 30)); v.push_back(Person("赵六", 40)); Person p("王五",30); auto it = find(v.begin(), v.end(), p);//查找元素5 if (it != v.end()) { cout << "找到此人:" << it->m_name << it->m_age << endl; } else { cout << "未找到此人"; } }
输入如下:
找到此人:王五30
find_if
功能: 按指定规则查找元素
函数原型:
find_if(iterator beg,iterator end,_Pred);
beg
起始迭代器end
结束迭代器_Pred
称为谓词(返回值是bool类型的函数或仿函数称为谓词),在这里用做查找规则。 谓词这个概念很重要,此后会经常见到- 找到返回指定位置的迭代器,找不到返回结束迭代器
示例:
bool greaterFive(int val)//查找规则 { return val > 5; } int main() { vector<int> v; for (int i = 0; i < 10; ++i) { v.push_back(i); } auto it = find_if(v.begin(), v.end(), greaterFive); if (it != v.end()) { cout << "找到大于5的元素:" << *it << endl; } else { cout << "未找到" << endl; } }
输出如下:
找到大于5的元素:6
adjacent_find
功能: 查找相邻且重复的元素
函数原型:
adjacent_find(iterator beg,iterator end);
beg
起始迭代器end
结束迭代器- 找到返回相邻元素第一个元素位置的迭代器,没找到返回容器结束迭代器
示例:
int main() { vector<int> v; v.push_back(2); v.push_back(5); v.push_back(2); v.push_back(3); v.push_back(3); auto it = adjacent_find(v.begin(), v.end()); if (it != v.end()) { cout << "相邻重复的元素为:" << *it << endl; } else { cout << "不存在相邻重复的元素" << endl; } }
输出如下:
相邻重复的元素为:3
binary_find
功能: 查找指定元素value,找到返回true,否则返回false
特点:
- 查找速度比一般查找算法快的多,因为一般查找算法的时间复杂度为O(n),而二分查找算法的时间复杂度为O(log(n))
- 但二分查找也有局限性,它不能用于查找无序序列,也就是说只能利用二分查找查升序排序或降序排序序列中指定的元素
函数原型:
bool binary_search(iterator beg,iterator end,value);
beg
起始迭代器end
结束迭代器- 只能在有序序列中使用,如果用于无序序列,函数返回的结果将不准确
示例:
int main() { vector<int> v; for (int i = 0; i < 10; ++i) { v.push_back(i); } bool flag = binary_search(v.begin(), v.end(), 5); if (flag == 1) { cout << "找到指定元素" << endl; } else { cout << "未找到" << endl; } }
输出如下:
找到指定元素
count
功能: 统计相同元素出现次数
函数原型:
count(iterator beg,iterator end,value);
- 统计元素
value
的个数 beg
起始迭代器end
结束迭代器
示例:
我们重点看一下count
在自定义数据类型中的使用
class Person { public: string m_name; int m_age; Person(string name,int age):m_name(name),m_age(age) {} bool operator==(const Person& p)//重载==,作为统计元素规则 { if (m_age == p.m_age) { return true;//统计年龄相同的元素 } return false; } }; int main() { vector<Person> v; v.push_back(Person("张三", 30)); v.push_back(Person("李四", 25)); v.push_back(Person("王五", 35)); v.push_back(Person("赵六", 25)); v.push_back(Person("熊大", 25)); v.push_back(Person("熊二", 20)); Person p("光头强", 25); int num = count(v.begin(), v.end(), p); cout << "年龄为25的生物的个数:" << num << endl; }
输出如下:
年龄为25的生物的个数:3
count_if
功能: 按照指定条件统计元素个数
函数原型:
count_if(iteraotr beg,iterator end,_Pred);
beg
起始迭代器end
结束迭代器- _Pred 谓词,在这里用作统计的条件
示例:
bool greater5(int val) { return val > 5; } int main() { vector<int> v; for (int i = 0; i < 10; ++i) { v.push_back(i); } int num = count_if(v.begin(), v.end(), greater5); cout << "大于5的元素的个数为:" << num << endl; }
输出如下:
大于5的元素的个数为:4
常用排序算法
简介:
sort
对容器内元素进行排序random_shuffle
对指定范围内元素随机调整次序merge
容器元素合并,并存储到另一容器中reverse
反转指定范围的元素
sort
功能: 对容器或数组内元素进行排序
特点:
sort
是C++STL中最常用的算法了,没有之一!- sort排序是最快的排序,时间复杂度O(n*log(n)),因为其内部主要由快速排序+插入排序+堆排序实现的。
- 当排序的序列数据量大时采用快排算法,分段归并排序。一旦分段后的数据量小于某个门槛(16),为避免快排的递归调用带来过大的额外负荷,就改用插入排序。如果递归层次过深,还会改用堆排序。
函数原型:
sort(iterator beg,iterator end,_Pred);
- 默认对容器内元素升序排序(从小到大)
beg
起始迭代器end
结束迭代器- _Pred 谓词,可以不填这个参数(默认升序排序),如果想按照其他规则排序,如降序排序,这个参数就必须填入
- 这个算法只有随机存取迭代器可以使用,如普通数组、vector容器、deque容器等等
下面的一个例子将会把前面的算法for_each
、transform
和sort
结合在一起使用
void myPrint(int val) { cout << val << " "; } int targetVector(int val) { return val; } bool myComepare(int v1,int v2) { return v1 > v2; } int main() { int a[10] = { 1,4,7,2,5,8,3,6,9 };//乱序数组 vector<int> v(10); transform(a, a + 10, v.begin(), targetVector); cout << "排序前打印数组a: "; for_each(a, a + 10, myPrint); cout << "\n排序前打印容器v: "; for_each(v.begin(), v.end(), myPrint); sort(a, a + 10);//默认升序排序 cout << "\n升序排序后打印数组a: "; for_each(a, a + 10, myPrint); sort(v.begin(), v.end(), myComepare);//降序排序 cout << "\n降序排序后打印容器v: "; for_each(v.begin(), v.end(), myPrint); }
输出如下:
排序前打印数组a: 1 4 7 2 5 8 3 6 9 0
排序前打印容器v: 1 4 7 2 5 8 3 6 9 0
升序排序后打印数组a: 0 1 2 3 4 5 6 7 8 9
降序排序后打印容器v: 9 8 7 6 5 4 3 2 1 0
random_shuffle
功能: 指定范围内元素随机调整次序
函数原型:
random_shuffle(iterator beg,iterator end);
beg
起始迭代器end
结束迭代器- 指定范围
[beg,end)
内元素随机打乱
注意: 在使用random_shuffle
之前最好先撒下随机数种子srand((unsigned)time(NULL))
,否则每次随机的结果都是一样的。srand
函数在头文件#include<ctime>
中。
示例:
void myPrint(int val) { cout << val << " "; } int main() { int a[10] = { 0,1,2,3,4,5,6,7,8,9 }; srand((unsigned)time(NULL));//随机数种子 random_shuffle(a, a + 10); cout << "随机打乱后:"; for_each(a, a + 10, myPrint); }
打印如下(每个人打印的结果可能不同,因为是随机打乱的):
随机打乱后:0 5 4 6 7 1 8 3 9 2
merge
功能: 将两个有序的容器合并到另一个目标容器中,合并后该目标容器仍然有序
函数原型:
merge(iterator beg1,iterator end1,iterator beg2,iterator end2,iterator target_beg);
beg1
第一个容器或数组起始迭代器end1
第一个容器或数组结束迭代器beg2
第一个容器或数组起始迭代器end2
第一个容器或数组结束迭代器target_beg
目标容器或数组起始迭代器
注意:
- 两个容器必须是有序的并且是同一种顺序,不能一个升序一个降序
- 目标容器的大小必须提前指定,并且其大小不小于合并的那两个容器的大小之和
示例:
void myPrint(int val) { cout << val << " "; } int main() { vector<int> v; int a[10] = { 0,1,2,3,4,5,6,7,8,9 }; for (int i = 0; i < 10; ++i) { v.push_back(i + 5); } vector<int> target(10 + v.size()); cout << "打印a: "; for_each(a,a+10, myPrint); cout << "\n打印打印v2: "; for_each(v.begin(), v.end(), myPrint); merge(a, a + 10, v.begin(), v.end(), target.begin()); cout << "\n打印合并后容器target: "; for_each(target.begin(), target.end(), myPrint); }
打印如下:
打印a: 0 1 2 3 4 5 6 7 8 9
打印打印v2: 5 6 7 8 9 10 11 12 13 14
打印合并后容器target: 0 1 2 3 4 5 5 6 6 7 7 8 8 9 9 10 11 12 13 14
reverse
功能: 将容器内元素进行反转
函数原型:
reverse(iterator beg,iterator end);
beg
起始迭代器end
结束迭代器
示例:
int main() { int arr[10] = { 0,1,2,3,4,5,6,7,8,9 }; reverse(arr, arr + 10); cout << "反转后输出:"; for (int i = 0; i < 10; ++i) { cout << arr[i] << " "; } }
输出如下:
反转后输出:9 8 7 6 5 4 3 2 1 0
常用的替换算法
简介:
swap
交换两个容器的元素,或者仅仅交换两个元素replace
将容器内指定范围的旧元素替换为新元素replace_if
按条件将替换元素,满足条件的替换成指定元素
swap
功能: 交换两个容器内的元素,或者仅仅交换两个元素
函数原型:
swap(container c1,container c2);
c1
容器1或元素1c2
容器2或元素2
注意: c1
和c2
必须是同种类型的容器或元素,否则换不了,编译器报错。
示例:
void myPrint(int val) { cout << val << " "; } int main() { int a=1, b=2; vector<int> v1,v2; for (int i = 0; i < 10; ++i) { v1.push_back(i); //v1: 0,1,2,3,4,5,6,7,8,9 v2.push_back(9 - i); //v2: 9,8,7,6,5,4,3,2,1,0 } swap(a, b); cout << "a = " << a << ", b = " << b << endl; swap(v1, v2); cout << "输出v1: "; for_each(v1.begin(), v1.end(), myPrint); cout << "\n输出v2: "; for_each(v2.begin(), v2.end(), myPrint); }
输出如下:
a = 2, b = 1
输出v1: 9 8 7 6 5 4 3 2 1 0
输出v2: 0 1 2 3 4 5 6 7 8 9
replace
功能: 将容器内指定范围的旧元素替换为新元素
函数原型:
replace(iterator beg,iterator end,oldvalue,newvalue);
beg
起始迭代器end
结束迭代器- 将容器
[beg,end)
内元素oldvalue
全部换成newvalue
示例:
int main() { int arr[10] = { 6,3,1,4,8,6,6,7,6,5 }; replace(arr + 1, arr + 10, 6, 60); cout << "替换后:"; for (int i = 0; i < 10; ++i) { cout << arr[i] << " "; } }
输入如下:
替换后:6 3 1 4 8 60 60 7 60 5
replace_if
功能: 按条件将替换元素,满足条件的替换成指定元素
函数原型:
replace_if(iterator beg,iterator end,_Pred,newvalue);
beg
起始迭代器end
结束迭代器_Pred
是谓词,将满足谓词条件的元素替换成newvalue
示例:
bool lessFive(int val)//谓词,条件是小于5的数 { return val < 5; } int main() { int arr[10] = { 0,1,2,3,4,5,6,7,8,9 }; replace_if(arr, arr + 10, lessFive, 0); cout << "替换后:"; for (int i = 0; i < 10; ++i) { cout << arr[i] << " "; } }
输出如下:
替换后:0 0 0 0 0 5 6 7 8 9
常用集合算法
简介:
set_intersection
求两个容器的交集set_union
求两个容器的并集set_difference
求两个容器的差集
set_intersection
功能: 求两个容器内元素的交集,并把这个交集传给另一个容器
函数原型:
set_intersection(iterator beg1,iterator end1,iterator beg2,iterator end2,iterator target_beg)
beg1
第一个容器起始迭代器end1
第一个容器结束迭代器beg2
第一个容器起始迭代器end2
第一个容器结束迭代器target_beg
目标容器的起始迭代器- 函数返回值为目标容器最后一个元素的下一个地址处的迭代器
注意:求交集的两个容器必须是有序序列,而且同序(同升或同降),否则报错。
示例:
int main() { vector<int> v1, v2; for (int i = 0; i < 10; ++i) { v1.push_back(i);//v1: 0,1,2,3,4,5,6,7,8,9 v2.push_back(i + 5); //v2: 5,6,7,8,9,10,11,12,13,14 } vector<int> target; //设置目标容器大小 target.resize(min(v1.size(), v2.size())); auto target_end = set_intersection(v1.begin(), v1.end(), v2.begin(), v2.end(), target.begin()); cout << "打印存储交集的目标容器:"; for (auto it = target.begin(); it != target_end; ++it) { cout << *it << " "; } }
输出如下:
打印存储交集的目标容器:5 6 7 8 9
set_ union
功能: 求两个容器内元素的并集,并把这个并集传给另一个容器
函数原型:
set_union(iterator beg1,iterator end1,iterator beg2,iterator end2,iterator target_beg)
beg1
第一个容器起始迭代器end1
第一个容器结束迭代器beg2
第一个容器起始迭代器end2
第一个容器结束迭代器target_beg
目标容器的起始迭代器- 函数返回值为目标容器最后一个元素的下一个地址处的迭代器
注意:求并集的两个容器必须是有序序列,而且同序(同升或同降),否则报错。
示例:
int main() { vector<int> v1, v2; for (int i = 0; i < 10; ++i) { v1.push_back(i);//v1: 0,1,2,3,4,5,6,7,8,9 v2.push_back(i+5); //v2: 5,6,7,8,9,10,11,12,13,14 } vector<int> target; //设置目标容器大小 target.resize(v1.size()+ v2.size()); auto target_end = set_union(v1.begin(), v1.end(), v2.begin(), v2.end(), target.begin()); cout << "打印存储并集的目标容器:"; for (auto it = target.begin(); it != target_end; ++it) { cout << *it << " "; } }
输出如下:
打印存储并集的目标容器:0 1 2 3 4 5 6 7 8 9 10 11 12 13 14
set_ difference
功能: 求两个容器内元素的差集,并把这个差集传给另一个容器
所谓差集:容器v1相对于v2的差集是,v1内元素去除v1和v2交集部分所剩余的元素
函数原型:
set_difference(iterator beg1,iterator end1,iterator beg2,iterator end2,iterator target_beg)
beg1
第一个容器起始迭代器end1
第一个容器结束迭代器beg2
第一个容器起始迭代器end2
第一个容器结束迭代器target_beg
目标容器的起始迭代器- 函数返回值为目标容器最后一个元素的下一个地址处的迭代器
注意:求并集的两个容器必须是有序序列,而且同序(同升或同降),否则报错。
示例:
int main() { vector<int> v1, v2; for (int i = 0; i < 10; ++i) { v1.push_back(i);//v1: 0,1,2,3,4,5,6,7,8,9 v2.push_back(i + 5); //v2: 5,6,7,8,9,10,11,12,13,14 } vector<int> target; //设置目标容器大小 target.resize(max(v1.size(), v2.size())); auto target_end = set_difference(v1.begin(), v1.end(), v2.begin(), v2.end(), target.begin()); cout << "打印v1和v2的差集:"; for (auto it = target.begin(); it != target_end; ++it) { cout << *it << " "; } target_end = set_difference(v2.begin(), v2.end(), v1.begin(), v1.end(), target.begin()); cout << "\n打印v2和v1的差集:"; for (auto it = target.begin(); it != target_end; ++it) { cout << *it << " "; } }
输出如下:
打印v1和v2的差集:0 1 2 3 4
打印v2和v1的差集:10 11 12 13 14
常用的算术生成算法
注意:本文之前介绍的所有算法都在头文件
#include<algorithm>
中,现在将介绍两个在#include<numeric>
中的算法
简介:
accumulate
计算容器元素累计总和fill
向容器中添加元素
accumulate
功能: 计算容器内元素累计总和
函数原型:
accumulate(iterator beg,iterator end,value);
beg
起始迭代器end
结束迭代器value
是起始值,如果不需要把它设为0- 函数返回容器内元素累计总和
#include<iostream> #include<vector> #include<numeric> using namespace std; int main() { vector<int> v; for (int i = 0; i <= 100; i++) { v.push_back(i); } int sum = accumulate(v.begin(), v.end(), 0); cout << "容器内元素和为:" << sum << endl; }
输出如下:
容器内元素和为:5050
fill
功能: 向容器中填充指定元素
函数原型:
fill(iterator beg,iterator end,value);
beg
起始迭代器end
结束迭代器- 向容器中填充
value
示例:
#include<iostream> #include<vector> #include<numeric> using namespace std; int main() { vector<int> v(10); fill(v.begin(), v.end(), 1); for (int i = 0; i < 10; ++i) { cout << v[i] << " "; } }
输出如下:
1 1 1 1 1 1 1 1 1 1
结束语
本篇到此结束,共一万两千多字,你的点赞、评论、关注、收藏都是对我最大的支持,谢谢啦!(悄咪咪说一声,本篇可能是C站最详细的C++STL常用算法总结哦)。
这篇关于【万字总结篇】C++STL常用算法详解(错等年系列)的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-11-23增量更新怎么做?-icode9专业技术文章分享
- 2024-11-23压缩包加密方案有哪些?-icode9专业技术文章分享
- 2024-11-23用shell怎么写一个开机时自动同步远程仓库的代码?-icode9专业技术文章分享
- 2024-11-23webman可以同步自己的仓库吗?-icode9专业技术文章分享
- 2024-11-23在 Webman 中怎么判断是否有某命令进程正在运行?-icode9专业技术文章分享
- 2024-11-23如何重置new Swiper?-icode9专业技术文章分享
- 2024-11-23oss直传有什么好处?-icode9专业技术文章分享
- 2024-11-23如何将oss直传封装成一个组件在其他页面调用时都可以使用?-icode9专业技术文章分享
- 2024-11-23怎么使用laravel 11在代码里获取路由列表?-icode9专业技术文章分享
- 2024-11-22怎么实现ansible playbook 备份代码中命名包含时间戳功能?-icode9专业技术文章分享