C++函数式编程与Rust对比

在刷leetcode的时候，想使用c++20的范围库，体验一下函数式编程的快乐。这一题是leetcode 300题。

300. Longest Increasing Subsequence
Given an integer array nums, return the length of the longest strictly increasing subsequence

Example 1:

Input: nums = [10,9,2,5,3,7,101,18]
Output: 4
Explanation: The longest increasing subsequence is [2,3,7,101], therefore the length is 4.

Example 2:

Input: nums = [0,1,0,3,2,3]
Output: 4

Example 3:

Input: nums = [7,7,7,7,7,7,7]
Output: 1

有两种思路来做，现在用动态规划的方法实现：
dp[i]是以nums[i]结尾的最长递增子序列的长度，注意必须是以nums[i]结尾，那么递归公式是

1

dp[i] = max(dp[j]) + 1 if nums[i] > nums[j] and i > j

在c++中，为了获取索引，使用了C++23的enumerate。

1
2
3
4
5
6
7
8


@startuml
state dp
dp -> dp1 : take i
dp1 -> dp2 : enumerate
dp2 -> dp3 : filter nums[i] > nums[j]
dp3 -> dp4 : values
dp4 -> max : max_element
@enduml

code如下：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24


#include <vector>
#include <algorithm>
#include <ranges>

using namespace std;
class Solution300 {
public:
    int lengthOfLIS(vector<int>& nums) {
        int sz = nums.size();
        // dp: LIS size of end with nums[i]
        vector<int> dp(sz, 0);
        dp[0] = 1;
        for (int i = 1; i < sz; ++i) {
	        // views::enumerate and views::values need c++23
            auto v = dp
	            | views::take(i)
	            | views::enumerate
                | views::filter([&](auto item) {return nums[get<0>(item)] < nums[i];})
                | views::values;
            dp[i] = v.empty() ? 1 : *ranges::max_element(v) + 1;
        }
        return *ranges::max_element(dp);
    }
};

其中对于max_element，本想直接写成

1
2
3


dp[i] = *ranges::max_element(dp | views::take(i) | views::enumerate
                | views::filter([&](auto item) {return nums[get<0>(item)] < nums[i];})
                | views::values) + 1;

然而有编译器报错

1
2
3
4
5


error: no match for 'operator*' (operand type is 'std::ranges::borrowed_iterator_t<std::ranges::filter_view<std::ranges::take_view<std::ranges::ref_view<std::vector<int> > >, Solution300::lengthOfLIS(std::vector<int>&)::<lambda(int)> > >')
   70 |             *ranges::max_element(dp | views::take(i)
      |             ^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
   71 |                 | views::filter([&](int x) {return x < nums[i];}));
      |                 ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

错误显示该类型std::ranges::borrowed_iterator_t是不能解引用的。
从cppreference网站上查询像std::ranges::max_element， std::ranges::lower_bound这一类的算法返回的都是std::ranges::borrowed_iterator_t类型。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11


template< ranges::range R >
using borrowed_iterator_t = /* see below */;
若 R 实现 borrowed_range 则为 std::ranges::iterator_t<R> ，否则为 std::ranges::dangling 。
某些受约束算法用此二模板别名避免返回潜在悬垂的迭代器或视图。

template<class R>
concept borrowed_range =
    ranges::range<R> &&
    (std::is_lvalue_reference_v<R> ||
     ranges::enable_borrowed_range<std::remove_cvref_t<R>>);
概念 borrowed_range 定义范围的要求，使得函数能按值接收它，并返回从它获得的迭代器，而无悬垂之虞。

所以应该是生成的views类似于右值，其迭代器会悬垂失效，如果将它赋给左值，那么max_element返回的迭代器就可以使用了。

1
2


auto v = ...
dp[i] = v.empty() ? 1 : *ranges::max_element(v) + 1;

这里还有一个问题，max_element在Range为空时，返回的是rangs::begin(r)。想在一行写完，这点逻辑也不好表示。
因此C++的函数式编程在最后消费迭代器的时候，写法不是很便利。
在Rust中，相似的写法是

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16


impl Solution {
    pub fn length_of_lis(nums: Vec<i32>) -> i32 {
        let sz = nums.len();
        let mut dp: Vec<i32> = vec![0; sz];
        for (i, n) in nums.iter().enumerate() {
            dp[i] = *dp.iter()
                       .take(i)
                       .enumerate()
                       .filter(|(j, _)| nums[*j] < *n)
                       .map(|(_, v)| v)
                       .max()
                       .unwrap_or(&0) + 1;
        }
        *dp.iter().max().unwrap();
    }
}

Rust中迭代器的fp风格就比较自然，最后消费迭代器的max方法，也是能返回Option(T)，可以直接处理容器为空的情况了。
更进一步，如果不想两次循环dp的话，希望直接在第一次给dp赋值时，直接求出最大值，但是这样写显然会遭遇了闭包捕获不可变引用与已有可变引用冲突的问题：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19


impl Solution {
    pub fn length_of_lis(nums: Vec<i32>) -> i32 {
        let sz = nums.len();
        let mut dp: Vec<i32> = vec![0; sz];
        *dp.iter_mut()
	        .enumerate()
	        .map(|(i, v)|{
	            *v = *dp.iter()
                       .take(i)
                       .enumerate()
                       .filter(|(j, _)| nums[*j] < nums[i])
                       .map(|(_, v)| v)
                       .max()
                       .unwrap_or(&0) + 1;
	            v})
	            .max()
	            .unwrap()
	}
}

可见对这个问题，两个语言写法都挺奇怪的。但是Rust明显对函数式编程的支持更好。然而也可以看到现在的编程语言相互融合，越来越像。除了C。

回到这个问题，还有另一种方法，新建一个subseq的vector。对于每个num，如果大于subseq最后的元素，则放入subseq。否则找到subseq中第一个大于等于num的位置，替换为num。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19


class Solution {
public:
    int lengthOfLIS(vector<int>& nums) {
        int max = 1;
        int sz = nums.size();
        vector<int> subsq;
        for (int i = 0; i < sz; ++i) {
            if (subsq.empty() or nums[i] > subsq.back()) {
                subsq.push_back(nums[i]);
            } else {
                auto it = lower_bound(subsq.begin(), subsq.end(), nums[i]);
                if (it != subsq.end()) {
                    *it = nums[i];
                }
            }
        }
        return subsq.size();
    }
};

Contents