创建一个包含多个另一个字符串副本的字符串的最佳方法

Question

我将创建一个函数，该函数将以字符串和整数作为参数，并返回包含给定次数重复字符串参数的字符串。

例如：

std::string MakeDuplicate( const std::string& str, int x )
{
    ...
}

调用MakeDuplicate("abc", 3);将返回"abcabcabc"。

我知道我可以通过循环x次来做到这一点，但我相信一定有更好的方法。

- Richard

---

为什么是123？你的意思不是应该用MakeDuplicate("abc", 3)吗？ - Pace

你怎么这么确定一定有更好的方法呢？ - Daniel Daranas

只是因为你在想一个标准的方法，所以并没有。有一个构造函数可以重复一个单一字符 n 次。std::string s(9, 'A'); - GManNickG

Answer 1

我认为循环没有问题，只需首先进行储备(reserve)：

std::string MakeDuplicate( const std::string& str, int x )
{
    std::string newstr;
    newstr.reserve(str.length()*x); // prevents multiple reallocations

    // loop...

    return newstr;
}

- luke

---

谢谢MikeSep，发现得好。已经更正了。 - luke

循环是没问题的，只是其中一件事情让人感觉好像有更明确的方法来实现它，但也许并没有。 - Richard

我认为在C++中没有一种惯用的方法来做你所要求的事情。 - luke

一种稍微更高效的版本可能是先复制实际字符串，然后循环 x-1 次。虽然这需要检查 0 以避免不必要的复制。 - Matthieu M.

Matthieu M. - 我曾经考虑过这个问题，但你仍然可能会进行两次内存分配：一次是在构造字符串时，另一次是将其设置为最大大小。整体上的一次预先分配可能更快。 - luke

Answer 2

在某个时候，必须使用循环。你可能能够通过一些花哨的语言习惯来隐藏循环，但最终你必须循环。

- John Weldon

Answer 3

对于小的 'x' 值，简单循环是最好的选择。对于较大的 'x' 值和相对较短的 'str'，我们可以考虑通过重用已经连接好的字符串来找到一种“更聪明”的解决方案。

std::string MakeDuplicate( const std::string& str, unsigned int x ) {

  std::string newstr;
  if (x>0) {
    unsigned int y = 2;
    newstr.reserve(str.length()*x);  
    newstr.append(str);
    while (y<x) {
      newstr.append(newstr);
      y*=2;
    }
    newstr.append(newstr.c_str(), (x-y/2)*str.length());
  }
  return newstr;
}

或者类似这样：o)，（我认为可以用更好的方式来表达，但思路是一致的）。

编辑：我对此很感兴趣，并在我的笔记本上使用Visual Studio进行了三种解决方案的比较测试（重用版本、带预分配的简单循环、不带预分配的简单复制与循环-1）。结果如预期：对于小x（<10），预分配版本通常最快，没有预分配略慢，在x较大时，“重用”版本的速度提升非常显著（log n vs n复杂度）。不错，我只是想不到任何真正需要使用它的问题 ：o）

- MaR

Answer 4

有一种替代循环的方法，它叫做递归，而在递归中，尾递归是最好的，因为你可以理论上一直使用它 -- 就像一个循环 :D

p.s.，尾递归经常被视为循环的语法糖 -- 然而，在过程式语言（C++）的情况下，编译器通常无法优化尾递归，因此你可能会耗尽内存（但如果你写了一个会耗尽内存的递归，那么你就有更大的问题了）:D

请再踩我一次！！

显然，递归不是计算机科学中用于相同任务的构造。

- Hassan Syed

---

虽然它很优雅，但当有人键入MakeDuplicate("非常长的字符串……", 200000)时，他们会哭的 :) - Skurmedel

循环可以并行化，但递归不能。 - Hamish Grubijan

@lp 嗯，我同意（编译器优化），但如果你用另一个递归包装所涉及的递归，你可以并行化......根据我的经验，这样的代码更加健壮——想想 Erlang :D - Hassan Syed

C++通常不会优化尾递归。使用这种方案可能会导致栈溢出。 - Billy ONeal

为什么会被踩？这是一个理想的回答，可以展示为什么优雅的递归解决方案不适用（至少对于较大的x）。 - MaR