文章目录
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++实战笔记.极客时间