Iterator::collect 分配的内存量是否与 String::with_capacity 相同？

在 C++ 中，当连接一堆字符串时（其中每个元素的大小大致已知），通常会预先分配内存以避免多次重新分配和移动：

std::vector<std::string> words;
constexpr size_t APPROX_SIZE = 20;

std::string phrase;
phrase.reserve((words.size() + 5) * APPROX_SIZE);  // <-- avoid multiple allocations
for (const auto &w : words)
  phrase.append(w);

同样，我在 Rust 中做到了这一点（这个块需要unicode 分段 https://crates.io/crates/unicode-segmentation crate)

fn reverse(input: &str) -> String {
    let mut result = String::with_capacity(input.len());
    for gc in input.graphemes(true /*extended*/).rev() {
        result.push_str(gc)
    }
    result
}

有人告诉我，惯用的做法是使用单个表达式

fn reverse(input: &str) -> String {
  input
      .graphemes(true /*extended*/)
      .rev()
      .collect::<Vec<&str>>()
      .concat()
}

虽然我真的很喜欢它并且想使用它，但从内存分配的角度来看，前者分配的块会比后者少吗？

我用它拆解了这个cargo rustc --release -- --emit asm -C "llvm-args=-x86-asm-syntax=intel"但它没有散布源代码，所以我不知所措。

您的原始代码很好，我不建议更改它。

原始版本分配一次：内部String::with_capacity.

第二个版本分配at least两次：首先，它创建一个Vec<&str>并通过以下方式增长它pushing &str就可以了。然后，它计算所有的总大小&strs 并创建一个新的String具有正确的尺寸。 （此代码位于the join_generic_copy中的方法str.rs https://github.com/rust-lang/rust/blob/1.38.0/src/liballoc/str.rs.) 这很糟糕，原因如下：

1. 显然，它进行了不必要的分配。
2. 字素簇可以任意大，因此中间Vec无法提前有效地调整大小——它只是从大小 1 开始并从那里开始增长。
3. 对于典型的字符串，它分配更多空间比实际需要的只是存储最终结果，因为&str大小通常为 16 字节，而 UTF-8 字素簇通常远小于此大小。
4. 迭代中间过程会浪费时间Vec获得最终尺寸，您可以从原始尺寸中获取它&str.

最重要的是，我什至不认为这个版本是惯用的，因为它collect进入临时状态Vec为了迭代它，而不仅仅是collect原始迭代器，就像您在答案的早期版本中所做的那样。此版本修复了问题 #3 并使问题 #4 变得无关紧要，但没有令人满意地解决问题 #2：

input.graphemes(true).rev().collect()

collect uses FromIterator for String，这将尝试使用 https://github.com/rust-lang/rust/blob/1.38.0/src/liballoc/vec.rs#L1921的下界size_hint来自Iterator实施Graphemes。然而，正如我之前提到的，扩展字素簇可以任意长，因此下限不能大于 1。更糟糕的是，&strs 可能为空，所以FromIterator<&str> for String不知道anything关于结果的大小（以字节为单位）。这段代码只是创建一个空的String并打电话push_str反复地在上面。

需要明确的是，这还不错！String有一个保证摊销 O(1) 插入的增长策略，因此，如果您的字符串大多很小，不需要经常重新分配，或者您不认为分配成本是瓶颈，请使用collect::<String>()如果您发现它更具可读性并且更容易推理，那么这里可能是合理的。

让我们回到原来的代码。

let mut result = String::with_capacity(input.len());
for gc in input.graphemes(true).rev() {
    result.push_str(gc);
}

This 是惯用的. collect也是惯用语，但所有collect基本上就是上面的，初始容量不太准确。自从collect没有做你想做的事，自己编写代码并不不符合习惯。

有一个稍微更简洁的迭代器版本，仍然只进行一次分配。使用extend方法，它是Extend<&str> for String:

fn reverse(input: &str) -> String {
    let mut result = String::with_capacity(input.len());
    result.extend(input.graphemes(true).rev());
    result
}

我有一种模糊的感觉extend更好，但是这两种都是编写相同代码的完全惯用的方式。你不应该重写它来使用collect，除非您觉得这更好地表达了意图and你不关心额外的分配。

Related

• 压平和收集切片的效率 https://stackoverflow.com/questions/58571612/efficiency-of-flattening-and-collecting-slices