c++ - std::string::substr 成员函数的复杂度是多少？

Question

std::string::substr成员函数的复杂度是多少？它是由标准定义的还是由实现定义的？

Answer 1

一个简单的实现将是 O(k)，其中 k 是结果子字符串的长度。std::string 不支持写时复制。如果您想要 O(1) 子字符串操作，请使用诸如Rope之类的数据结构。

Answer 2

C++11 标准没有定义substr21.4.7.8 或我能找到的任何其他地方的性能特征。在实践中，您几乎可以肯定地期望O(n)性能与n结果的长度有关。

Answer 3

这就是标准所要说的：

n3242, 21.4.7.8

1. 要求：pos <= size()
2. 抛出：out_of_range如果pos > size()
3. 效果：确定要复制的字符串的有效长度rlen为n和size() - pos
4. 回报：basic_string<charT,traits,Allocator>(data()+pos,rlen)。

所以答案是否定的，复杂性没有定义。

编辑：根据 n3242 更正，pos > size not pos >= size