3.2 基本操作
原文链接: https://rust-unofficial.github.io/too-many-lists/third-basics.html
我们已经懂不少 Rust 基础了，很多简单的事可以再来一遍。
构造函数又可以复制粘贴：
1
2
3
4
5
| impl<T> List<T> {
pub fn new() -> Self {
List { head: None }
}
}
|
push 和 pop 不再合适。可以提供 prepend 和 tail，大致提供类似功能。
从 prepend 开始。它接受链表和一个元素，返回新 List。和可变链表一样，要建新节点，把旧链表作为 next。新之处在于如何得到那个 next，因为我们不能修改任何东西。
答案是 Clone trait。几乎所有类型都实现了 Clone，在只有共享引用时提供通用的「再来一个逻辑上独立的」方式。像 C++ 的拷贝构造函数，但绝不会隐式调用。
Rc 特别用 Clone 来增加引用计数。所以不是把 Box 移到子链表，而是 clone 旧链表的头。甚至不必 match head，因为 Option 的 Clone 实现正好是我们想要的。
试试看：
1
2
3
4
5
6
| pub fn prepend(&self, elem: T) -> List<T> {
List { head: Some(Rc::new(Node {
elem: elem,
next: self.head.clone(),
}))}
}
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
| > cargo build
warning: field is never used: `elem`
--> src/third.rs:10:5
|
10 | elem: T,
| ^^^^^^^
|
= note: #[warn(dead_code)] on by default
warning: field is never used: `next`
--> src/third.rs:11:5
|
11 | next: Link<T>,
| ^^^^^^^^^^^^^
|
哇，Rust 对「真的用到字段」要求真严。它能判断没有任何消费者能观察到这些字段的使用！不过目前看起来还行。
tail 是这个操作的逻辑逆操作。接受链表，返回去掉首元素后的整条链表。就是 clone 链表中第二个元素（如果存在）。试试：
1
2
3
| pub fn tail(&self) -> List<T> {
List { head: self.head.as_ref().map(|node| node.next.clone()) }
}
|
1
2
3
4
5
6
7
8
9
10
| cargo build
error[E0308]: mismatched types
--> src/third.rs:27:22
|
27 | List { head: self.head.as_ref().map(|node| node.next.clone()) }
| ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ expected struct `std::rc::Rc`, found enum `std::option::Option`
|
= note: expected type `std::option::Option<std::rc::Rc<_>>`
found type `std::option::Option<std::option::Option<std::rc::Rc<_>>>`
|
嗯，搞砸了。map 期望我们返回 Y，这里却返回 Option<Y>。好在这又是常见的 Option 模式，用 and_then 让我们能返回 Option。
1
2
3
| pub fn tail(&self) -> List<T> {
List { head: self.head.as_ref().and_then(|node| node.next.clone()) }
}
|
很好。
有了 tail，大概也该提供 head，返回首元素的引用。就是可变链表的 peek：
1
2
3
| pub fn head(&self) -> Option<&T> {
self.head.as_ref().map(|node| &node.elem)
}
|
不错。
功能够测试了：
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
| #[cfg(test)]
mod test {
use super::List;
#[test]
fn basics() {
let list = List::new();
assert_eq!(list.head(), None);
let list = list.prepend(1).prepend(2).prepend(3);
assert_eq!(list.head(), Some(&3));
let list = list.tail();
assert_eq!(list.head(), Some(&2));
let list = list.tail();
assert_eq!(list.head(), Some(&1));
let list = list.tail();
assert_eq!(list.head(), None);
// 确保空 tail 也能工作
let list = list.tail();
assert_eq!(list.head(), None);
}
}
|
1
2
3
4
5
6
7
8
9
10
11
12
| > cargo test
Running target/debug/lists-5c71138492ad4b4a
running 5 tests
test first::test::basics ... ok
test second::test::into_iter ... ok
test second::test::basics ... ok
test second::test::iter ... ok
test third::test::basics ... ok
test result: ok. 5 passed; 0 failed; 0 ignored; 0 measured
|
完美！
Iter 也和可变链表一模一样：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
| pub struct Iter<'a, T> {
next: Option<&'a Node<T>>,
}
impl<T> List<T> {
pub fn iter(&self) -> Iter<'_, T> {
Iter { next: self.head.as_deref() }
}
}
impl<'a, T> Iterator for Iter<'a, T> {
type Item = &'a T;
fn next(&mut self) -> Option<Self::Item> {
self.next.map(|node| {
self.next = node.next.as_deref();
&node.elem
})
}
}
|
1
2
3
4
5
6
7
8
9
| #[test]
fn iter() {
let list = List::new().prepend(1).prepend(2).prepend(3);
let mut iter = list.iter();
assert_eq!(iter.next(), Some(&3));
assert_eq!(iter.next(), Some(&2));
assert_eq!(iter.next(), Some(&1));
}
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
| cargo test
Running target/debug/lists-5c71138492ad4b4a
running 7 tests
test first::test::basics ... ok
test second::test::basics ... ok
test second::test::iter ... ok
test second::test::into_iter ... ok
test second::test::peek ... ok
test third::test::basics ... ok
test third::test::iter ... ok
test result: ok. 6 passed; 0 failed; 0 ignored; 0 measured
|
谁说动态类型更简单？
（是菜鸟说的）
注意我们不能为这个类型实现 IntoIter 或 IterMut。我们对元素只有共享访问。