Existe-t-il un moyen idiomatique de conserver des références à des éléments d'un conteneur en croissance constante?

Question

Je suis en train d'écrire un conteneur pour les objets de type T qui donne accès à des références &T aux objets stockés (je veux éviter de faire des copies). Comme le conteneur ne cesse de croître au cours de sa durée de vie, la durée de vie des références renvoyées &T doit être la même que celle du conteneur.

Le plus proche que j'ai eu jusqu'à présent était d'utiliser Box<T> objets en interne dans mon conteneur et d'utiliser Box<T>.as_ref() pour renvoyer des références à ces objets. Ensuite, cependant, je rencontre le même problème que dans cet exemple minimal:

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 
} 

Je comprends que ce ne serait pas correct d'utiliser x dans la ligne 5 si elle avait été supprimée au cours de la v l'emprunt mutable. Mais ce n'est pas le cas ici, et ce ne sera jamais pour mon conteneur. S'il n'y a pas de moyen sûr d'exprimer cela dans Rust, comment pourrais-je "réparer" l'exemple (sans copier x)?

Answer 1

Malheureusement, il n'y a rien « prêt à l'emploi » pour votre usecase, mais vous pouvez écrire un wrapper autour Vec cela ne dangereux choses pour vous donner les fonctionnalités dont vous avez besoin tout en gardant les garanties qui a besoin de 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 
    } 
} 

les garanties que j'ai choisi est que vous ne pouvez pas indexer dans le Pusher, mais vous obtenez une référence modifiable à l'objet nouvellement poussé. Une fois pour libérer le poussoir, vous pouvez revenir à l'indexation.

Un exemple d'utilisation est

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

Le problème est que votre Vec pourrait manquer de mémoire. Si cela se produit, il doit allouer un nouveau bloc (plus grand) de mémoire, copier toutes les anciennes données et supprimer l'ancienne allocation de mémoire. À ce stade, toutes les références dans l'ancien conteneur deviendraient invalides.

Vous pouvez concevoir un rope (un Vec de Vec), où, une fois VEC intérieure est pleine, vous venez de créer un nouveau, donc jamais pointeurs invalidant juste en poussant.

Cela nécessiterait un code dangereux et une analyse très minutieuse des règles d'emprunt que vous devez suivre.

Answer 3

Comme la réponse de @ ker dit, juste parce que vous ne cultivez que d'un conteneur ne signifie pas les références restent valables, comme la mémoire peut être réaffecté.

Une autre solution si vous ne de plus en plus le conteneur est juste stocker des indices au lieu de références:

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. 
}