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）”的条目
应该具有恒定的复杂性。

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

标准中添加“注释 A”专门是为了安抚那些认为应该允许 size() 具有线性复杂度的人，这样在修改容器时就不必保留大小了。

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

Answer 2

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

Answer 3

这是回答 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 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 标准允许实现使用ropes 作为字符串的实现，但事实是标准库的当前实现都没有使用它们。

⁽²⁾ 如果实现使用绳索，则操作可以通过构造绳索的块的数量来取决于大小（如果块是通过链表或类似构造链接的），或者如果允许它们有不同的尺寸。 但据我所知，绳索并未在任何标准库实现中使用。

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);

}

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