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

Question

我想知道是否有人知道 C++ string::erase 函数的实现及其复杂性。我知道 C++ 字符串是一个字符对象。我假设它不会分配和创建一个新的字符对象，然后从旧字符串 O(n) 和 O(n) 空间复制字符。它是否在字符 O(n) 和 O(1) 空间上移动？我查看了 cplusplus.com 和 Bjarne Stroustrup 的书，但没有找到答案。有人可以指出我实现它的源代码或知道答案吗？

谢谢！

Answer 1

正如评论中所述，该标准没有为许多basic_string功能（包括erase）指定任何复杂性要求。这部分是因为历史上有许多不同的实现策略（最著名的是写时复制在 C++98 时代流行），所以委员会不愿意太精确地指定任何内容。

典型的现代实现的基本行为非常类似于vector<char>：插入和删除在最后（通过摊销重新分配）很便宜，而在开始时很昂贵。处理小字符串时根本不需要内存分配（通过重用指针的空间来存储字符）。这意味着，如果整个字符串变得很短，则擦除可能会导致复制整个字符串（但复制很便宜）。这也意味着迭代器和引用比 with 更容易失效vector。

没有任何算法在 a 上表现更好string，但有具有不同性能特征的替代数据结构。该绳子是在这些典型的，因为它提供了一个访问速度较慢，但速度更快的插入和删除。