前言#
昨天我们实现了一个有瑕疵的单栈链表，今天我们来优化下
一个还行的单链栈#
我们刚搞了一个很小的链表，但是从头到尾一直有一种变扭的妥协，现在我们来优化下，绝不妥协！天王老子来了也不行！（难说）
接下来的流程：
- 造轮子
- 支持泛型，目前仅支持
- 支持数据查看(
peeking) - 让我们的链表可以迭代（难点）
在这个过程中，我们将对下面的知识有些许深入理解：
Option<T>的使用- 泛型
- 生命周期
- 迭代器
如果你对上面的四种知识存在至少一种不了解或者感到陌生，请出门左拐：rust基础学习--final: 章节索引 - 知乎 (zhihu.com)。
然后我们新建一个second.rs文件并将它添加到lib.rs中。
使用Option<T>#
回到我们之前设计的链表结构：
enum Link {
Empty,
More(Box<Node>)
}前面我们说过了，空和非空实际上可以变成有和没有。没有我们直接用None表示即可。
所以我们第一步先把可以用Option<T>替换的都给替换了，甭管好不好，不好再优化嘛。
use std::mem;
pub struct List {
head: Link,
}
// yay type aliases!
type Link = Option<Box<Node>>;
struct Node {
elem: i32,
next: Link,
}
impl List {
pub fn new() -> Self {
List { head: None }
}
pub fn push(&mut self, elem: i32) {
let new_node = Box::new(Node {
elem: elem,
next: mem::replace(&mut self.head, None),
});
self.head = Some(new_node);
}
pub fn pop(&mut self) -> Option<i32> {
match mem::replace(&mut self.head, None) {
None => None,
Some(node) => {
self.head = node.next;
Some(node.elem)
}
}
}
}
impl Drop for List {
fn drop(&mut self) {
let mut cur_link = mem::replace(&mut self.head, None);
while let Some(mut boxed_node) = cur_link {
cur_link = mem::replace(&mut boxed_node.next, None);
}
}
}
其实也没多大变化，只是少了一些违和感。
接下来我们来用Option<T>提供给我们的一些方法处理掉另外一些变扭的地方：mem::replace，早看它不爽了！
我们这里有俩法宝可以替代mem::replace：
take：它相当于replace(None)，也就是将Some里的数据拿出来，往里塞入一个None。insert：有拿自然就有放，将数据塞入Some里面（注意，当且只当insert的对象是None，如果原来就有数据则无效）
不过目前我们只需要用到take，我们来替换掉mem::replace。
pub struct List {
head: Link,
}
type Link = Option<Box<Node>>;
struct Node {
elem: i32,
next: Link,
}
impl List {
pub fn new() -> Self {
List { head: None }
}
pub fn push(&mut self, elem: i32) {
let new_node = Box::new(Node {
elem: elem,
next: self.head.take(),
});
self.head = Some(new_node);
}
pub fn pop(&mut self) -> Option<i32> {
match self.head.take() {
None => None,
Some(node) => {
self.head = node.next;
Some(node.elem)
}
}
}
}
impl Drop for List {
fn drop(&mut self) {
let mut cur_link = self.head.take();
while let Some(mut boxed_node) = cur_link {
cur_link = boxed_node.next.take();
}
}
}
虽然差不多，但变扭感有所下降，用了Option<T>，自然要用它的api才对胃。
其中pop的那块代码还可以简化：
match self.head.take() {
None => None,
Some(node) => {
self.head = node.next;
Some(node.elem)
}
}这段代码其实可以用map来实现，简单的说就是可以帮你Option<T>变成Option<U>，看个例子：
let maybe_some_string = Some(String::from("Hello, World!"));
// `Option::map` takes self *by value*, consuming `maybe_some_string`
let maybe_some_len = maybe_some_string.map(|s| s.len());
assert_eq!(maybe_some_len, Some(13));
let x: Option<&str> = None;
assert_eq!(x.map(|s| s.len()), None);那我们这块代码也可以改成
self.head.take().map(|node| {
self.head = node.next;
node.elem
})ok，一阶段我们使用Option<T>替换掉所有变扭的方法和结构，接下来我们来继续优化下我们的代码
泛型#
现在我们的链表只支持i32类型的，我们来让它通用一点。得益于Box的特性，我们的数据都是在堆上的，所以可以很舒服的实现泛型。
pub struct List<T> {
head: Link<T>,
}
type Link<T> = Option<Box<Node<T>>>;
struct Node<T> {
elem: T,
next: Link<T>,
}然后再来调整下impl部分
impl<T> List<T> {
pub fn new() -> Self {
List { head: None }
}
pub fn push(&mut self, elem: T) {
let new_node = Box::new(Node {
elem: elem,
next: self.head.take(),
});
self.head = Some(new_node);
}
pub fn pop(&mut self) -> Option<T> {
self.head.take().map(|node| {
self.head = node.next;
node.elem
})
}
}
impl<T> Drop for List<T> {
fn drop(&mut self) {
let mut cur_link = self.head.take();
while let Some(mut boxed_node) = cur_link {
cur_link = boxed_node.next.take();
}
}
}很基础，就不多说了。
peek（瞥一眼）#
我们目前只能通过pop拿到node保存的数据，但很多时候我们只是想看下数据，拿出来对比，并不想改动链表，这个时候pop就不行了，所以我们需要设计一个方法来获取数据。
不过需要注意，我们只是返回引用，不能直接拿出来。
你第一想法可能是下面这样：
pub fn peek(&self) -> Option<&T> {
self.head.map(|node| {
&node.elem
})
}但是你的第二想法应该就会立刻把它否定，或者你的编译器帮你否定。
我们前面看过map的代码，它会直接把原来的数据也就是head拿出来，而不是take出来，这对于&self来说是不可饶恕的。
> cargo build
error[E0515]: cannot return reference to local data `node.elem`
--> src/second.rs:37:13
|
37 | &node.elem
| ^^^^^^^^^^ returns a reference to data owned by the current function
error[E0507]: cannot move out of borrowed content
--> src/second.rs:36:9
|
36 | self.head.map(|node| {
| ^^^^^^^^^ cannot move out of borrowed content我们只是想要一个引用，所以这个时候我们可以使用as_ref拿到head的引用。
pub fn peek(&self) -> Option<&T> {
self.head.as_ref().map(|node| {
&node.elem
})
}这样就行了，因为这里的|node|变成引用类型&Box<Node<T>>，所以不用担心所有权问题了。
或者as_mut，这货一样会返回Option<&T>，不过是&mut T。
pub fn peek_mut(&mut self) -> Option<&mut T> {
self.head.as_mut().map(|node| {
&mut node.elem
})
}这俩在刷链表的算法题中非常常见。
然后我们来搞点测试用例：
#[test]
fn peek() {
let mut list = List::new();
assert_eq!(list.peek(), None);
assert_eq!(list.peek_mut(), None);
list.push(1); list.push(2); list.push(3);
assert_eq!(list.peek(), Some(&3));
assert_eq!(list.peek_mut(), Some(&mut 3));
list.peek_mut().map(|&mut value| {
value = 42
});
assert_eq!(list.peek(), Some(&42));
assert_eq!(list.pop(), Some(42));
}但是这个测试用例遇到了问题，无法过编译：
> cargo test
error[E0384]: cannot assign twice to immutable variable `value`
--> src/second.rs:100:13
|
99 | list.peek_mut().map(|&mut value| {
| -----
| |
| first assignment to `value`
| help: make this binding mutable: `mut value`
100 | value = 42
| ^^^^^^^^^^ cannot assign twice to immutable variable ^~~~~我们明明在map中声明了|&mut value|了，为啥还是不能修改？
实际上这是个误区：闭包的参数是一个模式匹配，也就是说它会匹配符合&mut value的模式，那么value就是i32，整体组成一个&mut i32，我们自然是不能修改i32的，因为它immutable！。
ok，了解了这个误区之后，我们回到代码中，现在我们移除&mut就行了，这就代表着这是个可以修改的i32引用。
不过我们还是不能直接value = 42，为什么呢？因为这是个可变引用，直接修改的修改的只是指针，我们需要修改的是指针指向的那个空间的数据，这个时候我们就可以使用deref，也就是解引用，直接指向内存空间
根据我们之前学到的知识，我们直接使用*就好啦。
#[test]
fn peek() {
let mut list = List::new();
assert_eq!(list.peek(), None);
assert_eq!(list.peek_mut(), None);
list.push(1); list.push(2); list.push(3);
assert_eq!(list.peek(), Some(&3));
assert_eq!(list.peek_mut(), Some(&mut 3));
list.peek_mut().map(|value| {
*value = 42
});
assert_eq!(list.peek(), Some(&42));
assert_eq!(list.pop(), Some(42));
}
这样就没问题了。
intoIter#
从这里开始，复杂度上升！
迭代器是必要的，虽然链表在索引这块没有优势，但是我们还是不可避免的会用到，总不能每次都在pop吧。。。
要实现迭代的功能，我们需要给我们的List实现[Iterator](Iterator in std::iter - Rust (rust-lang.org))这个trait。
pub trait Iterator {
type Item;
fn next(&mut self) -> Option<Self::Item>;
}其中[Item](Iterator in std::iter - Rust (rust-lang.org))是我们迭代器中项的类型，我们一般称它们为关联类型(associated type)，可自定义，写法为type Item = xxx(比如i32)。
这么做的好处是我们只需要写一处类型声明，其它地方全都是默认的Self::Item即可。
[next](Iterator in std::iter - Rust (rust-lang.org))是实现Iterator必须实现的方法，它定义了如何返回一个项。
不过这里有个问题，我们不仅仅需要实现T（IntoIter）一种类型，我们还需要&T（Iter）和&mut T（IterMut）。
我们先来实现IntoIter的，其实我们已经实现了类似next的方法，那就是pop，所以我们直接在里面使用pop即可。
// Tuple structs are an alternative form of struct,
// useful for trivial wrappers around other types.
pub struct IntoIter<T>(List<T>);
impl<T> List<T> {
pub fn into_iter(self) -> IntoIter<T> {
IntoIter(self)
}
}
impl<T> Iterator for IntoIter<T> {
type Item = T;
fn next(&mut self) -> Option<Self::Item> {
// access fields of a tuple struct numerically
self.0.pop()
}
}简单的说下这里面的几个点：
- 我们定义了一个
tuple struct也就是元组结构体，作用是给List<T>实现Iterator - 我们的
List<T>实现一个into_iter的方法，用来返回一个迭代对象。
你可能会疑惑：为什么要绕一圈，不直接给List<T>实现Iterator？
因为**List<T>不能自身就是迭代器！**
我们不能让它自己本身就是迭代器，这是一种越界。这算是一种规范。
但最主要的是我们还得实现Iter和IterMut（笑）
然后我们来搞几个测试用例：
#[test]
fn into_iter() {
let mut list = List::new();
list.push(1); list.push(2); list.push(3);
let mut iter = list.into_iter();
assert_eq!(iter.next(), Some(3));
assert_eq!(iter.next(), Some(2));
assert_eq!(iter.next(), Some(1));
assert_eq!(iter.next(), None);
}ok，最简单的迭代器就搞定了，我们来实现剩下俩。
Iter#
这货的难度比IntoIter高一个度，因为我们保留一个引用，也就是一个指针，这就意味着我们需要声明生命周期！
我们先来照猫画虎一下：
pub struct Iter<T> {
next: Option<&Node<T>>,
}
impl<T> List<T> {
pub fn iter(&self) -> Iter<T> {
Iter { next: self.head.map(|node| &node) }
}
}
impl<T> Iterator for Iter<T> {
type Item = &T;
fn next(&mut self) -> Option<Self::Item> {
self.next.map(|node| {
self.next = node.next.map(|node| &node);
&node.elem
})
}
}很明显有问题，我们来看下问题的具体：
> cargo build
error[E0106]: missing lifetime specifier
--> src/second.rs:72:18
|
72 | next: Option<&Node<T>>,
| ^ expected lifetime parameter
error[E0106]: missing lifetime specifier
--> src/second.rs:82:17
|
82 | type Item = &T;
| ^ expected lifetime parameter作者：Oh god. Lifetimes. I've heard of these things. I hear they're a nightmare.
自然就是需要声明生命周期，因为编译器无法推导放在类型上的数据的引用会在什么时候挂掉，所以只能我们手动去声明。
也存在不需要声明的场景，比如：
// 只有一个引用参数，并且返回的数据也是引用，这个时候推导出这俩共用一个生命周期
fn foo(&A) -> &B; // sugar for:
fn foo<'a>(&'a A) -> &'a B;
// 假设A,B,C相互独立，那就是各自管各自的生命周期，无法关联到一起
fn foo(&A, &B, &C); // sugar for:
fn foo<'a, 'b, 'c>(&'a A, &'b B, &'c C);
// 在method中，如果返回的也是个引用，那么它的生命周期按`self`的来，因为self如果没了就意味着调用这个`foo`方法的家伙也没了，B和C我不知道，但是self没了，靠谱点输出也没了才安全。
fn foo(&self, &B, &C) -> &D; // sugar for:
fn foo<'a, 'b, 'c>(&'a self, &'b B, &'c C) -> &'a D;
这些都是编译器可以推导出来的，因为它遵守输入的生命周期最少都要比输出的活得久
换句话说就是输出按输入中生命周期最短那个算，这样必定安全。
你也可以在终端输入rustc --explain E0106
> rustc --explain E0106
This error indicates that a lifetime is missing from a type. If it is an error
inside a function signature, the problem may be with failing to adhere to the
lifetime elision rules (see below).
Here are some simple examples of where you'll run into this error:
struct Foo { x: &bool } // error
struct Foo<'a> { x: &'a bool } // correct
enum Bar { A(u8), B(&bool), } // error
enum Bar<'a> { A(u8), B(&'a bool), } // correct
type MyStr = &str; // error
type MyStr<'a> = &'a str; //correct
...这里会告诉你怎么做是对的。
对于我们的这个代码，改起来也还算简单：
pub struct Iter<'a, T> {
next: Option<&'a Node<T>>,
}
impl<'a, T> List<T> {
pub fn iter(&'a self) -> Iter<'a, T> {
Iter { next: self.head.map(|node| &'a node) }
}
}
impl<'a, T> Iterator for Iter<'a, T> {
type Item = &'a T;
fn next(&'a mut self) -> Option<Self::Item> {
self.next.map(|node| {
self.next = node.next.map(|node| &'a node);
&'a node.elem
})
}
}可以看到，生命周期的传染性和async/.await有的一拼，代码改完可读性减低一半。但这是必要的，因为我们没有**gc**!
类似的C或者C++对于处理空指针（悬浮引用）的问题上采用的是放任，有问题自行解决。
rust则是选择能管就管，毕竟对标的是它俩，对外宣传的重点就是安全，安全，还TM的安全！。
那么古尔丹，代价是什么呢？
自然就是开发的成本和复杂度。
扯远了，回到代码中。
上面的代码还是有问题：
> cargo build
error: expected `:`, found `node`
--> src/second.rs:77:47
|
77 | Iter { next: self.head.map(|node| &'a node) }
| ---- while parsing this struct ^^^^ expected `:`
error: expected `:`, found `node`
--> src/second.rs:85:50
|
85 | self.next = node.next.map(|node| &'a node);
| ^^^^ expected `:`
error[E0063]: missing field `next` in initializer of `second::Iter<'_, _>`
--> src/second.rs:77:9
|
77 | Iter { next: self.head.map(|node| &'a node) }
| ^^^^ missing `next`简单地说就是我们写太多'a了，都在同一个函数里我们写它干啥，吃饱了撑着。
调整下，涉及到Iter里的T才需要声明，比如List<T>是没有必要声明的：
// Iter is generic over *some* lifetime, it doesn't care
pub struct Iter<'a, T> {
next: Option<&'a Node<T>>,
}
// No lifetime here, List doesn't have any associated lifetimes
impl<T> List<T> {
// We declare a fresh lifetime here for the *exact* borrow that
// creates the iter. Now &self needs to be valid as long as the
// Iter is around.
pub fn iter<'a>(&'a self) -> Iter<'a, T> {
Iter { next: self.head.map(|node| &node) }
}
}
// We *do* have a lifetime here, because Iter has one that we need to define
impl<'a, T> Iterator for Iter<'a, T> {
// Need it here too, this is a type declaration
type Item = &'a T;
// None of this needs to change, handled by the above.
// Self continues to be incredibly hype and amazing
fn next(&mut self) -> Option<Self::Item> {
self.next.map(|node| {
self.next = node.next.map(|node| &node);
&node.elem
})
}
}
这回去掉没用的生命周期之后，
居然还有问题！！！
cargo build
error[E0308]: mismatched types
--> src/second.rs:77:22
|
77 | Iter { next: self.head.map(|node| &node) }
| ^^^^^^^^^^^^^^^^^^^^^^^^^^^ expected struct `second::Node`, found struct `std::boxed::Box`
|
= note: expected type `std::option::Option<&second::Node<T>>`
found type `std::option::Option<&std::boxed::Box<second::Node<T>>>`
error[E0308]: mismatched types
--> src/second.rs:85:25
|
85 | self.next = node.next.map(|node| &node);
| ^^^^^^^^^^^^^^^^^^^^^^^^^^^ expected struct `second::Node`, found struct `std::boxed::Box`
|
= note: expected type `std::option::Option<&'a second::Node<T>>`
found type `std::option::Option<&std::boxed::Box<second::Node<T>>>`
(╯°□°)╯︵ ┻━┻
问题也简单，类型问题，我们返回的是一个Box::<Node>，我们要的是Node，所以需要*一下，因为Box本身返回的是一个指针。
impl<T> List<T> {
pub fn iter<'a>(&'a self) -> Iter<'a, T> {
Iter { next: self.head.map(|node| &*node) }
}
}
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.map(|node| &*node);
&node.elem
})
}
}cargo，启动！
cargo build
Compiling lists v0.1.0 (/Users/ABeingessner/dev/temp/lists)
error[E0515]: cannot return reference to local data `*node`
--> src/second.rs:77:43
|
77 | Iter { next: self.head.map(|node| &*node) }
| ^^^^^^ returns a reference to data owned by the current function
error[E0507]: cannot move out of borrowed content
--> src/second.rs:77:22
|
77 | Iter { next: self.head.map(|node| &*node) }
| ^^^^^^^^^ cannot move out of borrowed content
error[E0515]: cannot return reference to local data `*node`
--> src/second.rs:85:46
|
85 | self.next = node.next.map(|node| &*node);
| ^^^^^^ returns a reference to data owned by the current function
error[E0507]: cannot move out of borrowed content
--> src/second.rs:85:25
|
85 | self.next = node.next.map(|node| &*node);
| ^^^^^^^^^ cannot move out of borrowed content(ﾉಥ益ಥ）ﾉ ┻━┻
原来忘了as_ref
pub struct Iter<'a, T> {
next: Option<&'a Node<T>>,
}
impl<T> List<T> {
pub fn iter<'a>(&'a self) -> Iter<'a, T> {
Iter { next: self.head.as_ref().map(|node| &*node) }
}
}
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_ref().map(|node| &*node);
&node.elem
})
}
}cargo, 启..启动！
cargo build
Compiling lists v0.1.0 (/Users/ABeingessner/dev/temp/lists)
error[E0308]: mismatched types
--> src/second.rs:77:22
|
77 | Iter { next: self.head.as_ref().map(|node| &*node) }
| ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ expected struct `second::Node`, found struct `std::boxed::Box`
|
= note: expected type `std::option::Option<&second::Node<T>>`
found type `std::option::Option<&std::boxed::Box<second::Node<T>>>`
error[E0308]: mismatched types
--> src/second.rs:85:25
|
85 | self.next = node.next.as_ref().map(|node| &*node);
| ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ expected struct `second::Node`, found struct `std::boxed::Box`
|
= note: expected type `std::option::Option<&'a second::Node<T>>`
found type `std::option::Option<&std::boxed::Box<second::Node<T>>>`😭
又多了个Box，因为*解的是as_ref这一层，Box的没解到。
我们直接改用as_deref，返回解引用的引用，也就是数据的引用，即&Node，相当于as_ref.map(|node| &**node)
另外我们还可以通过类型声明的方式让编译器帮我们解引用，比如：
self.next = node.next.as_ref().map::<&Node<T>, _>(|node| &node);
因为map自身接收泛型，所以需要我们声明。这样编译器会自动帮我们*。
pub struct Iter<'a, T> {
next: Option<&'a Node<T>>,
}
impl<T> List<T> {
pub fn iter<'a>(&'a self) -> Iter<'a, 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
})
}
}cargo，再带我们冲一次吧！！
cargo build
这回终于可以了（流下心酸的眼泪）
然后我们来写测试用例：
#[test]
fn iter() {
let mut list = List::new();
list.push(1); list.push(2); list.push(3);
let mut iter = list.iter();
assert_eq!(iter.next(), Some(&3));
assert_eq!(iter.next(), Some(&2));
assert_eq!(iter.next(), Some(&1));
}IterMut#
这货难度自然和Iter差不多，但是难一点，因为是支持可变的，可变引用的限制比不可变引用的大很多。
我们先来写类型：
pub struct IterMut<'a, T> {
next: Option<&'a mut Node<T>>,
}
impl<'a, T> Iterator for IterMut<'a, T> {
type Item = &'a T;
fn next(&mut self) -> Option<Self::Item> { /* stuff */ }
}其中实现Iterator这部分相当于
impl<'a, T> Iterator for Iter<'a, T> {
type Item = &'a T;
fn next<'b>(&'b mut self) -> Option<&'a T> { /* stuff */ }
}然后根据上一小节复习的知识，next方法中可以省略掉生命周期。
然后我们来实现剩下的方法：
pub struct IterMut<'a, T> {
next: Option<&'a mut Node<T>>,
}
impl<T> List<T> {
pub fn iter_mut(&mut self) -> IterMut<'_, T> {
IterMut { next: self.head.as_deref_mut() }
}
}
impl<'a, T> Iterator for IterMut<'a, T> {
type Item = &'a mut T;
fn next(&mut self) -> Option<Self::Item> {
self.next.map(|node| {
self.next = node.next.as_deref_mut();
&mut node.elem
})
}
}
不过这里有个问题
error[E0507]: cannot move out of borrowed content
--> src/second.rs:103:9
|
103 | self.next.map(|node| {
| ^^^^^^^^^ cannot move out of borrowed content因为next自身保管的就是&mut，如果你再分享一个&mut出去，那么就会同时存在两个&mut，这是不允许的。
另外这里补充一个知识：&是Copy的，连带着Option<&>也是Copy的，但是&mut不是，所以Option<&mut>也不是Copy的。
存放在堆上的数据一般都是Copy的，比如i32类型，它可以直接复制，为什么呢？因为它会自动调用Copy，复制一个也放到栈上（注意，如果你是&i32，那就是搞了一个指针也放在栈上指向这个数据）。
回到我们的问题中，既然不能同时存在俩&mut，那我们只能将next里面的take出来了
fn next(&mut self) -> Option<Self::Item> {
self.next.take().map(|node| {
self.next = node.next.as_deref_mut();
&mut node.elem
})
}注意，这个时候self.next被take之后变成 None了，我们之所以这么做一方面是没办法很好解决所有权问题（要么用unsafe），另一方面是我们没办法拿到next的上一个，所以可以大胆一点，将next直接take出来。
现在我们可以直接通过引用去修改数据，这样就舒服很多了。
代码整合#
#![allow(unused)]
fn main() {
pub struct List<T> {
head: Link<T>,
}
type Link<T> = Option<Box<Node<T>>>;
struct Node<T> {
elem: T,
next: Link<T>,
}
impl<T> List<T> {
pub fn new() -> Self {
List { head: None }
}
pub fn push(&mut self, elem: T) {
let new_node = Box::new(Node {
elem: elem,
next: self.head.take(),
});
self.head = Some(new_node);
}
pub fn pop(&mut self) -> Option<T> {
self.head.take().map(|node| {
self.head = node.next;
node.elem
})
}
pub fn peek(&self) -> Option<&T> {
self.head.as_ref().map(|node| {
&node.elem
})
}
pub fn peek_mut(&mut self) -> Option<&mut T> {
self.head.as_mut().map(|node| {
&mut node.elem
})
}
pub fn into_iter(self) -> IntoIter<T> {
IntoIter(self)
}
pub fn iter(&self) -> Iter<'_, T> {
Iter { next: self.head.as_deref() }
}
pub fn iter_mut(&mut self) -> IterMut<'_, T> {
IterMut { next: self.head.as_deref_mut() }
}
}
impl<T> Drop for List<T> {
fn drop(&mut self) {
let mut cur_link = self.head.take();
while let Some(mut boxed_node) = cur_link {
cur_link = boxed_node.next.take();
}
}
}
pub struct IntoIter<T>(List<T>);
impl<T> Iterator for IntoIter<T> {
type Item = T;
fn next(&mut self) -> Option<Self::Item> {
// access fields of a tuple struct numerically
self.0.pop()
}
}
pub struct Iter<'a, T> {
next: Option<&'a Node<T>>,
}
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
})
}
}
pub struct IterMut<'a, T> {
next: Option<&'a mut Node<T>>,
}
impl<'a, T> Iterator for IterMut<'a, T> {
type Item = &'a mut T;
fn next(&mut self) -> Option<Self::Item> {
self.next.take().map(|node| {
self.next = node.next.as_deref_mut();
&mut node.elem
})
}
}
#[cfg(test)]
mod test {
use super::List;
#[test]
fn basics() {
let mut list = List::new();
// Check empty list behaves right
assert_eq!(list.pop(), None);
// Populate list
list.push(1);
list.push(2);
list.push(3);
// Check normal removal
assert_eq!(list.pop(), Some(3));
assert_eq!(list.pop(), Some(2));
// Push some more just to make sure nothing's corrupted
list.push(4);
list.push(5);
// Check normal removal
assert_eq!(list.pop(), Some(5));
assert_eq!(list.pop(), Some(4));
// Check exhaustion
assert_eq!(list.pop(), Some(1));
assert_eq!(list.pop(), None);
}
#[test]
fn peek() {
let mut list = List::new();
assert_eq!(list.peek(), None);
assert_eq!(list.peek_mut(), None);
list.push(1); list.push(2); list.push(3);
assert_eq!(list.peek(), Some(&3));
assert_eq!(list.peek_mut(), Some(&mut 3));
list.peek_mut().map(|value| {
*value = 42
});
assert_eq!(list.peek(), Some(&42));
assert_eq!(list.pop(), Some(42));
}
#[test]
fn into_iter() {
let mut list = List::new();
list.push(1); list.push(2); list.push(3);
let mut iter = list.into_iter();
assert_eq!(iter.next(), Some(3));
assert_eq!(iter.next(), Some(2));
assert_eq!(iter.next(), Some(1));
assert_eq!(iter.next(), None);
}
#[test]
fn iter() {
let mut list = List::new();
list.push(1); list.push(2); list.push(3);
let mut iter = list.iter();
assert_eq!(iter.next(), Some(&3));
assert_eq!(iter.next(), Some(&2));
assert_eq!(iter.next(), Some(&1));
}
#[test]
fn iter_mut() {
let mut list = List::new();
list.push(1); list.push(2); list.push(3);
let mut iter = list.iter_mut();
assert_eq!(iter.next(), Some(&mut 3));
assert_eq!(iter.next(), Some(&mut 2));
assert_eq!(iter.next(), Some(&mut 1));
}
}
}其实这段代码还是有瑕疵，Iter里面我们只能存一次和拿一次！
总结#
今天我们优化了昨天的代码，但是还存在一些问题，我们下面来处理这个问题。