std::string size() 是 O(1) 运算吗?
std::string size() 是 O(1) 运算吗?
Is std::string size() a O(1) operation?
我使用的STL实现是VC++自带的
The implementation of STL I'm using is the one built into VC++
推荐答案
如果您问 MSVC 的 string::size() 实现是否具有恒定复杂性，那么答案是肯定的.但是 Don Wakefield 提到了 C++ 标准 23.1 中的表 65说 size() 的复杂性应该遵循注释 A"中所说的.注释 A 说:
If you're asking if MSVC's implementation of string::size() has constant complexity, then the answer is yes. But Don Wakefield mentioned Table 65 in 23.1 of the C++ Standard where it says that the complexity of size() should follow what's said in 'Note A'. Note A says:
那些标记为(注 A)"的条目应该具有恒定的复杂性.
Those entries marked ‘‘(Note A)’’ should have constant complexity.
然而，这并不意味着这些条目应该具有恒定的复杂性.标准使用非常具体的术语，应该"意味着它不是强制性的.
However, that does not mean that those entries shall have constant complexity. Standards use very specific terminology, and "should" means that it is not mandatory.
'Note A' 被添加到标准中是为了安抚那些认为应该允许 size() 具有线性复杂性的人修改.
'Note A' was added to the standard specifically to appease those who believed that size() should be allowed to have linear complexity so it would not be necessary to keep the size when the containers were modified.
所以你不能依赖 size() 具有恒定的复杂性，但老实说，我不确定是否有任何实现没有恒定的 string::size().
So you can't rely on size() having constant complexity, but I'm honestly not sure if there are any implementations that do not have a constant string::size().
相关文章