C++高级 —— 泛型算法
2021/12/23 17:07:19
本文主要是介绍C++高级 —— 泛型算法,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
文章目录
- 增强for循环for_each
- 排序算法
- topK问题:partial_sort和nth_element
- 数据分类:partition
- 查找算法
- 二分查找:binary_search
- 大于等于:lower_bound
- 参考文献
c++中的算法是工作在容器上的一些泛型函数,其会对容器内的元素实时各种操作。这篇博客就是记录一些C++提供的常用的算法。
增强for循环for_each
这个是手写for循环的真正替代品,使用方式见如下代码:
#include <iostream> #include <algorithm> #include <array> using namespace std; int main() { array<int,5> arr = {1, 3, 5, 7, 9}; for_each(arr.begin(), arr.end(), [](int arr_element) { cout << arr_element << endl; }); }
[ik@localhost test]$ ./test 1 3 5 7 9
排序算法
常见的排序算法如下:
- sort:快速但不稳定的排序
- stable_sort:稳定的排序
- partial_sort:选出TopK
- nth_element:选出TopK,但是不做排序
- partition:按照某种规则把元素划分两组
- max_element:选出最大元素
- min_element:选出最小的元素
前两个很常见,就不介绍了。
topK问题:partial_sort和nth_element
注:
这个函数会改变原有数据
#include <iostream> #include <algorithm> #include <array> using namespace std; int main() { array<int,7> arr = {21,13,24,67,90,85,12}; //partial_sort 将begin至end中指定的最小的n个元素放入最前面,其只会排序一部分 array<int, 7> top3 = arr; partial_sort(top3.begin(), next(top3.begin(), 3), top3.end()); cout << "partial_sort top3: "; for_each(top3.begin(), top3.end(), [](int arr_element) { cout << arr_element << " "; }); cout << endl; //nth_elemnt 会选出最好的n个元素,是partial_sort的不排序版本 array<int, 7> best3 = arr; nth_element(best3.begin(), next(best3.begin(), 3), best3.end()); cout << "nth_element best3: "; for_each(best3.begin(), best3.end(), [](int arr_element) { cout << arr_element << " "; }); cout << endl; }
[ik@localhost test]$ g++ -o test test.cpp [ik@localhost test]$ ./test partial_sort top3: 12 13 21 67 90 85 24 nth_element best3: 13 12 21 24 67 85 90
数据分类:partition
注:
这个函数会改变原有数据
#include <iostream> #include <algorithm> #include <array> using namespace std; int main() { array<int,7> arr = {21,13,24,67,90,85,12}; auto print_arr = [](const auto &x) { cout << x << " "; }; auto pos = partition(arr.begin(), arr.end(), [](const auto &x) { return x > 50; }); cout << "partition: "; for_each(arr.begin(), pos, print_arr); cout << endl; cout << "arr: "; for_each(arr.begin(), arr.end(), print_arr); cout << endl; }
[ik@localhost test]$ ./test partition: 85 90 67 arr: 85 90 67 24 13 21 12
查找算法
排序算法的目标是让元素变得有序,这样就可以快速札沼,节约时间。
二分查找:binary_search
#include <iostream> #include <algorithm> #include <array> using namespace std; int main() { array<int,7> arr = {21,13,24,67,90,85,12}; auto print_arr = [](const auto &x) { cout << x << " "; }; //排序 sort(arr.begin(),arr.end()); //二分查找,但是只能确定元素是否存在 auto found = binary_search(arr.begin(), arr.end(), 88); if(!found) { cout << "not found 88" << endl; } }
[ik@localhost test]$ g++ -o test test.cpp [ik@localhost test]$ ./test not found 88
大于等于:lower_bound
由于binary_search不返回元素的指针,只返回这个元素是否存在,所以我们想要定位到元素还需要一个算法lower_bound
,这个函数会返回第一个大于等于目标元素的迭代器。
#include <iostream> #include <algorithm> #include <array> using namespace std; int main() { array<int,7> arr = {21,13,24,67,90,85,12}; auto print_arr = [](const auto &x) { cout << x << " "; }; //排序 sort(arr.begin(),arr.end()); //二分查找,但是只能确定元素是否存在 auto found = lower_bound(arr.begin(), arr.end(), 77); cout << "lower_bound: " << *found << endl; if(*found == 77) { cout << "found!" << endl; } }
[ik@localhost test]$ g++ -o test test.cpp [ik@localhost test]$ ./test lower_bound: 85
小于等于用的upper_bound也是一样的用法。
参考文献
[1] 罗剑锋.罗剑锋的C++实战笔记.极客时间
这篇关于C++高级 —— 泛型算法的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-10-04el-table 开启定时器下,表格的选中状态会消失是什么原因-icode9专业技术文章分享
- 2024-10-03如何安装和初始化飞牛私有云 fnOS?-icode9专业技术文章分享
- 2024-10-03如何安装 App 并连接到飞牛 NAS?-icode9专业技术文章分享
- 2024-10-03如何安装飞牛 TV 并连接到影视服务器?-icode9专业技术文章分享
- 2024-10-03如何在PVE和ESXI上安装飞牛私有云 fnOS?-icode9专业技术文章分享
- 2024-10-03fnOS国产最强NAS安装系统异常情况处理-icode9专业技术文章分享
- 2024-10-03飞牛NAS如何创建存储空间?-icode9专业技术文章分享
- 2024-10-03fnOS国产最强NAS硬盘会自动休眠吗?-icode9专业技术文章分享
- 2024-10-03fnOS国产最强NAS如何安装飞牛影视和创建媒体库?-icode9专业技术文章分享
- 2024-10-03fnOS国产最强NAS如何为家人朋友开通影视账号?-icode9专业技术文章分享