graph - 图结构中的拥有指针

Question

在 Rust 社区的慷慨帮助下，我设法获得了使用托管指针组装的拓扑数据结构的基础。这很好地结合在一起，总的来说我对 Rust 感到非常兴奋。然后我读了这个post (这似乎是一个合理的计划)并且它启发了我回溯并尝试在可能的情况下仅使用拥有的指针重新组装它。

这是使用托管指针的工作版本:

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);
}   }   }   }   }   }    

在追逐生命周期错误几个小时后，我得出的结论是，由于循环性质，这甚至可能无法使用拥有的指针(没有像我那样打结 warned )。我对此的微弱尝试如下。我的问题是，这种结构是否可以在不诉诸托管指针的情况下实现？如果不是，上面的代码是否被认为是合理的“使用rust ”？ (惯用的使用rust )。谢谢。

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);              
    }
} 

Answer 1

我很确定使用 &mut指针是不可能的，因为一次只能有一个这样的指针，例如:

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

可以通过将不安全的指针存储到内存 (ptr::to_mut_unsafe_ptr) 或将索引存储到 darts 中来不安全地绕过借用检查器。 GMap的成员.本质上，存储对内存的单个引用(在 self.darts 中)并且所有操作都必须通过它。

这可能看起来像:

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需要更改为 GMap 上的方法之一(例如 fn(&mut self, node_ind: uint, invs: &[uint], f: &fn(&Dart<T>)) )，或者至少采取 GMap类型。

(完全不同的是，库支持 external iterators ，它比内部迭代器(采用闭包的迭代器)更具可组合性。因此定义其中一个用于traverse 可能(也可能不会)让使用起来更好。)