rust - 展平收片效率

Question

如果使用标准 .flatten().collect::<Box<[T]>>()在 Iterator<Item=&[T]> where T: Copy 上, 做:

• 执行单一分配；和
• 使用memcpy将每个项目复制到目的地

还是它做了一些效率较低的事情？

Answer 1

Box<[T]>不执行 FromIterator<&T> ，所以我假设您的实际内部迭代器是产生 owned T 的东西

FromIterator<T>对于 Box<[T]> forwards to Vec<T> ，这uses size_hint() 为lower预留空间+ 1 项目，并在超出该项目时重新分配(根据需要移动元素)。所以问题是，Flatten<I> 是什么？返回 size_hint ？

执行Iterator::size_hint对于 Flatten<I> forwards to the internal struct FlattenCompat<I> ，这有点复杂，因为它支持双端迭代，但最终returns (0, None) if the outer iterator has not been advanced or exhausted .

所以你的问题的答案是:它做了一些效率较低的事情。即，(除非您已经在迭代器上至少调用过一次 next 或 next_back)它会创建一个空的 Vec<T>。并根据任何增长策略逐步增长 Vec使用(未指定，但 guaranteed by the documentation to result in O(1) amortized push )。

这不是人为限制；这是基本的方式 Flatten作品。预先计算展平迭代器大小的唯一方法是用尽外部迭代器并将所有内部迭代器相加 size_hint秒。这是一个坏主意，因为它并不总是有效(内部迭代器可能不会返回有用的 size_hint s)，而且还因为您还必须找到一种方法来在耗尽外部迭代器之后保留内部迭代器；对于通用迭代器适配器，没有可接受的解决方案。

如果您对特定迭代器有所了解，可以知道最终大小应该是多少，您可以通过调用 Vec::with_capacity 自行保留分配。并使用 Extend 从 flatten 填充它ed 迭代器，而不是使用 collect .