c++ - 如何在 O(1) 中从 C++ 中的 'string' 中删除终端字符？

Question

更正式地说，令str 为所讨论的字符串，并令其长度为l。我知道使用 substr 函数可以轻松完成上述操作，如下所示:

• 删除第一个字符 - str.substr(1)
• 删除最后一个字符 - str.substr(0,l-1)

但根据this页面，上述方法在 O(l) 中完成。

有没有办法在 O(1) 中实现相同的目标？

编辑:在您将此问题标记为重复之前，请注意我要求O(1) 实现以删除字符串的终端字符。这个问题似乎是重复的问题的答案都没有做出任何努力来回答这个问题，显然是因为那个问题没有要求它。

Answer 1

substr 函数不会删除字符。您调用该函数的字符串不会被修改，因此所有字符都保持不变。尽管如此，调用它以选择包含除终止字符以外的所有字符的子字符串所需的时间将为 O(n)，因为它涉及复制所有其他字符。

从字符串中删除一个字符所需的时间在于移动所有后续字符以替换删除的字符，很像 substr 中发生的复制。一个字符串中一般有n个字符，所以删除任意一个字符的复杂度为O(n)。

没有固定时间的方法来删除任意长度字符串的第一个字符。从字符串的 end 删除固定数量的字符 C 可以在常数时间内完成，因此删除最后一个字符 (C> = 0) 是 O(1)。

如果您经常需要在序列的末端添加或删除元素，您可能会考虑更适合该操作的数据结构。 list 和 deque 都适用于此。