结构中的可变载体

Question

我正在尝试使用图形聚类算法在Rust中工作.部分代码是WeightedGraph具有邻接列表表示的数据结构.核心将像这样表示(在Python中显示,以明确我正在尝试做什么):

class Edge(object):
    def __init__(self, target, weight):
        self.target = target
        self.weight = weight

class WeightedGraph(object):
    def __init__(self, initial_size):
        self.adjacency_list = [[] for i in range(initial_size)]
        self.size = initial_size
        self.edge_count = 0

    def add_edge(self, source, target, weight):
        self.adjacency_list[source].append(Edge(target, weight))
        self.edge_count += 1

因此,邻接列表包含一个数组n数组:图中每个节点一个数组.内部数组保存该节点的邻居,表示为Edge(target节点号和双精度数weight).

我将整个事情翻译成Rust的尝试看起来像这样:

struct Edge {
    target: uint,
    weight: f64
}

struct WeightedGraph {
    adjacency_list: ~Vec<~Vec<Edge>>,
    size: uint,
    edge_count: int
}

impl WeightedGraph {
    fn new(num_nodes: uint) -> WeightedGraph {
        let mut adjacency_list: ~Vec<~Vec<Edge>> = box Vec::from_fn(num_nodes, |idx| box Vec::new());

        WeightedGraph {
            adjacency_list: adjacency_list,
            size: num_nodes,
            edge_count: 0
        }
    }

    fn add_edge(mut self, source: uint, target: uint, weight: f64) {
        self.adjacency_list.get(source).push(Edge { target: target, weight: weight });
        self.edge_count += 1;
    }
}

但是rustc给了我这个错误:

weightedgraph.rs:24:9: 24:40 error: cannot borrow immutable dereference of `~`-pointer as mutable
weightedgraph.rs:24         self.adjacency_list.get(source).push(Edge { target: target, weight: weight });
                            ^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

那么,有两个主要问题:

1.我怎样才能使该add_edge方法起作用？

我认为WeightedGraph应该拥有所有内部数据(如果我错了,请纠正我).但为什么add_edge不能修改图表自己的数据呢？

2. ~Vec<~Vec<Edge>>表示在每个元素中保存动态列表的可变大小数组/列表的正确方法是什么？

该教程还提到~[int]了矢量语法,所以它应该是:~[~[Edge]]相反？或者Vec<Edge>和之间有什么区别~[Edge]？如果我应该使用~[~[Edge]],那么我将如何构建/初始化内部列表呢？(目前,我试图使用Vec::from_fn)

Answer 1

在WeightedGraph不拥有其所有内部数据,但即使你自己的东西,你必须选择加入变异它.get给你一个&指针,变异你需要一个&mut指针.Vec::get_mut会给你:self.adjacency_list.get_mut(source).push(...).

关于~Vec<Edge>和~[Edge]:它曾经是(直到最近),其~[T]表示可增长的载体T,不像是写其他所有类型,~...这种特殊的情况下被删除,~[T]现在只是一个独特的指针T-slice,即一个拥有指针一堆T在没有任何增长能力的记忆中.Vec<T>现在是可增长的矢量类型.

需要注意的是它的Vec<T>,不是 ~Vec<T> ; 在~曾经是矢量语法的一部分,但在这里它只是一个普通的唯一指针,表示完全没有必要的间接和分配.你想要的adjacency_list: Vec<Vec<Edge>>.A Vec<T>是一个完全成熟的具体类型(data, length, capacity如果对您来说意味着什么,则为三元组),它封装了内存分配和间接,您可以将其用作值.你不会box因此获得任何收益,并且失去清晰度和表现.

你有另一个(次要的)问题:fn add_edge(mut self, ...)就像fn add_edge(self, ...)" self价值取值"一样.由于adjacency_list成员是线性类型(它可以是dropped,它是移动而不是隐式复制),因此您WeightedGraph也是线性类型.以下代码将失败,因为第一次add_edge调用消耗了图形.

let g = WeightedGraph::new(2);
g.add_edge(1, 0, 2); // moving out of g
g.add_edge(0, 1, 3); // error: use of g after move

你想要&mut self:允许变异,self但不要取得它的所有权/不要移动它.