vector - 如何在不分配内存的情况下改变并选择性地从 vec 中删除元素？

Question

我有一个包含 Effect 实例 vec 的 Player 结构。我想遍历这个 vec，减少每个 Effect 的剩余时间，然后删除剩余时间为零的任何 effect。到目前为止，一切都很好。但是，对于移除的任何效果，我还想在销毁效果实例之前将其传递给 Player 的 undo_effect() 方法。

这是游戏循环的一部分，所以我想尽可能不分配任何额外的内存。

我尝试过使用简单的 for 循环以及迭代器、drain、retain 和 filter，但我一直遇到这样的问题，即 self(玩家)会被多次可变地借用，因为修改 self.effects 需要可变借用，undo_effect() 方法也是如此。 nightly 中的 drain_filter() 在这里看起来很有用，但它是在 2017 年首次提出的，所以不要屏住呼吸。

一种确实可以编译的方法(见下文)是使用两个向量并在每个帧上交替使用它们。元素从 vec 1 pop()'ed，然后 push()'ed 到 vec 2 或适本地传递给 undo_effect()。在下一个游戏循环迭代中，方向被反转。由于每个 vec 都不会缩小，因此唯一的分配是它们变得比以前更大。我开始将其抽象为自己的结构，但想检查是否有更好(或更简单)的方法。

这个不会编译。 self.undo_effect() 调用会将 self 借用为可变的两次。

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);
    }
}

下面的代码编译正常 - 但有更好的方法吗？

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

有没有不需要不必要的内存分配的迭代器版本？我可以只为删除的元素分配内存，因为这种情况会少得多。

迭代器会比 pop()/push() 版本更高效吗？

编辑 2020-02-23:我最终回到了这个问题上，我发现了一个稍微更稳健的解决方案，类似于上面的解决方案，但没有需要 target_index 字段的危险。

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);
        }
    }
}

由于 self.effects_cache 在此方法之外未使用，并且不需要 self.effects_cache 预先具有任何特定值，因此其余代码可以简单地使用 self.effects 并且它将始终是最新的。

Answer 1

主要问题是您正在借用 Player 的字段 (effects) 并在借用该字段时尝试调用 undo_effect。如您所述，这不起作用。

您已经意识到可以兼顾两个向量，但实际上您只能兼顾一个(永久)向量:

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);
    }
}

这不会分配，因为 Vec 的默认构造函数不分配。

另一方面，双向量解决方案可能更有效，因为它允许单次传递 self.effects 而不是两次。 YMMV.