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

Question

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

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

我试过使用简单的 for 循环以及迭代器、排出、保留和过滤，但我一直运行解决自我（玩家）会被多次可变借用的问题，因为修改 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

如果我没理解错的话，你有两个问题：

如何将 Vec 拆分为两个 Vec（一个满足预选条件，另一个不满足预选条件）
没有内存开销是否可行

有多种方法可以将 Vec 分成两个（或更多）。

您可以使用 Iteratator::partition，这将为您提供两个可以进一步使用的不同迭代器。
有一个不稳定的 Vec::drain_filter 函数，它在 Vec 本身
使用 splitn（或 splitn_mut），这会将您的 Vec/slice 拆分为 n（在您的情况下为 2）迭代器

看你想做什么，所有的解决方案都适用并且很好用。

没有内存开销是否可行？不适用于上述解决方案，因为您需要创建第二个 Vec 来容纳过滤后的项目。但是有一个解决方案，即你可以 "sort" Vec 其中前半部分将包含满足谓词（例如未过期）的所有项目，而后半部分将不符合谓词（已过期）。您只需要计算满足谓词的项目数量。

然后您可以使用 split_at（或 split_at_mut）将 Vec/slice 分成两个不同的部分。之后你可以调整 Vec 的大小到好的项目的长度，其他的将被删除。

Answer 2

主要问题是您正在借用 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.

Answer 3

最佳答案是this one in C++。

[O]rder the indices vector, create two iterators into the data vector, one for reading and one for writing. Initialize the writing iterator to the first element to be removed, and the reading iterator to one beyond that one. Then in each step of the loop increment the iterators to the next value (writing) and next value not to be skipped (reading) and copy/move the elements. At the end of the loop call erase to discard the elements beyond the last written to position.

Rust 对您的特定问题的适应是将删除的项目移出向量，而不是仅仅覆盖它们。

另一种方法是使用链表而不是向量来保存您的 Effect 实例。

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

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

vector

rust

borrowing