Reference to element in vector

Question

I'm having trouble giving a struct a member variable that is a reference to another type. Here is my struct and implementation:

struct Player<'a> {
    current_cell: &'a Cell,
}

impl<'a> Player<'a> {
    pub fn new(starting_cell: &'a Cell) -> Player<'a> {
        Player { current_cell: starting_cell }
    }
}

The player has a reference to the current Cell that they are in. Here is my Game struct and its implementation:

struct Game {
    is_running: bool,
    cells: Vec<Cell>,
}

impl Game {
    pub fn new() -> Game {
        let cells = construct_cells();
        let player = Player::new(cells[0]);

        Game {
            is_running: false,
            cells: cells,
        }
    }
}

cells is a vector of Cells. When I create the game, I create a vector of cells in construct_cells() and then I start the player at the first cell. The error I am getting is:

expected &Cell, found struct `Cell`

I can see that I'm not passing a reference when I create the Player, but if I change the parameter to &cells[0] then it yells at me for borrowing the entire vector and then trying to use it again when I create the Game struct. So what's going on? How do I just give the player a reference to a Cell?

Answer 1

Despite appearances, storing the reference to an object stored in a mutable vector is not safe. Vectors can grow; once a vector's length matches its capacity, it can only grow by allocating a larger array and moving all objects inside it to the new location. Existing references to its elements would be left dangling, so Rust doesn't allow that. (Also, a vector can be shrunk or cleared, in which case any references to its elements will obviously point to deallocated memory.) The same problem would exist with a C++ std::vector.

There are several ways around it. One is to switch from a direct reference to Cell to a safe back-reference that consists of a back-pointer to the Game and an index to the vector element:

struct Player<'a> {
    game: &'a Game,
    cell_idx: usize,
}

impl<'a> Player<'a> {
    pub fn new(game: &'a Game, cell_idx: usize) -> Player<'a> {
        Player { game, cell_idx }
    }
    pub fn current_cell_name(&self) -> &str {
        &self.game.cells[self.cell_idx].name
    }
}

Compilable example at the playground.

That has the downside that it doesn't allow adding cells except by appending them, because it would invalidate players' indices. It also requires bounds-checking on every access to a cell property by Player. But Rust is a systems language that has references and smart pointers - can we do better?

The alternative is to invest a bit of additional effort to make sure that Cell objects aren't affected by vector reallocations. In C++ one would achieve that by using a vector of pointers-to-cell instead of a vector of cells, which in Rust one would use by storing Box<Cell> in the vector. But that wouldn't be enough to satisfy the borrow checker because shrinking or dropping the vector would still invalidate the cells.

This can be fixed using a reference-counted pointer, which will allow the cell to both survive the vector growing (because it is allocated on the heap) and shrinking so it no longer includes it (because it is not owned exclusively by the vector):

struct Game {
    is_running: bool,
    cells: Vec<Rc<Cell>>,
}

impl Game {
    fn construct_cells() -> Vec<Rc<Cell>> {
        ["a", "b", "c"]
            .iter()
            .map(|n| {
                Rc::new(Cell {
                    name: n.to_string(),
                })
            })
            .collect()
    }

    pub fn new() -> Game {
        let cells = Game::construct_cells();

        Game {
            is_running: false,
            cells,
        }
    }

    // we could also have methods that remove cells, etc.
    fn add_cell(&mut self, cell: Cell) {
        self.cells.push(Rc::new(cell));
    }
}

At the cost of an additional allocation for each Cell (and an additional pointer dereference from Game to each cell), this allows an implementation of Player more efficient than index:

struct Player {
    cell: Rc<Cell>,
}

impl Player {
    pub fn new(cell: &Rc<Cell>) -> Player {
        Player {
            cell: Rc::clone(cell),
        }
    }
    pub fn current_cell_name(&self) -> &str {
        &self.cell.name
    }
}

Again, compilable example at the playground.