C/C++教程

C++高级 —— 泛型算法

本文主要是介绍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++高级 —— 泛型算法的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!