How do I mutate and optionally remove elements from a vec without memory allocation?

Question

I have a Player struct that contains a vec of Effect instances. I want to iterate over this vec, decrease the remaining time for each Effect, and then remove any effects whose remaining time reaches zero. So far so good. However, for any effect removed, I also want to pass it to Player's undo_effect() method, before destroying the effect instance.

This is part of a game loop, so I want to do this without any additional memory allocation if possible.

I've tried using a simple for loop and also iterators, drain, retain, and filter, but I keep running into issues where self (the Player) would be mutably borrowed more than once, because modifying self.effects requires a mutable borrow, as does the undo_effect() method. The drain_filter() in nightly looks useful here but it was first proposed in 2017 so not holding my breath on that one.

One approach that did compile (see below), was to use two vectors and alternate between them on each frame. Elements are pop()'ed from vec 1 and either push()'ed to vec 2 or passed to undo_effect() as appropriate. On the next game loop iteration, the direction is reversed. Since each vec will not shrink, the only allocations will be if they grow larger than before. I started abstracting this as its own struct but want to check if there is a better (or easier) way.

This one won't compile. The self.undo_effect() call would borrow self as mutable twice.

struct Player {
    effects: Vec<Effect>
}

impl Player {
    fn update(&mut self, delta_time: f32) {
        for effect in &mut self.effects {
            effect.remaining -= delta_time;
            if effect.remaining <= 0.0 {
                effect.active = false;
            }
        }

        for effect in self.effects.iter_mut().filter(|e| !e.active) {
            self.undo_effect(effect);
        }

        self.effects.retain(|e| e.active);
    }
}

The below compiles ok - but is there a better way?

struct Player {
    effects: [Vec<Effect>; 2],
    index: usize
}

impl Player {
    fn update(&mut self, delta_time: f32) {
        let src_index = self.index;
        let target_index = if self.index == 0 { 1 } else { 0 };

        self.effects[target_index].clear(); // should be unnecessary.
        while !self.effects[src_index].is_empty() {
            if let Some(x) = self.effects[src_index].pop() {
                if x.active {
                    self.effects[target_index].push(x);
                } else {
                    self.undo_effect(&x);
                }
            }
        }

        self.index = target_index;
    }
}

Is there an iterator version that works without unnecessary memory allocations? I'd be ok with allocating memory only for the removed elements, since this will be much rarer.

Would an iterator be more efficient than the pop()/push() version?

EDIT 2020-02-23: I ended up coming back to this and I found a slightly more robust solution, similar to the above but without the danger of requiring a target_index field.

std::mem::swap(&mut self.effects, &mut self.effects_cache);
self.effects.clear();
while !self.effects_cache.is_empty() {
    if let Some(x) = self.effects_cache.pop() {
        if x.active {
            self.effects.push(x);
        } else {
            self.undo_effect(&x);
        }
    }
}

Since self.effects_cache is unused outside this method and does not require self.effects_cache to have any particular value beforehand, the rest of the code can simply use self.effects and it will always be current.

Matthieu M. Matthieu M. · Accepted Answer · 2019-08-06T13:12:47

The main issue is that you are borrowing a field (effects) of Player and trying to call undo_effect while this field is borrowed. As you noted, this does not work.

You already realized that you could juggle two vectors, but you could actually only juggle one (permanent) vector:

struct Player {
    effects: Vec<Effect>
}

impl Player {
    fn update(&mut self, delta_time: f32) {
        for effect in &mut self.effects {
            effect.remaining -= delta_time;
            if effect.remaining <= 0.0 {
                effect.active = false;
            }
        }

        //  Temporarily remove effects from Player.
        let mut effects = std::mem::replace(&mut self.effects, vec!());

        //  Call Player::undo_effects (no outstanding borrows).
        //  `drain_filter` could also be used, for better efficiency.
        for effect in effects.iter_mut().filter(|e| !e.active) {
            self.undo_effect(effect);
        }

        //  Restore effects
        self.effects = effects;

        self.effects.retain(|e| e.active);
    }
}

This will not allocate because the default constructor of Vec does not allocate.

On the other hand, the double-vector solution might be more efficient as it allows a single pass over self.effects rather than two. YMMV.

How do I mutate and optionally remove elements from a vec without memory allocation?

3 Answers