新特性

C++ 20 Ranges

备注：编译时需要设置 -std=c++20

g++ -std=c++20 test.cpp -o app

前缀内容 – Ranges 核心、lambda表达式和算法工作机制、管道符

/* 
    Q1: Ranges？
        传统STL基于迭代器的一次升级！

        处理容器和迭代器间复杂操作
        任何可迭代的对象均可视为Ranges，
            · 包括STL容器（vector, list, map...）
            · 数组
            · 由函数生成的连续连续或非连续序列 (std::iota() - 递增序列函数)

    Q2: Ranges core？  View
        Views 不会复制或修改原始数据，
        而是通过对数据的非拥有引用，使得在不修改原始数据下对数据进行过滤、映射、切片等操作

    Q3: How to use Ranges?
        需要知道： 
            lambda表达式中的捕获外部变量（C++11）
            管道符 | (将左边的数据流向右边)
*/

// Q3 Answer
#include<iostream>
#include<vector>
#include<ranges>
#include<algorithm>
using namespace std; 

int ViewFunc(){
    vector<int> Number = {0, 1, 2, 3, 4, 5, 6};
    // views视图
    auto ViewNumber = Number | views::filter([](int n){return n % 2 == 0;});

    // 输出视图 (ViewNumber是一个范围)
    ranges::for_each(ViewNumber, [](int n) {cout << n << ' ';});
    return 0;
}

/*
    刨析原理:
        P1.Lambda表达式和算法工作机制
        P2. 管道符 |
*/

// P1-1 捕获外部变量 []
int LambdaFunc1(){
    int externalVar = 20;
    auto lambda = [externalVar](){
        // 此处使用的是 "捕获"的 externalVar副本
        cout << externalVar << endl;
    };
    lambda();  // 无需参数

    return 0;
}

// P1-1 扩展，捕获全体外部参数 [=] - 值捕获、 [&] - 引用捕获
int lambdaFunc1_Plus1(){
    int x = 10, y = 20;

    // 值捕获
    auto lambda1 = [=](){  // 捕获所有外部变量的副本
        // 可以访问x和y,但不能修改它们，除非使用 mutable
        cout << x + y << endl;
    };
    lambda1();
    
    // 使用 mutable 修改内部值并不会影响外部变量
    auto lambda2 = [=]() mutable{
        ++x;
        cout << x + y << endl;
    };
    lambda2();
    cout << x << endl;

    // 引用捕获 (修改内部值会修改外部变量)
    auto lambda3 = [&](){
        ++x;
        cout << x + y << endl;
    };
    lambda3();
    cout << x << endl;

    return 0;
}

// 值传递和引用传递可以混合使用 [=, &a] - 除 引用捕获a外其他外部变量均值捕获
int lambdaFunc1_Plus2(){
    int x = 10, y = 20, z = 30;

    auto lambda = [=, &x]() mutable{
        ++x, ++y, ++z;
        cout << x + y + z << endl;
    };

    lambda();

    cout << "x = " << x << "\ty = " << y << "\tz = " << z << endl;

    return 0;
}


// P1-2 参数传递 ()
int LambdaFunc2(){
    int eternalVar = 20;
    auto lambda = [](int n){
        cout << n << endl;
    };
    lambda(eternalVar);  // 需要传递参数

    return 0;
}

// p2  管道符， ranges一部分
int PipeSymbolFunc(){
    auto ints = {1,2,3,4,5};
    auto even = [](int n){return n % 2 == 0;};
    auto square = [](int n){return n * n;};

    // ints中的每个i都流向后面的判断或操作
    for(const auto& i: ints | views::filter(even) | views::transform(square)){
        cout << i << endl;
    }

    return 0;
}

int main(){
    // LambdaFunc1();
    // LambdaFunc2();
    // lambdaFunc1_Plus2();
    PipeSymbolFunc();
    return 0;
}

Ranges适配器

/*
    Q1：Ranges adapter?
        A1. transform， 接受函数或lambda，将输入的Range中的元素应用该函数，并生成一个新的函数
        A2. filter, 根据提供的谓词筛选符合条件的元素，舍弃不符合条件的元素
        A3. take, 取Range中前N个元素
        A4. drop, 丢弃Range的前N个元素, 返回剩余元素
        A5. join 用于将嵌套的范围(ex: vector<vector<T>>, list<string>)扁平为一个连续的单一范围
        A6. slice, 取出Range的一个区间 (C++23新增)
*/


#include<iostream>
#include<ranges>
#include<algorithm>
#include<vector>
using namespace std;

// A1. transform
int Adapter_transform(){
    vector<int> vec = {1,2,3,4,5};
    
    // 写法1
    // for(const int& v: vec | views::transform([](int n){return n*n;})){
    //     cout << v << ' ';
    // }

    // 写法2 - 更推荐
    auto View_vec = vec | views::transform([](int n){return n * n;});

    ranges::for_each(View_vec, [](int n){
        cout << n << ' ';
    });

    return 0;
}

// A2. filter
int Adapter_filter(){
    vector<int> vec = {1,2,3,4,5,6,7,8};

    // 直接写A1中的写法2
    auto View_vec = vec | views::filter([](int n){
        return n % 2 == 0;
    });

    ranges::for_each(View_vec, [](int n){
        cout << n << ' ';
    });

    return 0;
}

// A3. take & A4. drop & A6.slice
int Adapter_std(){
    vector<int> vec = {1,2,3,4,5,6};

    // slice 可以用 take 和 drop替代
    // auto view_vec = vec | views::slice(1, 5);
    // 等价于删除第一个元素，然后再取 5 - 1 = 4个元素
    auto view_vec = vec | views::drop(1) | views::take(4);

    ranges::for_each(view_vec, [](int n){
        cout << n << ' ';
    });

    return 0;
}

// A4. join (难) - 每使用一次join就降一个维度
int Adapter_join(){
    // 多维条件判断
    vector<vector<int>> vec = {{1,3}, {}, {4,-5}, {-1}, {6, 7}};

    auto view = vec
                | views::filter([](auto v){return !v.empty();})
                | views::join
                | views::filter([](int x){return x > 0;});
    
    // 相当于把第一次过滤的结果用于第二次过滤 

    ranges::for_each(view, [](int n){
        cout << n << ' ';
    });
    // 输出 1 3 4 6 7

    cout << endl;

    // 处理多层嵌套
    vector<vector<vector<int>>> ThreeLevelVec = {
                                                {{1,3},{}},
                                                {{2,3,4},{1},{3}}
                                            };
    auto Anotherview = ThreeLevelVec
           | views::join
           | views::join;

    ranges::for_each(Anotherview, [](int n){
        cout << n << ' ';
    });
    // 输出: 1 3 2 3 4 1 3
    return 0;
}


int main(){
    // Adapter_transform();
    // Adapter_filter();
    Adapter_join();
    return 0;
}

内置算法

参考文献：Constrained algorithms (since C++20)

遇到查阅即可

力扣来源

3000. 对角线最长的矩形的面积 – 力扣（LeetCode）官解的第一个评论

该题需要解决：找到两数 平方和 & 乘积的最大值

// 常规写法
class Solution {
public:
    int areaOfMaxDiagonal(vector<vector<int>>& dimensions) {
        int Maxproduct = 0, MaxPowSum = 0;

        for(const vector<int>& v: dimensions){
            int l = v[0], w = v[1];
            int product = l * w;
            int PowSum = pow(l, 2) + pow(w, 2);
            if(MaxPowSum < PowSum){
                MaxPowSum = PowSum;
                Maxproduct = product;
            } 
            else if(MaxPowSum == PowSum)
                Maxproduct = max(Maxproduct, product);
        } 

        return Maxproduct;
    }
};

使用ranges和pair快速解决问题

#include<ranges>
class Solution {
public:
    int areaOfMaxDiagonal(vector<vector<int>>& dimensions) {
        auto&& v = ranges::max(dimensions, {}, [](auto&& v){
            return pair{pow(v[0], 2) + pow(v[1], 2), v[0] * v[1]};
        }); 
        return v[0] * v[1];   
    }
};

该种写法本质：将所有的dismensions中的数据映射到 pair(平方和， 乘积) 的数组中，然后去取映射数组的最大值，返回对应的dimensions中的数据，消耗的空间为 2n ( n = dimensions.size() )，可以看到其实用传统解法所用的时间相近，但消耗的内存空间要小一点。

源码解读

std::gcd <numeric>

原理：Stein算法 (m, n = n, m % n 的变体)

基于三个事实

• 若 m, n 为偶数， gcd(m, n) = 2 * gcd(m/2, n/2)
• 若m为偶数，n为奇数，gcd(m, n) = gcd(m/2, n)
• 若m, n为奇数， gcd(m, n) = gcd((m – n) /2, n) 假设 m > n

源码如下：

  // GCD implementation, using Stein's algorithm
  template<typename _Tp>
    constexpr _Tp
    __gcd(_Tp __m, _Tp __n)
    {
      static_assert(is_unsigned<_Tp>::value, "type must be unsigned");
      // 0与任何数互质
      if (__m == 0)
	return __n;
      if (__n == 0)
	return __m;
       
      // 移除二进制尾0，将偶数变为奇数
      const int __i = std::__countr_zero(__m);
      __m >>= __i;
      const int __j = std::__countr_zero(__n);
      __n >>= __j;
      
      // 记录两个偶数变为奇数的最小公因数k
      const int __k = __i < __j ? __i : __j; // min(i, j)

      while (true)
	{
         // 基于事实三: 若m, n为奇数， gcd(m, n) = gcd(m, (n - m)/2)  假设 n > m
	  if (__m > __n)
	    {
	      _Tp __tmp = __m;
	      __m = __n;
	      __n = __tmp;
	    }

	  __n -= __m;
          
          // 若 n - m等于0，算法结束，
          // 基于事实一：若 m, n 为偶数， gcd(m, n) = 2 * gcd(m/2, n/2)
	  if (__n == 0)
	    return __m << __k;
         
          // 基于事实二: 若m为偶数，n为奇数，gcd(m, n) = gcd(m/2, n) 确保n为奇数
	  __n >>= std::__countr_zero(__n);
	}
    }
}

算法过程（90， 60）

• step1: m = 90 (0b1011010) – 尾0数为1， n = 60 (0b111100) – 尾0数为2，公共因子数k = 1
• step2: 移除尾0， m -> 45，n->15
• step3: 基于事实三：m = 15，n = 45，gcd(m,n) = gcd(m, (n-m)/2), n = n – m = 30
• step4: 基于事实二：若m为偶数，n为奇数，gcd(m, n) = gcd(m/2, n)：n去除尾0数 n->15
• step5: 循环执行step3, step4
• step6：基于事实一：若 m, n 为偶数， gcd(m, n) = 2 * gcd(m/2, n/2)， 返回（m左移最小公因数k）即为 m和n的最小公约数