是否有更有效的方法来调整表示为Vec ？

Question

我有一个包含由单个Vec<u8>表示的二维网格的结构，因为wasm_bindgen不支持<Vec<Vec<T>>。例如，网格：

0 1 
2 3

与元素Vec<u8>一起存储为[0, 1, 2, 3]。

我希望能够调整网格的宽度；如果新宽度较小，则网格应从右侧删除列；如果新宽度较大，则网格应使用零填充新列。可能必须在Vec中的多个位置添加或删除项目。

要设置网格的宽度，我将Vec分成块，将块变成向量，调整向量的大小，并弄平向量。

struct Matrix {
    grid: Vec<u8>,
    width: usize,
}

impl Matrix {
    pub fn set_width(&mut self, new_width: usize) {
        self.grid = self
            .grid
            .chunks_exact(self.width)
            .flat_map(|chunk| {
                let mut chunk_vec = chunk.to_vec();
                chunk_vec.resize(new_width, 0);
                chunk_vec
            })
            .collect();

        self.width = new_width;
    }
}

是否有更有效的方法？我认为这些块可能会在较大的网格大小上分配大量内存，因为它们都变成了Vec。

---

设置高度要容易得多，因为将在Vec的末尾追加或删除行：

pub fn set_height(&mut self, new_height: usize) {
    self.grid.resize(self.width * new_height, 0);
    self.height = new_height;
}

Answer 1

为了简单地减少分配数量，您可以使传递给flat_map的闭包返回一个迭代器，而不是Vec：

pub fn set_width(&mut self, new_width: usize) {
    use std::iter::repeat;
    self.grid = self
        .grid
        .chunks_exact(self.width)
        .flat_map(|chunk| chunk.iter().copied().chain(repeat(0)).take(new_width))
        .collect();

    self.width = new_width;
}

[对于每个块，我们创建一个迭代器，该迭代器生成块的copied内容，后跟repeat ed字符串0，然后将其（take）截断为总大小new_width。这不需要创建任何Vec来存储中间结果，因此它分配的次数更少...最有可能。

此代码很好，但稍作更改我们可以做得更好。 FlatMap无法知道内部迭代器的大小，因此它没有给出有用的size_hint（有关类似示例，请参见Efficiency of flattening and collecting slices）。这意味着Vec开始为空，可能必须多次增长（重新分配并复制其内容），然后才能足够大。相反，我们可以先使用Vec::with_capacity保留正确的空间量，然后使用extend向量而不是collect放入其中：

pub fn set_width(&mut self, new_width: usize) {
    use std::iter::repeat;
    let mut new_grid = Vec::with_capacity(self.grid.len() / self.width * new_width);
    for chunk in self.grid.chunks_exact(self.width) {
        new_grid.extend(chunk.iter().copied().chain(repeat(0)).take(new_width));
    }
    self.grid = new_grid;

    self.width = new_width;
}

也可以在最多一次重新分配的情况下就地调整网格大小（通常重新使用现有的网格）。但是，该算法要复杂得多。以上是我写set_width的方式，除非被证明是瓶颈。