【C++】算法库(批量操作、搜索操作)

C++算法库

文章目录

• C++算法库
• • 批量操作
  • • for_each
    • for_each_n
  • 搜索操作
  • • all_of ,any_of ,none_of
    • find, find_if, find_if_not
    • find_end
    • std::find_first_of
    • adjacent_find
    • count, count_if
    • equal
    • search
    • search_n

算法库提供大量用途的函数（例如查找、排序、计数、操作），它们在元素范围上操作。

》》概念约束
》》ranges标准库

C++20 在命名空间 std::ranges 中提供大多数算法的受约束版本，在这些算法中，范围既可以由迭代器-哨位对，也可以由单个 range 实参指定，还支持投影和成员指针可调用对象。

std::vector<int> v {7, 1, 4, 0, -1};
std::ranges::sort(v); // 受约束算法

• 头文件

#include <algorithm>
#include <numeric> 
#include <memory>
#include <ranges> //C++20

批量操作

for_each

应用函数到范围中的元素

std::vector<int> v {3, -4, 2, -8, 15, 267};

auto print = [](const int& n) { std::cout << n << ' '; };

std::for_each(v.cbegin(), v.cend(), print);//3 -4 2 -8 15 267 
std::for_each(v.begin(), v.end(), [](int &n){ n++; });
std::for_each(v.cbegin(), v.cend(), print);//4 -3 3 -7 16 268 

• 应用ranges

std::vector<int> nums{3, 4, 2, 8, 15, 267};

auto print = [](const auto& n) { std::cout << ' ' << n; };

std::ranges::for_each(std::as_const(nums), print);//3 4 2 8 15 267
std::ranges::for_each(nums, [](int &n){ n++; });
std::ranges::for_each(std::as_const(nums), print);// 4 5 3 9 16 268

for_each_n

应用一个函数对象到序列的前 n 个元素

std::vector<int> v {3, -4, 2, -8, 15, 267};
std::for_each_n(v.begin(), 3, [](int &n){ n++; });
//4 -3 3 -8 15 267

• ranges

std::vector<int> nums{3, 4, 2, 8, 15, 267};
std::ranges::for_each_n(nums.begin(), 3, [](int &n){ n++; });
//4 5 3 8 15 267

搜索操作

all_of ,any_of ,none_of

检查谓词是否对范围中所有、任一或无元素为 true

• all_of 所有是否满足条件
• any_of 至少有一个满足
• none_of 没有一个满足

std::vector<int> v2 {10 , 2};
if (std::all_of(v2.begin(), v2.end(), [](int i) { return i % 2 == 0; }))
    std::cout << "All numbers are even\n"; //true
if (std::none_of(v2.begin(), v2.end(), [](int i) { return i % 2 == 0; }))
    std::cout << "None of them are odd\n"; //false
if (std::any_of(v2.begin(), v2.end(), [](int i) { return i % 2 == 0; }))
    std::cout << "At least one number is odd\n"; //true

• ranges

std::vector<int> v2 {10 , 2};
if (std::ranges::all_of(v2, [](int i) { return i % 2 == 0; }))
    std::cout << "All numbers are even\n"; //true
if (std::ranges::none_of(v2, [](int i) { return i % 2 == 0; }))
    std::cout << "None of them are odd\n"; //false
if (std::ranges::any_of(v2, [](int i) { return i % 2 == 0; }))
    std::cout << "At least one number is odd\n"; //true

find, find_if, find_if_not

寻找首个满足特定判别标准的元素

• find 寻找首个为x的元素
• find_if 寻找首个为true的元素
• find_if 寻找首个为false的元素

std::distance(v.begin(), x)返回出现位置

std::vector<int> v {3, -4, 2, -8, 15, 267};
auto x = std::find(v.begin(),v.end(),3);
if(x != v.end())
    std::cout << "v 包含" << std::distance(v.begin(), x); // 0
auto y = std::find_if(v.begin(),v.end(), [](int i) { return i % 2 == 0; });
if(y != v.end())
    std::cout << "v " << std::distance(v.begin(), y); // 1
auto z = std::find_if_not(v.begin(),v.end(), [](int i) { return i % 2 == 0; });
if(z != v.end())
    std::cout << "v " << std::distance(v.begin(), z); // 0

• ranges

std::vector<int> v {3, -4, 2, -8, 15, 267};
auto x = std::ranges::find(v,3);
if(x != v.end())
    std::cout << "v 包含" << std::distance(v.begin(), x); // 0
auto y = std::ranges::find_if(v, [](int i) { return i % 2 == 0; });
if(y != v.end())
    std::cout << "v " << std::distance(v.begin(), y); // 1
auto z = std::ranges::find_if_not(v, [](int i) { return i % 2 == 0; });
if(z != v.end())
    std::cout << "v " << std::distance(v.begin(), z); // 0

find_end

在特定范围中寻找最后出现的元素序列

    std::vector<int> v {1,2,3,1,2,3,4,5,6};
    vector<vector<int>> v2 = {{1, 2, 3}, {3, 4, 5}};
    for(auto x : v2){
        auto t = std::find_end(v.begin(), v.end(), x.begin() , x.end());
        std::cout << std::distance(v.begin(), t);//3 5
    }

std::find_first_of

在范围 [first, last) 中搜索范围 [s_first, s_last) 中的任何元素

    std::vector<int> v {1,2,3,1,2,3,4,5,6};
    vector<vector<int>> v2 = {{1, 2, 3}, {3, 4, 5}};
    for(auto x : v2){
        auto t = std::find_first_of(v.begin(), v.end(), x.begin() , x.end());
        std::cout << std::distance(v.begin(), t);//0 2
    }

adjacent_find

查找首对相邻的相同（或满足给定谓词的）元素

std::vector<int> v1{0, 1, 2, 3, 40, 40, 41, 41, 5};
auto i1 = std::adjacent_find(v1.begin(), v1.end());
if (i1 == v1.end())
    std::cout << "没有匹配的相邻元素\n";
else
    std::cout << "第一对相等的相邻元素位于 "
                << std::distance(v1.begin(), i1) << "，*i1 = "
                << *i1 << '\n';

count, count_if

• count x个数
• count_if 满足表达式为true的个数

std::vector<int> v = {1, 2, 3, 4, 4, 3, 7, 8, 9, 10};
std::cout << std::count(v.begin(),v.end(),3);//2
std::cout << std::count_if(v.begin(),v.end(),[](int i) { return i % 2 == 0; });//偶数个数 5
string s = "aabbbbcccccccc";
std::cout << std::count(s.begin(),s.end(),'c');//8

• ranges

std::vector<int> v = {1, 2, 3, 4, 4, 3, 7, 8, 9, 10};
std::cout << std::ranges::count(v,3);//2
std::cout << std::ranges::count_if(v,[](int i) { return i % 2 == 0; });//偶数个数 5
string s = "aabbbbcccccccc";
std::cout << std::ranges::count(s,'c');//8

equal

确定两个元素集合是否是相同的

string a = "xyz";
string b = "xyz";
if(std::equal(a.begin(),a.end(),b.begin(),b.end()))
    std::cout << "equal";

• ranges

string a = "xyz";
string b = "xyz";
if(std::ranges::equal(a,b))
    std::cout << "equal";

search

搜索范围 [first, last) 中首次出现元素序列 [s_first, s_last) 的位置。

string str = "ddccabcabcabc";
string words = "abc";
auto it = std::search(str.begin(),str.end(),words.begin(),words.end());
std::cout << std::distance(str.begin() , it);//4

search_n

在范围中搜索一定量的某个元素的连续副本
在范围 [first, last) 中搜索 count 个等同元素的序列，每个都等于给定的值 value

string str = "1001010100010101001010101";
auto it = std::search_n(str.begin() , str.end() , 3 , '0');
std::cout << std::distance(str.begin() , it); //第一次出现连续的三个零的位置：8