std :: string size（）是否为O（1）操作？

StackOverflow https://stackoverflow.com/questions/256033

  •  05-07-2019
  •  | 
  •  

题

std :: string size（）是否为O（1）操作？

我正在使用的STL的实现是VC ++内置的一个

有帮助吗？

解决方案

如果你问的是MSVC的string :: size（）的实现是否具有恒定的复杂性，那么答案是肯定的。但 Don Wakefield 提到了C ++标准23.1中的表65说 size（）的复杂性应该遵循'Note A'中的说法。注意A说：

  

这些条目标有＆＃8216;＆＃8216;（注释A）＆＃8217;＆＃8217;   应该有不变的复杂性。

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

'注意A'被添加到标准中专门用于安抚那些认为应该允许 size（）具有线性复杂性的人，因此当容器没有时，没有必要保持大小。修改。

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

其他提示

这是一个简单的方法来回答msvc ++的问题。

在项目中编写一些代码：

string happy;
happy.size();

Hilight the .size call，右键单击，转到定义。

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

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

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

换句话说，这是一个O（1）实现。

是的，std :: string :: size（）是O（1）。

参见本标准第23.1节中的表65。 ＆QUOT; a.size（）＆QUOT;被列为“（注释A）”，其中表示“那些条目......应具有恒定的复杂性”。

第21.3节说字符串符合序列（23.1）的要求，ipso facto，size（）是恒定时间。

对于字符串， size（）操作 对于不使用 ropes 的所有字符串实现都是常量（1）。标准中没有明确的要求要求操作为 O（1），最接近的是 size（） 的通用要求>保持不变的时间，但这为任何其他复杂性措施留下了空间。

那么为什么必须它是O（1）？

这是因为无法根据字符串本身的内容计算大小。在C语言中，您使用NUL终止符来确定字符串的结尾，在C ++中，NUL与字符串中的任何其他字符一样有效。由于无法从内容（2）计算字符串的大小，因此必须在外部处理，而与字符串的实际大小无关。

（1） C ++ 03标准允许实现使用 ropes 作为字符串的实现，但事实是该标准的当前实现都不是图书馆使用它们。

（2）如果实现使用了绳索，如果块通过链表或类似链接链接，操作可能取决于构造绳索的块数的大小构造，或者如果他们被允许有不同的大小。但 ropes 并未在我所知的任何标准库实现中使用。

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

size_type __CLR_OR_THIS_CALL size() const

{   // return length of sequence

    return (_Mysize);

}

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

许可以下： CC-BY-SA 和 归因
不隶属于 StackOverflow
scroll top