为二叉树实现 IntoIterator
Implement IntoIterator for binary tree
我正在尝试构建一个二叉树并编写一个迭代器来遍历树中的值。
在为我的树节点实现 IntoIterator 特征时,我 运行 遇到了生命周期问题
src\main.rs:43:6: 43:8 error: the lifetime parameter `'a` is not constrained by the impl trait, self type, or predicates [E0207]
src\main.rs:43 impl<'a, T: 'a> IntoIterator for Node<T> {
我知道我需要指定 NodeIterator 将与 Node 一样长,但我不确定如何表达
use std::cmp::PartialOrd;
use std::boxed::Box;
struct Node<T: PartialOrd> {
value: T,
left: Option<Box<Node<T>>>,
right: Option<Box<Node<T>>>,
}
struct NodeIterator<'a, T: 'a + PartialOrd> {
current: &'a Node<T>,
parent: Option<&'a Node<T>>,
}
impl<T: PartialOrd> Node<T> {
pub fn insert(&mut self, value: T) {
...
}
}
impl<'a, T: 'a> IntoIterator for Node<T> { // line 43
type Item = T;
type IntoIter = NodeIterator<'a, T>;
fn into_iter(&self) -> Self::IntoIter {
NodeIterator::<'a> {
current: Some(&self),
parent: None
}
}
}
您遇到的特定错误是 'a
应该出现在 for
的右侧。否则编译器怎么知道a
是什么?
在实现 IntoIterator
时,您必须决定迭代器是 消耗 容器,还是只生成对容器的引用。目前,您的设置不一致,错误消息指出了这一点。
在二叉树的情况下,您还必须考虑生成值的顺序:传统顺序是深度优先(产生排序序列)和广度优先(公开 "layers" 的树)。我将首先假设深度,因为它是最常见的。
让我们先解决消费迭代器的情况。从某种意义上说,它更简单,我们不必担心生命周期。
#![feature(box_patterns)]
struct Node<T: PartialOrd> {
value: T,
left: Option<Box<Node<T>>>,
right: Option<Box<Node<T>>>,
}
struct NodeIterator<T: PartialOrd> {
stack: Vec<Node<T>>,
next: Option<T>,
}
impl<T: PartialOrd> IntoIterator for Node<T> {
type Item = T;
type IntoIter = NodeIterator<T>;
fn into_iter(self) -> Self::IntoIter {
let mut stack = Vec::new();
let smallest = pop_smallest(self, &mut stack);
NodeIterator { stack: stack, next: Some(smallest) }
}
}
impl<T: PartialOrd> Iterator for NodeIterator<T> {
type Item = T;
fn next(&mut self) -> Option<T> {
if let Some(next) = self.next.take() {
return Some(next);
}
if let Some(Node { value, right, .. }) = self.stack.pop() {
if let Some(right) = right {
let box right = right;
self.stack.push(right);
}
return Some(value);
}
None
}
}
fn pop_smallest<T: PartialOrd>(node: Node<T>, stack: &mut Vec<Node<T>>) -> T {
let Node { value, left, right } = node;
if let Some(left) = left {
stack.push(Node { value: value, left: None, right: right });
let box left = left;
return pop_smallest(left, stack);
}
if let Some(right) = right {
let box right = right;
stack.push(right);
}
value
}
fn main() {
let root = Node {
value: 3,
left: Some(Box::new(Node { value: 2, left: None, right: None })),
right: Some(Box::new(Node { value: 4, left: None, right: None }))
};
for t in root {
println!("{}", t);
}
}
现在,我们可以 "easily" 通过添加适当的参考文献使其适应非消耗情况:
struct RefNodeIterator<'a, T: PartialOrd + 'a> {
stack: Vec<&'a Node<T>>,
next: Option<&'a T>,
}
impl<'a, T: PartialOrd + 'a> IntoIterator for &'a Node<T> {
type Item = &'a T;
type IntoIter = RefNodeIterator<'a, T>;
fn into_iter(self) -> Self::IntoIter {
let mut stack = Vec::new();
let smallest = pop_smallest_ref(self, &mut stack);
RefNodeIterator { stack: stack, next: Some(smallest) }
}
}
impl<'a, T: PartialOrd + 'a> Iterator for RefNodeIterator<'a, T> {
type Item = &'a T;
fn next(&mut self) -> Option<&'a T> {
if let Some(next) = self.next.take() {
return Some(next);
}
if let Some(node) = self.stack.pop() {
if let Some(ref right) = node.right {
self.stack.push(right);
}
return Some(&node.value);
}
None
}
}
fn pop_smallest_ref<'a, T>(node: &'a Node<T>, stack: &mut Vec<&'a Node<T>>) -> &'a T
where
T: PartialOrd + 'a
{
if let Some(ref left) = node.left {
stack.push(node);
return pop_smallest_ref(left, stack);
}
if let Some(ref right) = node.right {
stack.push(right);
}
&node.value
}
里面有很多东西要打开;所以花点时间消化它。具体来说:
- 在
Some(ref right) = node.right
中使用ref
是因为我不想消费node.right
,只是为了获取Option
里面的引用;编译器会抱怨说没有它我不能搬出借来的对象(所以我只是听从了抱怨),
- 在
stack.push(right)
、right: &'a Box<Node<T>>
和 stack: Vec<&'a Node<T>>
中;这就是 Deref
的神奇之处:Box<T>
实现了 Deref<T>
,因此编译器会自动适当地转换引用。
注意:我没有按原样编写这段代码;相反,我只是将前几个引用放在我期望的位置(例如 Iterator
的 return 类型),然后让编译器指导我。
我正在尝试构建一个二叉树并编写一个迭代器来遍历树中的值。 在为我的树节点实现 IntoIterator 特征时,我 运行 遇到了生命周期问题
src\main.rs:43:6: 43:8 error: the lifetime parameter `'a` is not constrained by the impl trait, self type, or predicates [E0207]
src\main.rs:43 impl<'a, T: 'a> IntoIterator for Node<T> {
我知道我需要指定 NodeIterator 将与 Node 一样长,但我不确定如何表达
use std::cmp::PartialOrd;
use std::boxed::Box;
struct Node<T: PartialOrd> {
value: T,
left: Option<Box<Node<T>>>,
right: Option<Box<Node<T>>>,
}
struct NodeIterator<'a, T: 'a + PartialOrd> {
current: &'a Node<T>,
parent: Option<&'a Node<T>>,
}
impl<T: PartialOrd> Node<T> {
pub fn insert(&mut self, value: T) {
...
}
}
impl<'a, T: 'a> IntoIterator for Node<T> { // line 43
type Item = T;
type IntoIter = NodeIterator<'a, T>;
fn into_iter(&self) -> Self::IntoIter {
NodeIterator::<'a> {
current: Some(&self),
parent: None
}
}
}
您遇到的特定错误是 'a
应该出现在 for
的右侧。否则编译器怎么知道a
是什么?
在实现 IntoIterator
时,您必须决定迭代器是 消耗 容器,还是只生成对容器的引用。目前,您的设置不一致,错误消息指出了这一点。
在二叉树的情况下,您还必须考虑生成值的顺序:传统顺序是深度优先(产生排序序列)和广度优先(公开 "layers" 的树)。我将首先假设深度,因为它是最常见的。
让我们先解决消费迭代器的情况。从某种意义上说,它更简单,我们不必担心生命周期。
#![feature(box_patterns)]
struct Node<T: PartialOrd> {
value: T,
left: Option<Box<Node<T>>>,
right: Option<Box<Node<T>>>,
}
struct NodeIterator<T: PartialOrd> {
stack: Vec<Node<T>>,
next: Option<T>,
}
impl<T: PartialOrd> IntoIterator for Node<T> {
type Item = T;
type IntoIter = NodeIterator<T>;
fn into_iter(self) -> Self::IntoIter {
let mut stack = Vec::new();
let smallest = pop_smallest(self, &mut stack);
NodeIterator { stack: stack, next: Some(smallest) }
}
}
impl<T: PartialOrd> Iterator for NodeIterator<T> {
type Item = T;
fn next(&mut self) -> Option<T> {
if let Some(next) = self.next.take() {
return Some(next);
}
if let Some(Node { value, right, .. }) = self.stack.pop() {
if let Some(right) = right {
let box right = right;
self.stack.push(right);
}
return Some(value);
}
None
}
}
fn pop_smallest<T: PartialOrd>(node: Node<T>, stack: &mut Vec<Node<T>>) -> T {
let Node { value, left, right } = node;
if let Some(left) = left {
stack.push(Node { value: value, left: None, right: right });
let box left = left;
return pop_smallest(left, stack);
}
if let Some(right) = right {
let box right = right;
stack.push(right);
}
value
}
fn main() {
let root = Node {
value: 3,
left: Some(Box::new(Node { value: 2, left: None, right: None })),
right: Some(Box::new(Node { value: 4, left: None, right: None }))
};
for t in root {
println!("{}", t);
}
}
现在,我们可以 "easily" 通过添加适当的参考文献使其适应非消耗情况:
struct RefNodeIterator<'a, T: PartialOrd + 'a> {
stack: Vec<&'a Node<T>>,
next: Option<&'a T>,
}
impl<'a, T: PartialOrd + 'a> IntoIterator for &'a Node<T> {
type Item = &'a T;
type IntoIter = RefNodeIterator<'a, T>;
fn into_iter(self) -> Self::IntoIter {
let mut stack = Vec::new();
let smallest = pop_smallest_ref(self, &mut stack);
RefNodeIterator { stack: stack, next: Some(smallest) }
}
}
impl<'a, T: PartialOrd + 'a> Iterator for RefNodeIterator<'a, T> {
type Item = &'a T;
fn next(&mut self) -> Option<&'a T> {
if let Some(next) = self.next.take() {
return Some(next);
}
if let Some(node) = self.stack.pop() {
if let Some(ref right) = node.right {
self.stack.push(right);
}
return Some(&node.value);
}
None
}
}
fn pop_smallest_ref<'a, T>(node: &'a Node<T>, stack: &mut Vec<&'a Node<T>>) -> &'a T
where
T: PartialOrd + 'a
{
if let Some(ref left) = node.left {
stack.push(node);
return pop_smallest_ref(left, stack);
}
if let Some(ref right) = node.right {
stack.push(right);
}
&node.value
}
里面有很多东西要打开;所以花点时间消化它。具体来说:
- 在
Some(ref right) = node.right
中使用ref
是因为我不想消费node.right
,只是为了获取Option
里面的引用;编译器会抱怨说没有它我不能搬出借来的对象(所以我只是听从了抱怨), - 在
stack.push(right)
、right: &'a Box<Node<T>>
和stack: Vec<&'a Node<T>>
中;这就是Deref
的神奇之处:Box<T>
实现了Deref<T>
,因此编译器会自动适当地转换引用。
注意:我没有按原样编写这段代码;相反,我只是将前几个引用放在我期望的位置(例如 Iterator
的 return 类型),然后让编译器指导我。