[数据结构与算法]C++高级 —— 泛型算法

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