是否有一种惯用的方法来保持对不断增长的容器元素的引用？

Question

我正在尝试为 T 类型的对象编写一个容器，它提供对存储对象的引用 &T 的访问（我想避免制作副本）。由于容器只会在其生命周期内增长，因此 returned 引用 &T 的生命周期应该与容器的生命周期相同。

到目前为止我最接近的是在我的容器内部使用 Box<T> 对象并使用 Box<T>.as_ref() 到 return 对这些对象的引用。然后，但是，我运行遇到了与这个最小示例中相同的问题：

fn main() {
    let mut v = vec![Box::new(1)]; // line 1
    let x = v[0].as_ref();         // line 2: immutable borrow occurs here
    println!("x = {:?}", x);       // line 3
    v.push(Box::new(2));           // line 4: mutable borrow occurs here -> error
    println!("x = {:?}", x);       // line 5
}

我知道如果在可变借用期间从 v 中删除了它，那么在第 5 行中使用 x 是不合理的。但这里不是这种情况，它永远不会用于我的容器。如果没有安全的方法在 Rust 中表达这个，我怎么能 "repair" 这个例子（不复制 x）？

Answer 1

问题是您的 Vec 可能运行内存不足。如果发生这种情况，它必须分配一个新的（更大的）内存块，复制所有旧数据，并删除旧的内存分配。那时所有对旧容器的引用都将失效。

您可以设计一个 rope（Vec 的 Vec），其中，一旦内部 vec 已满，您只需创建一个新的，因此永远不会使指针无效通过推动。

这将需要一些不安全的代码和对您必须遵守的借用规则的非常仔细的分析。

Answer 2

正如@ker 的回答所说，仅仅因为你只增长了一个容器并不意味着引用保持有效，因为内存可以重新分配。

如果您只是在增长容器，另一种解决方案是只存储索引而不是引用：

fn main() {
    let mut v = vec!["Foo"];    // line 1
    let x = 0;                  // line 2: just store an index.
    println!("x = {:?}", v[x]); // Use the index as needed
    v.push("bar");              // line 4: No problem, there are no references.
    println!("x = {:?}", v[x]); // line 5: use the index again.
}

Answer 3

不幸的是，您的用例没有任何 "ready to use"，但您可以围绕 Vec 编写一个包装器，它可以 unsafe 东西来为您提供所需的功能同时保持 Rust 需要的保证

struct BoxVec<T>(Vec<Box<T>>);

impl<T> BoxVec<T> {
    pub fn new() -> Self { BoxVec(Vec::new()) }
    pub fn push<'a>(&'a mut self, t: T) -> &'a mut T {
        let mut b = Box::new(t);
        let t: &'a mut T = unsafe { std::mem::transmute::<&mut T, &'a mut T>(&mut b) };
        self.0.push(b);
        t
    }
    pub fn pusher<'a>(&'a mut self) -> BoxVecPusher<'a, T> {
        BoxVecPusher(self)
    }
}

struct BoxVecPusher<'a, T: 'a>(&'a mut BoxVec<T>);

impl<'a, T> BoxVecPusher<'a, T> {
    fn push<'b>(&'b mut self, t: T) -> &'a mut T {
        let mut b = Box::new(t);
        let t: &'a mut T = unsafe { std::mem::transmute::<&mut T, &'a mut T>(&mut b) };
        (self.0).0.push(b);
        t
    }
}

我选择的保证是您无法索引到 Pusher，但您会获得对新推送对象的可变引用。一旦释放推动器，您就可以返回索引。

示例用法是

let mut v = BoxVec::new();
v.push(1);
let x = v[0];
let mut p = v.pusher();
let i = p.push(2);
p.push(3); // works now
let y = v[0]; // denied by borrow checker

Full example in the playground

是否有一种惯用的方法来保持对不断增长的容器元素的引用？

Is there an idiomatic way to keep references to elements of an ever-growing container?

lifetime

rust

borrow-checker