Prepend std::string

Question

如何高效地在 std::string 中进行前置添加？是否值得编写一个完整的函数来实现，还是只需要使用 1 - 2 行代码？我没有看到任何与 std::string::push_front 相关的信息。

- zeboidlund

---

你为什么不能像这样做 s = a + s？ - Mike Bailey

@GWW：那确实更高效吗？ - Lightness Races in Orbit

你的意思是在一个 std::string 前面添加内容吗？那么要添加什么呢？ - Lightness Races in Orbit

@GWW：是的，可能只需要一次。这怎么比循环遍历原始字符串并逐字节复制数据更糟糕呢？我不知道有没有低级API函数可以反转内存块中的数据。 - Lightness Races in Orbit

@GWW：好的。这仍然不太可能；你最好知道需要多少个新字符，然后在单个字符串中一次性执行它们。反转不太可能会给你任何帮助。特别是因为你还需要预先反转原始字符串。 - Lightness Races in Orbit

Answer 1

实际上有一个类似于不存在的 std::string::push_front 的函数，见下面的示例。

---

std::string::insert 的文档

#include <iostream>
#include <string>

int
main (int argc, char *argv[])
{
  std::string s1 (" world");
  std::string s2 ("ello");

  s1.insert (0,     s2); // insert the contents of s2 at offset 0 in s1
  s1.insert (0, 1, 'h'); // insert one (1) 'h'        at offset 0 in s1

  std::cout << s1 << std::endl;
}

输出：

hello world

由于将一个字符串与数据拼接可能需要重新分配内存并复制/移动现有数据，因此您可以通过使用 std::string::reserve（预先分配更多内存）来摆脱重新分配部分，从而获得一些性能优势。

不幸的是，数据的复制/移动是不可避免的，除非您定义自己的自定义类，像std::string一样分配一个大缓冲区，并将第一个内容放在该内存缓冲区的中心。

然后，如果缓冲区足够大，您就可以在不进行重新分配和移动数据的情况下同时添加和插入数据。当然，仍然需要从源复制到目标。

如果你经常需要在开头添加数据，那么一个好的选择是将字符串以相反的顺序存储，并在需要时（如果更少）将其翻转。

- Filip Roséen - refp

---

我还要补充一点，如果你需要在一个字符串前添加多个项，可以先将这些项附加到该字符串的末尾，然后使用<algorithm>中的std::rotate将它们旋转到字符串前面，以避免二次时间性能。 - Don Reba

Answer 2

myString.insert(0, otherString);

让标准模板库的编写者担心效率问题；利用他们的工作成果，而不是重新编写轮子。

这种方式既能保证效率，又能充分利用他们的工作成果。

只要你使用的STL实现经过深思熟虑，你就会拥有高效的代码。如果你正在使用编写不好的STL，那么你肯定会遇到更大的问题 :)

- matiu

---

聪明的实现无法挽救低效的算法。 - Ben Voigt

Answer 3

如果您正在使用std::string::append，您应该意识到以下代码是等价的：

std::string lhs1 = "hello ";
std::string lhs2 = "hello ";
std::string rhs = "world!";

lhs1.append(rhs);
lhs2 += rhs; // equivalent to above
// Also the same:
// lhs2 = lhs2 + rhs;

同样地，“prepend”相当于以下内容：

std::string result = "world";
result = "hello " + result;
// If prepend existed, this would be equivalent to
// result.prepend("hello");

请注意，尽管上述操作可行，但效率不高。

- Mike Bailey

---

有人知道为什么这个回答被踩了吗？它的说法有错误吗？作为五年后的读者，我们应该从未经解释的踩数中推断出什么呢？这样做对任何人都没有好处。最终能否有人详细说明一下？ - underscore_d

如另一个答案所述，使用 operator+ 会创建字符串的副本。相比之下，使用 insert() 可以原地操作（在可能重新分配字符串缓冲区之后）。对于这些小例子来说，这并不重要，但对于巨大的字符串来说可能很重要。在 C++11 中，也可以使用 "result = "hello " + std::move(result)` 来避免复制。 - amon

@amon 谢谢！经过两年的进一步学习和你的指出，现在这似乎很明显了，但实际上还是值得说一下的。move()技巧有时候确实很方便，但C++是否确实保证使用.insert()会被优化，还是只有库实现者聪明才能做到呢？我认为应该是后者。 - underscore_d

Answer 4

有一个重载的 string operator+ (char lhs, const string& rhs);，因此您只需执行 your_string 'a' + your_string，以模仿 push_front。

这不是就地操作，而是创建一个新字符串，所以不要期望它非常高效。对于可能更有效的解决方案，请使用 resize 收集空间，std::copy_backward 将整个字符串后移一位，并在开头插入新字符。

- Alexander Gessler

---

不应该使用 std::string::resize 来“收集更多空间”，该函数会在需要时使内部缓冲区变大，这是正确的。但它也会用 char()（也称为 NULL（即值0））填充当前字符串。请参见此 codepad paste 进行演示。 - Filip Roséen - refp

Answer 5

问题在于效率：在字符串的开头插入更昂贵，因为它需要重新分配和移动现有字符。

如果您只是要在字符串前面添加内容，则最有效的方法是追加，然后反转字符串，或者更好的方法是按相反的顺序遍历字符串。

string s;
for (auto c: "foobar") {
  s.push_back(c);
}
for (auto it=s.rbegin(); it!=s.rend(); it++) {
  // do something
}

如果您需要同时进行前置和后置操作，我建议使用一个双端队列deque，然后从中构造一个字符串。 双端队列支持在开头和结尾进行O(1)的插入和删除操作。

deque<char> dq;
dq.push_front('f');
dq.push_back('o');
dq.push_front('o');
string s {dq.begin(), dq.end()};

- stwykd