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 说：

那些标记为“（注 A）”的条目应该具有恒定的复杂性。

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

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

因此，您不能依赖于size()具有恒定的复杂性，但老实说，我不确定是否有任何实现没有恒定的string::size().

Answer 2

这是为 msvc++ 回答该问题的一种简单方法。

在项目中编写一些代码：

string happy;
happy.size();

突出显示 .size 调用，右键单击，转到定义。

在我的安装（vs2005sp1）上，这会将我发送到 xstring:1635，如下所示：

size_type __CLR_OR_THIS_CALL size() const
    {   // return length of sequence
    return (_Mysize);
    }

所以看起来字符串有一个名为 _Mysize 的成员，它只是返回它。

换句话说，这是一个 O(1) 的实现。

Answer 3

是的，std::string::size() 是 O(1)。

Answer 4

请参阅标准第 23.1 节中的表 65。“a.size()”被列为“（注 A）”，表示“那些条目......应该具有恒定的复杂性”。

第 21.3 节说字符串符合序列 (23.1) 的要求，事实上，size() 是常数时间。

Answer 5

对于字符串，对于所有不使用绳索⁽¹⁾size()的字符串实现，操作必须是常量。标准中没有明确要求要求操作是，最接近的是应该是常数时间的通用要求，但这为任何其他复杂性度量留下了空间。O(1)size()

那么为什么必须是 O(1) 呢？

这是因为无法从字符串本身的内容计算大小。在 C 中，您使用 NUL 终止符来确定字符串的结尾，而在 C++ 中，NUL 与字符串中的任何其他字符一样有效。由于字符串的大小不能从内容⁽²⁾中计算出来，因此必须在外部进行处理，与字符串的实际大小无关。

⁽¹⁾ C++03 标准允许实现使用绳索作为字符串的实现，但事实是标准库的当前实现都没有使用它们。

⁽²⁾如果实现使用绳索，则操作可以通过构建绳索的块的数量来取决于大小，如果块通过链表或类似结构链接，或者如果它们被允许具有不同的尺寸。但是我知道的任何标准库实现中都没有使用绳索。

Answer 6

STL 保证容器的性能至少为 O(N)，但是包括 std::string 在内的许多容器可以将其实现为 O(1) 并且将。通常它要么返回一个简单的变量，要么执行 _End - _Begin 之类的操作并返回它。

Answer 7

的复杂性size() 应遵循“注 A”。这意味着，它应该具有恒定的复杂性，即 O(1)。虽然，我不确定实现，但 C++ 中的迭代器确实具有指向 STL 容器的关联操作，如 begin() 和 end()。这些操作具有恒定的时间复杂度，因为它们是容器要求。这意味着它begin() - end()也具有恒定的复杂性。这意味着，size()是 O(1) 操作。

Answer 8

size_type __CLR_OR_THIS_CALL size() const

{   // return length of sequence

    return (_Mysize);

}

所以最终可能会是这样，但你永远无法确定。