问字符串类擦除成员函数的C++时空复杂度

EN

作为stated in the comments，该标准没有为许多basic_string函数(包括erase)指定任何复杂性要求。这在一定程度上是因为历史上有许多不同的实现策略(最著名的是，写入时复制在C++98时代很流行)，所以委员会不愿太精确地指定任何东西。

典型的现代实现的basic behavior非常类似于vector<char>：插入和删除在结束时很便宜(通过分期重新分配)，在开始时很昂贵。处理小字符串时根本不需要内存分配(通过重用指针的空间来存储字符)。这意味着，如果字符串变得非常短，擦除可能会导致复制整个字符串(但复制成本很低)。这也意味着迭代器和引用是无效的比vector更容易。

没有任何算法在string上执行得更好，但是有一些替代的数据结构具有不同的性能特征。rope的典型之处在于，它提供的访问速度稍慢，但插入和删除速度要快得多。