c++ - std::string size() 是 O(1) 操作吗？

Question

std::string size() 是 O(1) 运算吗？

我使用的 STL 的实现是 VC++ 内置的

Answer 1

如果您要问 MSVC 的 string::size() 实现是否具有恒定的复杂性，那么答案是肯定的。但是Don Wakefield提到了 C++ 标准 23.1 中的表 65，它说 size() 的复杂性应该遵循“注释 A”中所说的内容。注 A 说:

Those entries marked ‘‘(Note A)’’ should have constant complexity.

但是，这并不意味着这些条目应该具有恒定的复杂性。标准使用非常具体的术语，“应该”意味着它不是强制性的。

'Note A' 被添加到标准中，以安抚那些认为应该允许 size() 具有线性复杂度的人，因此在容器被放置时不需要保持大小修改。

所以你不能依赖 size() 具有恒定的复杂性，但老实说，我不确定是否有任何实现没有恒定的 string::size( )。