时间戳

首页 > 解决方案 > 压扁和收集切片的效率

rust - 压扁和收集切片的效率

问题描述

如果有人在.flatten().collect::<Box<[T]>>()上使用标准Iterator<Item=&[T]> where T: Copy，是否：

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

标签： rustiteratorsliceflattenmemory-efficient

解决方案

Box<[T]>没有实现FromIterator<&T>，所以我假设你的实际内部迭代器是产生拥有T的东西。

FromIterator<T>forBox<[T]> 转发到 Vec<T>，它用于size_hint()为lower+ 1 个项目保留空间，并随着它的增长而重新分配（根据需要移动元素）。所以问题是，Flatten<I>return 是为了size_hint什么？

Iterator::size_hintfor的实现Flatten<I> 转发到内部 structFlattenCompat<I>，这有点复杂，因为它支持双端迭代，但如果外部迭代器没有提前或耗尽，最终会返回(0, None)。

所以你的问题的答案是：它做一些效率较低的事情。即，（除非您已经调用next或next_back迭代器至少一次）它创建一个空Vec<T>并根据使用的任何增长策略逐步增长它Vec（未指定，但文档保证会导致O(1)amortizedpush）。

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

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

推荐阅读