我们现在已经学习了很多 Rust 基础知识,所以我们可以再做很多简单的东西。
对于构造函数,我们可以再次复制粘贴:
Copy impl < T > List < T > {
pub fn new () -> Self {
List { head : None }
}
}
Push 和 pop 已经没有意义了。相反,我们可以提供 append 和 tail,它们提供了大致相同的东西。
让我们从 append 开始。它接受一个 List 和一个元素,并返回一个 List。与可变列表一样,我们希望创建一个新节点,它的下一个值是旧列表。唯一新奇的事情是如何得到下一个值,因为我们不允许修改任何东西。
我们祈祷的答案是 Clone 特质。 每种类型几乎都实现了 Clone,并且提供了一种通用的方式来获得 “另一种类似的副本”,这种共享在逻辑上不相交(仅给出了共享引用)。 它就像C ++中的副本构造函数,但从未被隐式调用。
Rc 特别使用 Clone 作为增加引用计数的方法。因此,我们不需要移动一个 Box 到子列表中,而是克隆旧列表的head。我们甚至不需要在head上匹配,因为Option 公开了一个完全符合我们需要的克隆实现。
好吧,让我们来试一试:
Copy pub fn append ( & self, elem : T ) -> List < T > {
List { head : Some ( Rc :: new ( Node {
elem : elem,
next : self . head . clone (),
}))}
}
Copy > 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 是此操作的逆逻辑。 它获取一个列表,并返回删除了第一个元素的整个列表。 所有操作就是克隆列表中的第二个元素(如果存在)。 让我们尝试一下:
Copy pub fn tail ( & self) -> List < T > {
List { head : self . head . as_ref () . map ( | node | node . next . clone ()) }
}
Copy 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。
Copy pub fn tail ( & self) -> List < T > {
List { head : self . head . as_ref () . and_then ( | node | node . next . clone ()) }
}
太好了。
既然有了tail,我们应该提供 head,它返回对第一个元素的引用。这只是从可变列表中 peek 一下:
Copy pub fn head ( & self) -> Option < & T > {
self . head . as_ref () . map ( | node | & node . elem )
}
很好。
这些功能已经足够我们测试了:
Copy #[cfg(test)]
mod test {
use super :: List ;
#[test]
fn basics () {
let list = List :: new ();
assert_eq! (list . head (), None );
let list = list . append ( 1 ) . append ( 2 ) . append ( 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 );
// Make sure empty tail works
let list = list . tail ();
assert_eq! (list . head (), None );
}
}
Copy > 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也与我们的可变列表相同:
Copy 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_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
})
}
}
Copy #[test]
fn iter () {
let list = List :: new () . append ( 1 ) . append ( 2 ) . append ( 3 );
let mut iter = list . iter ();
assert_eq! (iter . next (), Some ( & 3 ));
assert_eq! (iter . next (), Some ( & 2 ));
assert_eq! (iter . next (), Some ( & 1 ));
}
Copy 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,我们只能共享对元素的访问。