其它

1 turbofish

表达式中带有泛型参数的路径必须在左尖括号前加上一个::。 这种为表达泛型而结合起来形式::<>看起来有些像一条鱼，因此被称为turbofish。本节详细介绍它的使用。

在消费适配器与迭代器适配器中，介绍了这样的例子

例1：

1
2
3
4
5
6
7
fn main() {
    let v1: Vec<i32> = vec![1, 2, 3];

    let v2: Vec<_> = v1.iter().map(|x| x + 1).collect();

    assert_eq!(v2, vec![2, 3, 4]);
}

我们在这里显式指定了类型Vec<_>，是为了告诉编译器我们想要收集的集合类型为动态数组。尝试去掉类型标注看看会发生什么

例2：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
fn main() {
    let v1: Vec<i32> = vec![1, 2, 3];

    let v2 = v1.iter().map(|x| x + 1).collect();

    assert_eq!(v2, vec![2, 3, 4]);
}
/*
error[E0282]: type annotations needed
 --> src\main.rs:4:9
  |
4 |     let v2 = v1.iter().map(|x| x + 1).collect();
  |         ^^
  |
help: consider giving `v2` an explicit type
  |
4 |     let v2: _ = v1.iter().map(|x| x + 1).collect();
  |           +++
*/

这条消息的意思是，collect不知道你试图将迭代器收集为什么类型。它不知道是Vec，HashMap，HashSet还是任何实现了 FromIterator的类型。

这可以通过两种不同的方式解决。

  • 通过在声明变量时声明v2的类型

    • 直接显式声明

      1
      let v2: Vec<i32> = v1.iter().map(|x| x + 1).collect();

    • 交给编译器推断：<_>，就是例1使用的方法

      1
      let v2: Vec<_> = v1.iter().map(|x| x + 1).collect();

  • 使用turbofish语法，在这个例子中，就像这样：collect::<>

    • 直接显式声明

      1
      let v2 = v1.iter().map(|x| x + 1).collect::<Vec<i32>>();

    • 交给编译器推断：<_>

      1
      let v2 = v1.iter().map(|x| x + 1).collect::<Vec<_>>();

::<Vec<i32>>部分就是turbofish，意思是将这个迭代器收集到Vec<i32>。

那么，在什么情况下需要使用turbofish？来看另外一个例子

例3：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
fn main() {
    let s = "Hello, World!";
    let string = s.into();
}
/*
error[E0282]: type annotations needed
 --> src\main.rs:3:9
  |
3 |     let string = s.into();
  |         ^^^^^^
  |
help: consider giving `string` an explicit type
  |
3 |     let string: _ = s.into();
  |               +++
*/

尝试使用turbofish可以解决这个问题：

1
2
3
4
5
6
7
8
9
10
11
12
13
fn main() {
    let s = "Hello, World!";
    let string = s.into::<String>();
}
/*
error[E0107]: this associated function takes 0 generic arguments but 1 generic argument was supplied
   --> src\main.rs:3:20
    |
3   |     let string = s.into::<String>();
    |                    ^^^^ expected 0 generic arguments
    |
note: associated function defined here, with 0 generic parameters
*/

然而报了一个新的错误this associated function takes 0 generic arguments but 1 generic argument was supplied，为什么::<>可以作用于 collect但是不能作用于 into？答案就在这两个函数的类型签名中。

info的签名如下：

1
fn into(self) -> T;

collect的签名如下：

1
fn collect<B: FromIterator<Self::Item>>(self) -> B;

可以看出，collect 拥有一个泛型参数B，而into没有。这就是为什么前者可以使用turbofish语法，而后者不可以。

以此类推，如果一个函数签名是foo<A, B, C>，那么你就可以使用foo::<i32, i64, u32>()这种形式调用它：

1
2
3
4
5
fn foo<A, B, C>() {}

fn main() {
    foo::<i32, u32, i64>();
}

turbofish可以用于拥有泛型参数的东西，比如泛型结构体和泛型特征等，比如结构体定义为struct SomeStruct<T> { ... }，则可以使用 SomeStruct::<String>::some_method()方式调用其中的方法。

例4：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
struct foo<T> {
    a: T,
}

impl<T> foo<T> {
    fn test(&self, v: T) -> T {
        v
    }
}
fn main() {
    let t = foo { a: 3 };
    // SomeStruct::<sometype>::some_method()
    foo::<i32>::test(&t, 3);
}

因此，例3中的问题可以这样解决：

1
2
3
4
fn main() {
    let s = "Hello, World!";
    let string:String = s.into();
}

当然，其实还有一种万能的方式来解决这些问题，就是使用完全限定语法。

1
2
3
4
5
fn main() {
    let s = "Hello, World!";
    // <Type as Trait>::function(receiver_if_method, next_arg, ...);
    let string = <&str as Into<String>>::into(&s);
}

或者仍然通过turbofish，只不过是针对特征Into的turbofish：

1
2
3
4
fn main() {
    let s = "Hello, World!";
    let string = Into::<String>::into(s);
}

介绍一些turbofish的趣闻。

turbofish这个词的起源最早可追溯于reddit上的这篇文章，作者是@deadstone，在同一天，在twitter上发布的一篇推文也出现了turbofish这个词，作者是@Anna Harren，经过证实，他们是同一个人。

曾经，不止一人都在质疑turbofish的必要性，比如这个PR想要去掉turbofish中的双冒号::，并给出了示例：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
struct Nooper<T>(T);

impl<T> Nooper<T> {
    fn noop<U>(&self, _: U) {}
}

fn id<T>(t: T) -> T {
    t
}

fn main() {
    id<u32>(0u32); // ok
    let n = Nooper<&str>(":)"); // ok
    n.noop<()>(()); // ok
}

看起来是可行的，但是在这个PR下的一个评论给出了反例：

如果一个语句是这样的：

1
let a = (b<c, d>(e));

那么它既可以看成元组：

1
let a = ((b < c), (d > e));

也可以看成是两个泛型参数：

1
let a = b::<c, d>(e);

因此::暂时是不可去掉的，因为会导致歧义。

为此，在rust官方仓库中也专门介绍了不使用::所导致的歧义的例子，见bastion-of-the-turbofish：

1
2
3
4
fn main() {
    let (the, guardian, stands, resolute) = ("the", "Turbofish", "remains", "undefeated");
    let _: (bool, bool) = (the<guardian, stands>(resolute));
}

文件的标题叫做bastion-of-the-turbofish.rs，翻译过来就是“Turbofish的堡垒”，文件中还写了一大段对turbofish的一种夸张描述，将其描述为一只可怕的怪兽，掌控着所有rust程序员的命运。它说，在这个领域里，任何试图反对turbofish的人都将遭受它的愤怒和毁灭。这段文本还提到了创造turbofish这个词的人@Anna Harren，并将这里称为turbofish的堡垒。

2 leetcode中复杂数据结构的定义

我们在如何实现链表中介绍了链表的实现，下面来看看leetcode中是如何定义链表和树结构的，只有搞清楚定义才可以更方便地刷题。

2.1 链表结构定义

随便打开一道关于链表的题目，比如206. 反转链表，可以看到这样的定义：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
#[derive(PartialEq, Eq, Clone, Debug)]
pub struct ListNode {
  pub val: i32,
  pub next: Option<Box<ListNode>>
}

impl ListNode {
  #[inline]
  fn new(val: i32) -> Self {
    ListNode {
      next: None,
      val
    }
  }
}

题目本身很简单，我们主要关注节点的定义。这是一个很简单的定义，但它只实现了new。这很不方便，我们可以参考还可以的栈实现中的方法，为其添加类似push和pop的方法。这里直接给出解答：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
struct Solution;
// Definition for singly-linked list.
#[derive(PartialEq, Eq, Clone, Debug)]
pub struct ListNode {
    pub val: i32,
    pub next: Option<Box<ListNode>>,
}

impl ListNode {
    #[inline]
    fn new(val: i32) -> Self {
        ListNode { next: None, val }
    }
}

impl Solution {
    pub fn reverse_list(mut head: Option<Box<ListNode>>) -> Option<Box<ListNode>> {
        let mut ans = head.take().map(|node| {
            head = node.next;
            Box::new(ListNode {
                val: node.val,
                next: None,
            })
        });
        while let Some(node) = head.take() {
            head = node.next;
            let new_node = Box::new(ListNode {
                val: node.val,
                next: ans.take(),
            });
            ans = Some(new_node)
        }

        ans
    }
}

fn main() {
    let mut head = Some(Box::new(ListNode::new(4)));
    println!("{:?}", head);
    let arr = vec![3, 2, 4, 1];
    for val in arr {
        let new_node = Box::new(ListNode {
            val: val,
            next: head.take(),
        });
        head = Some(new_node);
    }
    println!("{:?}", head);
    let result = Solution::reverse_list(head);
    println!("{:?}", result);
}

可以看到，要想玩转这种定义下的链表，take和map方法是必须要熟练掌握的。

2.2 树结构定义

再来看看树结构定义：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
#[derive(Debug, PartialEq, Eq)]
pub struct TreeNode {
  pub val: i32,
  pub left: Option<Rc<RefCell<TreeNode>>>,
  pub right: Option<Rc<RefCell<TreeNode>>>,
}

impl TreeNode {
  #[inline]
  pub fn new(val: i32) -> Self {
    TreeNode {
      val,
      left: None,
      right: None
    }
  }
}

可真是复杂。我们在一个糟糕但安全的双端队列介绍过使用内部可变性的数据布局，这里的树结构也是同样的道理。不过，leetcode同样只为我们实现了new。

因此，需要熟悉borrow、borrow_mut等操作才可以无痛刷题。以144. 二叉树的前序遍历为例，直接给出解答，主要关注如何操作这个数据结构：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
struct Solution;
#[derive(Debug, PartialEq, Eq)]
pub struct TreeNode {
    pub val: i32,
    pub left: Option<Rc<RefCell<TreeNode>>>,
    pub right: Option<Rc<RefCell<TreeNode>>>,
}

impl TreeNode {
    #[inline]
    pub fn new(val: i32) -> Self {
        TreeNode {
            val,
            left: None,
            right: None,
        }
    }
}
use std::cell::RefCell;
use std::rc::Rc;
impl Solution {
    fn preorder(node: &Option<Rc<RefCell<TreeNode>>>, mut ans: Vec<i32>) -> Vec<i32> {
        match node {
            Some(n) => {
                ans.push(n.borrow().val);
                ans = Self::preorder(&n.borrow().left, ans);
                Self::preorder(&n.borrow().right, ans)
            }
            None => ans,
        }
    }

    pub fn preorder_traversal(root: Option<Rc<RefCell<TreeNode>>>) -> Vec<i32> {
        let ans = Vec::new();
        Self::preorder(&root, ans)
    }
}
fn main() {
    let tree = Some(Rc::new(RefCell::new(TreeNode::new(4))));
    let left = Some(Rc::new(RefCell::new(TreeNode::new(6))));
    let right = Some(Rc::new(RefCell::new(TreeNode::new(6))));

    let tree = tree.unwrap();
    tree.borrow_mut().left = left;
    tree.borrow_mut().right = right;
    let tree = Some(tree);
    println!("{:?}", tree);
    let result = Solution::preorder_traversal(tree);
    println!("{:?}", result);
}