记一次 Rust 类型系统的问题解决

发表于 更新于 分类于 阅读次数：

在做 Codeforces Educational Round 169 D Colored Portals 时，需要找到 i 前面距离 i 最近的颜色不完全相同但也不完全不同的 j，我随手写了个

1
2
3
4
5
6
7
8
9
10
11
12
13
const vector<string> type = {"BG", "BR", "BY", "GR", "GY", "RY"};
map<string, int> m;
vector<int> lc(n, -1), rc(n, -1);

for (int i = 0; i < n; i++) {
    auto condi = m | filter([&](const auto &p) { return p.first != in[i] && has_same(p.first, in[i]); });
    if (auto lci = ranges::max_element(
                condi, [](const auto &a, const auto &b) { return a.second < b.second; });
            lci != ranges::end(condi)) {
            lc[i] = lci->second;
    }
    m[in[i]] = i;
}

然后吐槽了下 C++ 没有 .iter().filter() 或者 .iter().map() 这种写法

于是我就建了个 D.rs 写了个 Rust 版本的:

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

fn has_same(a: &[char; 2], b: &[char; 2]) -> bool {
    (a[0] == b[0] || a[0] == b[1]) || (a[1] == b[0] || a[1] == b[1])
}
fn main() {

    let n : usize = 4;
    let inv : Vec<[char; 2]> = vec![['B', 'R'], ['B', 'R'], ['G', 'Y'], ['G', 'R']]; // simple

    let mut map : HashMap<[char; 2], i32> = HashMap::new();
    let mut lc = vec![-1; n];

    for i in 0usize..n {
        if let Some(lci) = map.iter()
            .filter(|(key, _)| *key != &inv[i] && has_same(key, &inv[i]))
            .max_by(|a, b| a.1.cmp(&b.1)) {
            lc[i] = *lci.1;
        }
        map.insert(inv[i].clone(), i as i32);
    }

    println!("{:?}", lc);
}

我不是什么 Rust 高手但至少 rustlings 是写完了，然而上次写 rs 还是三四个月之前了，所以这里的 *key != &inv[i] 一开始写成 *key = inv[i] 了，然后发现了一个有意思的现象：

  • 当我写 key != &inv[i] 时报错 no implement for &[char; 2] ==[char;2]

  • 当我写 key != inv[i] 时报错 no implement for &&[char;2] == [char;2]

这我就有两点疑问：

  1. &inv[i] 不应该是 &[char;2] 吗？为什么这里说他是 [char;2] ?
  2. key 的类型为什么变化了？

有意思的是这个问题能把 4o 或者 r1 全爆了，前者胡言乱语后者卡在深度思考的逻辑链里出不来，当然这里 4o 应该是 OpenAI 为了卖 o1 强行降智了

我回想了一下引用那一节(其实是根本没想起来什么直接翻书去了)发现有个自动解引用和自动借用机制存在，简单说就是引用比较引用自动解引用，需要引用的地方可以自动引用

于是就有了以下可以解释通的说法：

  • 对于key != &inv[i] 时两边分别为 &&[char; 2] != &[char; 2]， 同时自动解引用就是 &[char; 2] != [char; 2]，根据报错误以为 key 是 &[char; 2] 而 &inv[i] 是 [char; 2] 了
  • 对于key != inv[i] 时两边分别为 &&[char; 2] 和 [char; 2]

这就很 make sense 了，但还有一个问题可以思考，key 的 &&[char; 2] 类型是怎么来的？

ChatGPT 4o 做出了错误的回答:

如下解释是错误的！！！

好的，我明白了你在问什么。

当你执行 map.iter().next() 时，返回的类型是 Option<(&K, &V)>，而不是 Option<&(&K, &V)>。这看起来有些反直觉，但实际上是因为 map.iter() 本身已经返回了每个元素的引用，而 .next() 返回的是引用的元素本身，而不是引用的引用。 解释：

  1. map.iter() 返回 &(&K, &V)： map.iter() 返回的是 HashMap 中元素的 引用，也就是 &(&K, &V)，这意味着你得到了对 HashMap 中每个二元组 (K, V) 的引用。

    其中 &K 是对键 K 的引用。 &V 是对值 V 的引用。

    所以 map.iter() 迭代的每一项类型是 (&K, &V)，但是由于这些是对元素的引用，所以整个类型是 &(&K, &V)，即 HashMap 中元素的 引用。

  2. .next() 返回的是 Option<(&K, &V)>： .next() 是对 map.iter() 返回的迭代器的调用，它会返回迭代器中的下一个元素。

    在这种情况下，map.iter() 本身返回的是每个元素的引用，而 next() 直接返回这些元素的引用，因此返回类型是 Option<(&K, &V)>，这就是迭代器的下一项是对元素的引用。

    可以理解为 next() 相当于解了一层引用。

当你调用 map.iter() 时，它返回的是 &(&K, &V)，也就是对二元组的引用，且这个二元组本身已经包含了对键和值的引用。所以，next() 方法直接返回这个引用，并解开了一个层级，即返回了 Option<(&K, &V)>，而不是 Option<&(&K, &V)>。

总结起来：

  • map.iter() 返回的是对 (K, V) 元素的引用，即 &(&K, &V)。

  • .next() 解开了这层引用，直接返回了 Option<(&K, &V)>。

这样就可以避免不必要的引用，简化了类型。

如果我到这就信了就完了，事实上对于你无法验证答案真伪的问题不要问大模型，这里只是希望它提供一点灵感思路。

我查看 Rust 文档发现 .iter() 的例子中，普通数组的 .iter().next() 实际上是 Option<&T> 即 Some(&T) 或 None，也就是说并不存在 “next 解了一层引用” 之类的说法（但它其实有一部分说的是对的，AI 就是这样半真半假不能全信），此时它还在狡辩说只有 HashMap 的 next 会解引用。

估计出幻觉了，于是在编辑器中写以下代码：

1
2
3
4
5
6
7
8
9
10
use std::collections::HashMap;
fn main() {
    let map = HashMap::<i32, i32>::new();
    let vecs = Vec::<(i32, i32)>::new();
    let arr = [1, 2, 3];

    let _map_iter = map.iter().next();
    let _vecs_iter = vecs.iter().next();
    let _arr_iter = arr.iter().next();
}

按 Shift + K (即 neovim 的 K ) 借用 rust-analyzer LSP 查看类型，分别是：

  1. Option<(&i32, &i32)>

  2. Option<&(i32, i32)>

  3. Option<&i32>

这里我们知道：

  • Rust 的迭代器实际上是容器元素的引用而不是值，出于效率等目的。

  • Vec 的情况符合我们的预期，即迭代器是对容器里某个元素整体的引用

再次翻阅 HashMap 的文档，发现 .iter() 的返回值类型是 Iter<K, V> 而 Iter 中有一个 Item 是 (&K, &V) ， 那么也就破案了 HashMap 迭代器的类型

但回到最初的问题发现还是对不上，为什么 key 是对引用的引用？

仔细思考发现这里我忽略了filter 参数里的闭包的参数本身就是对迭代器中 Item 的引用\(^{[1]}\)。所以最前面那个对二元组的引用其实是闭包里出现的对迭代器的引用，但是迭代器本身又是对元素（包含两个引用的二元组）的引用，所以这里是对引用的引用。模式匹配后 key 继承了这两层引用：一层是对迭代器的，一层是迭代器对元素的。

\([1]:\) 以下是 filter 的定义:

1
2
3
4
5
6
7
fn filter<P>(self, predicate: P) -> Filter<Self, P>
where
    Self: Sized,
    P: FnMut(&Self::Item) -> bool,
{
    Filter::new(self, predicate)
}

可以看到 FnMut 的参数是对一个 Self::Item 的引用。