Есть ли идиоматический способ сохранить ссылки на элементы постоянно растущего контейнера?

Question

Я пытаюсь написать контейнер для объектов типа T, который обеспечивает доступ к хранимым объектам &T (я хочу избежать копирования). Так как контейнер только когда-либо растет в течение его срока службы, срок службы возвращаемых ссылок &T должен быть таким же, как для контейнера.

Ближайший я до сих пор должен был использовать Box<T> объектов внутри контейнера и использовать Box<T>.as_ref(), чтобы возвращать ссылки на эти объекты. Затем, однако, я столкнулся с такой же проблемой, как в этом примере минимальный:

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 
} 

Я понимаю, что это было бы несостоятельным использовать x в строке 5, если он был удален из v при изменяемом заема. Но это не тот случай, и это никогда не будет для моего контейнера. Если нет надежного способа выразить это в Rust, как я могу «восстановить» пример (без копирования x)?

Answer 1

К сожалению, нет ничего «готово к использованию» для USECASE, но вы можете написать обертку вокруг Vec что делает небезопасных материала, чтобы дать вам необходимые функции, сохраняя при этом гарантии, что Руст нуждается

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

Answer 2

Проблема в том, что у вашего Vec может закончиться память. Если это произойдет, ему необходимо выделить новый (больший) фрагмент памяти, скопировать все старые данные и удалить прежнее выделение памяти. В этот момент все ссылки в старый контейнер станут недействительными.

Вы можете спроектировать rope (а Vec из Vec), где, когда внутренний VEC полон, вы просто создать новый, таким образом, никогда не недействительности указатели просто нажатием.

Для этого потребуется некоторый небезопасный код и очень тщательный анализ правил заимствования, которые вы должны поддерживать.

Answer 3

Как говорится в ответе 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. 
}