- html - 出于某种原因,IE8 对我的 Sass 文件中继承的 html5 CSS 不友好?
- JMeter 在响应断言中使用 span 标签的问题
- html - 在 :hover and :active? 上具有不同效果的 CSS 动画
- html - 相对于居中的 html 内容固定的 CSS 重复背景?
我正在尝试构建一个二叉树并编写一个迭代器来遍历树中的值。在为我的树节点实现 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
时您必须决定迭代器是消费容器,还是只生成对容器的引用。目前,您的设置不一致,错误消息指出了这一点。
在二叉树的情况下,您还必须考虑生成值的顺序:传统顺序是深度优先(产生排序序列)和广度优先(暴露树的“层” ).我将首先假设深度,因为它是最常见的。
让我们先解决消费迭代器的情况。从某种意义上说,它更简单,我们不必担心生命周期。
#![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);
}
}
现在,我们可以通过添加适当的引用来“轻松”地使其适应非消费情况:
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
}
里面有很多东西要打开;所以花点时间消化它。具体来说:
ref
在Some(ref right) = node.right
是因为我不想消费node.right
, 只获取Option
里面的引用;编译器会提示我不能在没有它的情况下移出借来的对象(所以我只是听从了提示),stack.push(right)
, right: &'a Box<Node<T>>
然而stack: Vec<&'a Node<T>>
;这就是Deref
的魔力: Box<T>
工具 Deref<T>
因此编译器会根据需要自动转换引用。注意:我没有按原样编写这段代码;相反,我只是将前几个引用放在我期望的位置(例如 Iterator
的返回类型),然后让编译器指导我。
关于oop - 为二叉树实现 IntoIterator,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/43833588/
关闭。这个问题是opinion-based .它目前不接受答案。 想改善这个问题吗?更新问题,以便可以通过 editing this post 用事实和引文回答问题. 4年前关闭。 Improve t
就目前而言,这个问题不适合我们的问答形式。我们希望答案得到事实、引用或专业知识的支持,但这个问题可能会引起辩论、争论、投票或扩展讨论。如果您觉得这个问题可以改进并可能重新打开,visit the he
在面向对象的编程中,“基类”是派生其他类的类(http://en.wikipedia.org/wiki/Base_class)。 但是,基类的反面是什么?换句话说,什么是没有任何子类的类? 编辑:我正
关闭。这个问题需要更多focused .它目前不接受答案。 想改善这个问题吗?更新问题,使其仅关注一个问题 editing this post . 8年前关闭。 Improve this questi
据我了解,OOP 是大型项目最常用的范式。我也知道大系统的一些较小的子集使用其他范式(例如 SQL,它是声明性的),并且我也意识到在较低级别的计算 OOP 并不真正可行。但在我看来,通常更高级别的解决
就目前而言,这个问题不适合我们的问答形式。我们希望答案得到事实、引用资料或专业知识的支持,但这个问题可能会引发辩论、争论、投票或扩展讨论。如果您觉得这个问题可以改进并可能重新打开,visit the
就目前而言,这个问题不适合我们的问答形式。我们希望答案得到事实、引用或专业知识的支持,但这个问题可能会引起辩论、争论、投票或扩展讨论。如果您觉得这个问题可以改进并可能重新打开,visit the he
最近听说OOP(Java)有9条规则。我只知道四种:抽象、多态、继承和封装。 OOP 还有更多规则吗? 最佳答案 看来您正在寻找的是 Principles of Object-Oriented Des
我曾经在一次采访中被问到“OOP 的 3 个主要概念是什么?”。我回答说,我认为有4个,如下: 继承 封装 抽象 多态性 我说得对吗? 最佳答案 语言要成为面向对象有3个要求: 仅支持封装(对象)的语
我有一个关于特定 OOP 问题的组织的简单问题。 假设我有一个地形类,里面充满了瓷砖。 Tile 类有多个派生类,即 Door。 Door 类有一个名为 open() 的方法,用于打开门,还有一个名为
就目前情况而言,这个问题不太适合我们的问答形式。我们希望答案得到事实、引用资料或专业知识的支持,但这个问题可能会引发辩论、争论、民意调查或扩展讨论。如果您觉得这个问题可以改进并可能重新开放,visit
我是 Go 的新手,然后我通过示例搜索了很多如何拥有带有静态函数/变量的静态类,例如 C#。但是,我找不到任何可以很好地回答它的东西。也许这个问题看起来很愚蠢,但我不喜欢不确定或不完全理解某事。 假设
我曾尝试搜索此问题的答案,但很难用语言表达,而且许多问题要么是关于如何创建类,要么是关于如何做非常具体的事情。我需要更多的实用概述 - 我是自学成才的,我了解对象是什么(以及如何创建它们),但我从未见
在开始编码之前,我通常会尝试在没有太多分析(没有图表)的情况下进行 TDD。通常我发现自己将一个类拆分为其他类以分离关注点。我想知道更深入的分析是否会阻止这种情况。我认为大部分面向对象分析无法预测其中
在阅读单例时,我发现这个解释是使用单例的原因: since these object methods are not changing the internal class state, we can
如这里所述 https://standardofnorms.wordpress.com/2012/09/02/4-pillars-of-object-oriented-programming/ 并作为
我是这个网站的新手,所以如果我在发布问题时做错了什么,请告诉我,以便我下次修复。 我很好奇从单个基类继承多个类是否是糟糕的 OOP 实践。这可能不太合理,所以我要详细说明一下。 例如,假设您正在设计一
我对“工厂相关”设计模式及其 OOP 实现的理解一直很简单。 一个 《工厂法》是类内部的一个方法,它有一个接口(interface)(或抽象类)作为返回类型,并根据一些内部逻辑构造实现该接口(inte
C# 中的“密封”关键字,Java 中的 Final。 因为我几乎从不创建任何图表并且我只使用已经完成的类(来自框架)我多年后仍然不知道为什么有人会“锁定”一个类所以它永远不会被扩展/继承。 它是有益
我正在研究面向对象的概念,抽象概念基本上被描述为对用户隐藏实现。因此,如果类中有一个成员函数并且我们为某些任务调用该函数,抽象表示用户不应该关心事情是如何完成的,而应该只知道正在完成什么。但即使在非面
我是一名优秀的程序员,十分优秀!