Space C++ 中 str.substr() 的复杂性

Question

str.substr() 函数的 space 复杂度是多少？它与 str.erase() 相比如何？

想知道，因为我是运行 leetcode 上的代码，并且在使用 substr 函数时使用了 150MB 的内存：

num = num.substr(1,num.size());

一旦我删除了这个函数并使用了擦除函数，同时我的代码中没有任何其他更改，内存使用量下降到 6.8MB。具有擦除功能的更新代码：

num = num.erase(0,1);

Answer 1

num = num.substr(1,num.size());

substr 创建了一个没有第一个字符的字符串副本，所以在调用后少了 1 个字符，你有（几乎）两倍的初始字符串

⁽¹⁾ ~~字符串是共享的，所以~~赋值后删除初始字符串~~如果是未从其他地方引用，~~ 但在分配之前，您的内存中有两个版本需要内存。

num = num.erase(0,1);

修改字符串，执行时只需要一个版本的字符串

注意这和做的一样

num.erase(0,1);

(1)：来自 Pete Becker 的评论，因为 C++11 明确不允许共享 std::basic_string 的内部表示

Answer 2

Space complexity of str.substr() in C++

从技术上讲，这取决于 str 的类型。

按理说，除了输出大小之外，不应有任何开销。 std::string 的 space 复杂度与字符串的长度成线性关系。

Space complexity of str.substr() in C++