图结构中拥有的指针 [英] Owned pointer in graph structure
问题描述
这是使用托管指针的工作版本：
struct Dart< ; T> {
alpha：〜[@mut Dart< T>]，
嵌入：〜[@mut T]，
tagged：bool
}
IMPL< T>镖< T> {
pub fn new（dim：uint） - > @mut Dart< T> {
let mut dart = @mut Dart {alpha：〜[]，embed：〜[]，tagged：false};
dart.alpha = vec :: from_elem（dim，dart）;
返回飞镖;
}
pub fn get_dim（& self） - > uint {
返回self.alpha.len（）;
}
pub fn遍历（@mut self，invs：& [uint]，f：& fn（& Dart< T>））{
let dim = self.get_dim （）;
用于invs.each | i | {if * i> = dim {return}}; //测试invs的边界vec
if invs.len（）== 2 {
let spread：int = int :: abs（invs [1] as int - invs [0] as int）;
if spread == 1 {//简单循环
让mut dart = self;
let mut i = invs [0];
while！dart.tagged {
dart.tagged = true;
f（dart）;
dart = dart.alpha [i];
if i == invs [0] {i = invs [1];}
else {i == invs [0];}
}}
// else if spread == 2 {//最多4个单元格遍历
//}
}
else {
let mut stack =〜[self];
self.tagged = true;
while！stack.is_empty（）{
let mut dart = stack.pop（）;
f（dart）;
用于invs.each | i | {
if！dart.alpha [* i] .tagged {
dart.alpha [* i] .tagged = true;
stack.push（dart）;
}}}}}}
得出的结论是，由于循环性质，这可能甚至不可能与拥有的指针相关联（没有绑结，因为我是警告）。我对此的微弱尝试如下。我的问题是，这种结构可以实现而不诉诸托管指针？如果不是，上面的代码是否被认为是生锈的？ （惯性生锈）。谢谢。
struct GMap<'self，T> {
dim：uint，
darts：〜[〜Dart<'self，T>]
}
struct Dart<'self，T> {
alpha：〜[&'self mut Dart<'self，T>]，
embed：〜[&'self mut T]，
tagged：bool
}
impl<'self，T> GMap<'self，T> {
pub fn new_dart（&'self mut self self）{
let mut dart =〜Dart {alpha：〜[]，embed：〜[]，tagged：false};
let dartRef：&'self mut Dart<'self，T> = dart;
dartRef.alpha = vec :: from_elem（self.dim，copy dartRef）;
self.darts.push（dart）;
}
}
I很确定使用& mut 指针是不可能的，因为一次只能有一个这样的指针存在，例如：
fn main（）{
let mut i = 0;
let a =& mut i;
让b =& mut i;
and-mut.rs:4:12: 4:18错误：不能一次借用`i`作为可变多次
和-mut.rs:4让b =& mut i;
^ ~~~~~
and-mut.rs:3:12：3:18注意：第二次借用`i`为可变的
和--mut.rs:3让a =& mut i;
^ ~~~~~
错误：由于前面的错误而中止
可以通过将不安全的指针存储到内存（ ptr :: to_mut_unsafe_ptr ）或指向 darts code> GMap 的成员。从本质上说，存储一个对内存的引用（在 self.darts 中）并且所有操作都必须经过它。
<这可能看起来像：
impl<'self，T> GMap<'self，T> {
pub fn new_dart（&'self mut self self）{
let ind = self.darts.len（）;
self.darts.push（〜Dart {alpha：vec :: from_elem（self.dim，ind），embed：〜[]，tagged：false}）;
code $ <$ $ $ $ $ $ $ $ $ $> $ c>需要改变为 GMap （例如 fn（& mut self，node_ind：uint，invs：& [uint]，f：& fn（& Dart< T>））），或者至少取一个 GMap p>
（在完全不同的注释中，有支持外部迭代器，它比内部迭代器（那些需要闭包的组件）要复杂得多，因此为定义其中一个<遍历可能（或可能不）使用它更好。）
With the generous help of the rust community I managed to get the base of a topological data structure assembled using managed pointers. This came together rather nicely and I was pretty excited about Rust in general. Then I read this post (which seems like a reasonable plan) and it inspired me to back track and try to re-assemble it using only owned pointers if possible.
This is the working version using managed pointers:
struct Dart<T> {
alpha: ~[@mut Dart<T>],
embed: ~[@mut T],
tagged: bool
}
impl<T> Dart<T> {
pub fn new(dim: uint) -> @mut Dart<T> {
let mut dart = @mut Dart{alpha: ~[], embed: ~[], tagged: false};
dart.alpha = vec::from_elem(dim, dart);
return dart;
}
pub fn get_dim(&self) -> uint {
return self.alpha.len();
}
pub fn traverse(@mut self, invs: &[uint], f: &fn(&Dart<T>)) {
let dim = self.get_dim();
for invs.each |i| {if *i >= dim {return}}; //test bounds on invs vec
if invs.len() == 2 {
let spread:int = int::abs(invs[1] as int - invs[0] as int);
if spread == 1 { //simple loop
let mut dart = self;
let mut i = invs[0];
while !dart.tagged {
dart.tagged = true;
f(dart);
dart = dart.alpha[i];
if i == invs[0] {i = invs[1];}
else {i == invs[0];}
} }
// else if spread == 2 { // max 4 cells traversed
// }
}
else {
let mut stack = ~[self];
self.tagged = true;
while !stack.is_empty() {
let mut dart = stack.pop();
f(dart);
for invs.each |i| {
if !dart.alpha[*i].tagged {
dart.alpha[*i].tagged = true;
stack.push(dart);
} } } } } }
After a few hours of chasing lifetime errors I have come to the conclusion that this may not even be possible with owned pointers due to the cyclic nature (without tying the knot as I was warned). My feeble attempt at this is below. My question, is this structure possible to implement without resorting to managed pointers? And if not, is the code above considered reasonably "rusty"? (idiomatic rust). Thanks.
struct GMap<'self,T> {
dim: uint,
darts: ~[~Dart<'self,T>]
}
struct Dart<'self,T> {
alpha: ~[&'self mut Dart<'self, T>],
embed: ~[&'self mut T],
tagged: bool
}
impl<'self, T> GMap<'self, T> {
pub fn new_dart(&'self mut self) {
let mut dart = ~Dart{alpha: ~[], embed: ~[], tagged: false};
let dartRef: &'self mut Dart<'self, T> = dart;
dartRef.alpha = vec::from_elem(self.dim, copy dartRef);
self.darts.push(dart);
}
}
解决方案 I'm pretty sure that using &mut pointers is impossible, since one can only have one such pointer in existence at a time, e.g.:
fn main() {
let mut i = 0;
let a = &mut i;
let b = &mut i;
}
and-mut.rs:4:12: 4:18 error: cannot borrow `i` as mutable more than once at at a time
and-mut.rs:4 let b = &mut i;
^~~~~~
and-mut.rs:3:12: 3:18 note: second borrow of `i` as mutable occurs here
and-mut.rs:3 let a = &mut i;
^~~~~~
error: aborting due to previous error
One could get around the borrow checker unsafely, by either storing unsafe pointer to the memory (ptr::to_mut_unsafe_ptr), or indices into the darts member of GMap. Essentially, storing a single reference to the memory (in self.darts) and all operations have to go through it.
This might look like:
impl<'self, T> GMap<'self, T> {
pub fn new_dart(&'self mut self) {
let ind = self.darts.len();
self.darts.push(~Dart{alpha: vec::from_elem(self.dim, ind), embed: ~[], tagged: false});
}
}
traverse would need to change to either be a method on GMap (e.g. fn(&mut self, node_ind: uint, invs: &[uint], f: &fn(&Dart<T>))), or at least take a GMap type.
(On an entirely different note, there is library support for external iterators, which are far more composable than the internal iterators (the ones that take a closure). So defining one of these for traverse may (or may not) make using it nicer.)
这篇关于图结构中拥有的指针的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
