让我们仔细研究一下这个坏小子。
IntoIter
一如既往,IntoIter 将是最简单的,只需包装堆栈并调用 pop:
Copy 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 < T > {
self . 0 . pop_front ()
}
}
但是我们有一个有趣的新发现。 以前,我们的列表只有一个“自然”的迭代顺序,而Deque本质上是双向的。 从头到尾有什么特别之处? 如果有人想朝另一个方向迭代怎么办?
Rust实际上对此有一个答案:DoubleEndedIterator。 DoubleEndedIterator继承自Iterator(意味着所有DoubleEndedIterator均为Iterators),并且需要一个新方法:next_back。 它具有与 next 完全相同的签名,但是应该从另一端产生元素。 DoubleEndedIterator的语义对我们来说非常方便:迭代器成为双端队列。 您可以从正面和背面消耗元素,直到两端收敛为止,此时迭代器为空。
就像 Iterator 和 next 一样,事实证明 next_back 并不是DoubleEndedIterator 的消费者真正关心的东西。 而是,此接口的最好之处在于它公开了rev方法,该方法包装了迭代器以创建一个新的迭代器,该迭代器以相反的顺序生成元素。 这样做的语义很简单:在反向迭代器上对 next 的调用只是对 next_back 的调用。
无论如何,因为我们已经很老套了,所以提供此API非常简单:
Copy impl < T > DoubleEndedIterator for IntoIter < T > {
fn next_back ( &mut self) -> Option < T > {
self . 0 . pop_back ()
}
}
让我们来测试一下:
Copy #[test]
fn into_iter () {
let mut list = List :: new ();
list . push_front ( 1 ); list . push_front ( 2 ); list . push_front ( 3 );
let mut iter = list . into_iter ();
assert_eq! (iter . next (), Some ( 3 ));
assert_eq! (iter . next_back (), Some ( 1 ));
assert_eq! (iter . next (), Some ( 2 ));
assert_eq! (iter . next_back (), None );
assert_eq! (iter . next (), None );
}
Copy cargo test
Running target / debug / lists - 5c71138492ad4b4a
running 11 tests
test fourth :: test :: basics ... ok
test fourth :: test :: peek ... ok
test fourth :: test :: into_iter ... ok
test first :: test :: basics ... ok
test second :: test :: basics ... ok
test second :: test :: iter ... ok
test second :: test :: iter_mut ... ok
test third :: test :: iter ... ok
test third :: test :: basics ... ok
test second :: test :: into_iter ... ok
test second :: test :: peek ... ok
test result : ok . 11 passed; 0 failed; 0 ignored; 0 measured
很好。
Iter
Iter不会那么宽容。 我们将不得不再次处理那些糟糕的Ref事情! 由于引用,我们无法像以前那样存储&Nodes。 相反,让我们尝试存储Ref :
Copy pub struct Iter <' a , T >( Option < Ref <' a , Node < T >>>);
impl < T > List < T > {
pub fn iter ( & self) -> Iter < T > {
Iter (self . head . as_ref () . map ( | head | head . borrow ()))
}
}
到目前为止一切顺利。实现 next 可能有点麻烦,但是我认为它和旧栈 IterMut 的基本逻辑是一样的,只是添加了额外的 RefCell。
Copy impl <' a , T > Iterator for Iter <' a , T > {
type Item = Ref <' a , T >;
fn next ( &mut self) -> Option <Self :: Item > {
self . 0 . take () . map ( | node_ref | {
self . 0 = node_ref . next . as_ref () . map ( | head | head . borrow ());
Ref :: map (node_ref, | node | & node . elem)
})
}
}
Copy cargo build
error[ E0521 ] : borrowed data escapes outside of closure
--> src / fourth . rs : 155 : 13
|
153 | fn next ( &mut self) -> Option <Self :: Item > {
| --------- `self` is declared here, outside of the closure body
154 | self . 0 . take () . map ( | node_ref | {
155 | self . 0 = node_ref . next . as_ref () . map ( | head | head . borrow ());
| ^^^^^^ -------- borrow is only valid in the closure body
| |
| reference to `node_ref` escapes the closure body here
error[ E0505 ] : cannot move out of `node_ref` because it is borrowed
--> src / fourth . rs : 156 : 22
|
153 | fn next ( &mut self) -> Option <Self :: Item > {
| --------- lifetime ` '1` appears in the type of `self`
154 | self.0.take().map(|node_ref| {
155 | self.0 = node_ref.next.as_ref().map(|head| head.borrow());
| ------ -------- borrow of `node_ref` occurs here
| |
| assignment requires that `node_ref` is borrowed for `' 1 `
156 | Ref :: map (node_ref, | node | & node . elem)
| ^^^^^^^^ move out of `node_ref` occurs here
该死。
node_ref 的生命周期不足。 与普通引用不同,Rust 不允许我们像这样拆分引用。 我们从 head.borrow() 中获得的 Ref 只允许与 node_ref 一样长,但是最终在 Ref::map 调用中将其破坏了。
巧合的是,就在我写这篇文章的那一刻,我们想要的功能实际上已经在两天前稳定了。 这意味着它将在几个月后才能稳定发布。 因此,让我们继续进行最新的每晚构建版本:
Copy pub fn map_split < U , V , F >(orig : Ref <' b , T >, f : F ) -> ( Ref <' b , U >, Ref <' b , V >) where
F : FnOnce ( & T ) -> ( & U , & V ),
U : ? Sized ,
V : ? Sized ,
我们来试试..。
Copy fn next ( &mut self) -> Option <Self :: Item > {
self . 0 . take () . map ( | node_ref | {
let (next, elem) = Ref :: map_split (node_ref, | node | {
( & node . next, & node . elem)
});
self . 0 = next . as_ref () . map ( | head | head . borrow ());
elem
})
}
Copy cargo build
Compiling lists v0 . 1 . 0 ( / Users / ABeingessner / dev / temp / lists)
error[ E0521 ] : borrowed data escapes outside of closure
--> src / fourth . rs : 159 : 13
|
153 | fn next ( &mut self) -> Option <Self :: Item > {
| --------- `self` is declared here, outside of the closure body
...
159 | self . 0 = next . as_ref () . map ( | head | head . borrow ());
| ^^^^^^ ---- borrow is only valid in the closure body
| |
| reference to `next` escapes the closure body here
嗯。我们需要再次 Ref::Map 以正确地使用我们的生命周期。但是Ref::Map 返回一个 Ref,我们需要一个Option<Ref>,但是我们需要通过 Ref 来映射我们的 Option。。。
凝视了很久
??????
Copy fn next ( &mut self) -> Option <Self :: Item > {
self . 0 . take () . map ( | node_ref | {
let (next, elem) = Ref :: map_split (node_ref, | node | {
( & node . next, & node . elem)
});
self . 0 = if next . is_some () {
Some ( Ref :: map (next, | next | &** next . as_ref () . unwrap ()))
} else {
None
};
elem
})
}
Copy error[ E0308 ] : mismatched types
--> src / fourth . rs : 162 : 22
|
162 | Some ( Ref :: map (next, | next | &** next . as_ref () . unwrap ()))
| ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ expected struct `fourth::Node`, found struct `std::cell::RefCell`
|
= note : expected type `std :: cell :: Ref <' _ , fourth :: Node <_>>`
found type `std :: cell :: Ref <' _ , std :: cell :: RefCell <fourth :: Node <_>>>`
哦。对。有多个 refcell。我们在列表中走得越深,我们在每个 RefCell 下的嵌套就越多。我们需要维持,比如,一堆 Refs 来代表我们持有的所有借用,因为如果我们停止寻找一个元素,我们需要减少前面每个 RefCell 的借用计数..。
我不认为我们能做什么。这是个死胡同。让我们试着离开 RefCell。
那我们的 Rcs 呢。谁说我们需要存储引用?为什么我们不能克隆整个 Rc,在列表中间添加一个好的拥有句柄呢?
Copy pub struct Iter < T >( Option < Rc < Node < T >>>);
impl < T > List < T > {
pub fn iter ( & self) -> Iter < T > {
Iter (self . head . as_ref () . map ( | head | head . clone ()))
}
}
impl < T > Iterator for Iter < T > {
type Item =
呃... 等等,我们现在要返回什么?&T
? Ref<T>
?
不,这些都不起作用……我们的Iter不再拥有一生! &T 和 Ref 都要求我们在进入下一个生命周期之前声明一些生命周期。 但是我们设法摆脱 Rc 的任何事情都是借用Iterator ...大脑...受伤了... aaaaaahhhhhh
也许我们可以... map... 的 Rc... 得到一个 Rc<T> ?有这种东西吗?文档似乎没有这样的东西。实际上有人做了一个 crate,可以让你这样做。
但是,等等,即使我们这样做,也遇到了一个更大的问题:迭代器失效的可怕幽灵。 以前,我们完全不受迭代器失效的影响,因为Iter借用了列表,使其完全不可变。 但是,如果我们的Iter产生了Rcs,那么他们根本不会借用该列表! 这意味着人们可以在按住指针的同时开始调用push并弹出列表!
天啊,那有什么用? !
好吧,push 实际上很好。 我们已经了解了列表的某些子范围,并且列表将超出我们的视线。 没关系。
然而,pop 则是另一回事。如果他们在我们的范围之外弹出元素,它仍然应该是好的。我们看不到那些节点,所以什么都不会发生。然而,如果他们试图弹出我们正在指向的节点... 一切都会爆炸!特别是当它们打开 try_unwrap 的结果时,它实际上会失败,整个程序将陷入恐慌。
这其实挺酷的。我们可以获得大量内部拥有的指针到列表中,并同时对它进行变异,它将一直工作,直到他们尝试删除我们正在指向的节点。即使这样,我们也不会得到悬空指针或其他任何东西,程序会确定地陷入恐慌!
但是必须在映射Rcs的基础上处理迭代器失效问题,似乎不好。Rc真的让我们失望了。有趣的是,我们经历了不可变堆栈情况的反转。当不可变堆栈很难收回数据的所有权,但每个地方都能得到引用时,我们的列表在获得所有权方面没有问题,但实际上很难借用我们的引用。
虽然公平地说,我们的大部分挣扎都围绕着想要隐藏实现细节和拥有一个体面的 API。如果我们只是到处传播节点,我们可以做好每件事。
见鬼,我们可以使多个并发 IterMuts 在运行时被检查为不可变访问同一个元素!
实际上,这种设计更适合于内部数据结构,因为这种结构从来不会向 API 的使用者公开。内部可变性对于编写安全的应用程序非常重要。没有那么多安全的库。
不管怎样,那就是我放弃了Iter和IterMut。我们可以使用他们,但是很丑。