std :: string size()是否为O(1)操作？

std :: string size()是否为O(1)操作？

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

1> Michael Burr..：

---

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

那些标有''(注释A)'的条目应该具有不变的复杂性.

但是,这并不意味着这些条目应具有不变的复杂性.标准使用非常具体的术语,"应该"意味着它不是强制性的.

"注意A"被添加到标准中,专门用于安抚那些认为size()应该允许具有线性复杂性的人,因此在修改容器时没有必要保持大小.

所以你不能依赖于size()持续的复杂性,但我真的不确定是否有任何实现没有常量string::size().

---

作为旁注,尽管如此,仍然可以以标准方式检索字符串的大小作为O(1)操作:`(end() - begin())`.这保证是\ [amortized \] O(1)因为`begin()`和`end()`必须是O(1)(容器需求),字符串迭代器是随机访问(字符串要求),并且对于支持它的迭代器(迭代器要求),`operator -`必须是O(1).

---

@j_random_hacker:你在谈论假设语言还是C++？用一种假设的语言,我想你可以.在C++ 03标准中描述`std :: basic_string <> :: size()`它指的是容器需求(即推荐的常量),在11标准中要求是明确的:*复杂性:常数时间*.

---

...并且无法根据内容计算字符串的长度,因为对可存储的值没有限制.这意味着它必须在内部管理,因此独立于N.即它必须是*O(1)*."O(1)"不是*all*容器的要求这一事实并不意味着它在容器中可以是"O(N)",只是说至少有一个容器可以是非容器的常量,例如`std :: list <>`.

---

@DavidRodríguez-dribeas:你说得对!在03标准中,21.3/2表示"类模板`basic_string`符合序列的要求,如(23.1.1)"中所规定,而序列是一种容器(23.1.1/1),容器要求常量时间`begin()`和`end()`(23.1中的表65)很高兴听到他们在C++ 11中明确表示它.

2> tfinniga..：

---

这是一个简单的方法来回答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)实现.

3> lacker..：

---

是的,std :: string :: size()是O(1).

4> Don Wakefiel..：

---

参见标准第23.1节中的表65."a.size()"被列为"(注释A)",其中说"那些条目......应该具有不变的复杂性".

第21.3节说字符串符合序列(23.1)的要求,ipso facto,size()是恒定时间.

5> David Rodríg..：

---

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

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

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

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

⁽²⁾如果实施使用绳索,如果块通过链表或类似构造链接,或者如果允许它们具有不同,则操作可以通过构造绳索的块的数量来决定大小.大小.但是在我所知道的任何标准库实现中都没有使用绳索.