C++ 字符串函数 - 为什么它们通常具有未指定的复杂性？

Question

我刚刚注意到，根据最新的 C++ ISO 标准，string::pop_back和 string::erase (仅举两个例子，可能还有其他)成员函数具有未指定的复杂性。将复杂性留给图书馆编码人员的原因是什么？实际上是否有任何人知道的实现对 string::pop_back 具有非常量的复杂性？ ?

Answer 1

TLDR；因为历史和那个时间复杂性还没有被提出

情况:

[basic.string] 仅 直接指定一些操作具有一定的复杂性:

size() : O(1) 自 C++11

max_size() : O(1) 自 C++11

shrink_to_fit() :C++17 中的 O(n)(虽然在 C++11 中添加)

operator[] : O(1) 自 C++11

swap() :O(1)

data() : O(1) 自 C++11

它 间接指定更多(我可能在这里遗漏了一些):

length() : 等于 size()

empty() : 等于 size()

at() : 等于 operator[]

front() : 等于 operator[]

back() : 等于 operator[]

copy() :O(n)(来自其性格特征)

assign() :O(n)(来自其性格特征)

find()和变体:O(n)(来自其性格特征)

append(char* s) : O(m) 其中 m是 s 的长度(来自其性格特点)

data()上的要求这是关键。在 C++11 之前，字符串的底层存储是实现定义的。它可以是所有重要的链接列表，只要它可以在需要时转换为 c 样式数组。在C++11之后，底层实现仍然是平台相关的，但要求 data()是 O(1) 几乎可以保证字符串的存储在连续的 C 样式数组中(不再懒惰地复制您的链表)。在 C++17 中， data被重载以返回一个您可以修改的非常量字符数组，这种修改与使用 operator[] 相同。做同样的事情，这进一步巩固了实现(FWIW 存储仍然依赖于实现，但没有办法满足时间复杂度要求)。

您可以看到 C++03 唯一的性能要求是在 swap 上。 ，这反射(reflect)了标准长期以来的理念；更喜欢仅指定对象的行为并让实现负责性能保证。这为库实现者提供了更大的灵活性，可以针对他们认为合适的任何内容进行优化。

历史上发生了什么

当您深入研究添加复杂性措辞的提案(如 n2923: Specifying the complexity of size() )时，您会发现这些复杂性要求随着人们的考虑而逐渐增加。

哎呀，非常量 data()被添加到 C++17 中只是因为它之前没有被提出( link to std discussion on the matter(实际上只是链接回我们的 friend Howard Hinnant posted on StackOverflow))

写时复制

国际 n8215 ，作者讨论 basic_string详细地说，将写时复制作为其设计背后的最初理念之一(尽管它还没有完全实现)

On the other hand, the current specifications of basic_string are intended to allow reference counted strings for which copy-on-write (COW) is essential.

( Wikipedia, citing Scott Meyers 同意)。

如果标准允许写时复制，那么在标准中不做性能保证是有意义的，因为写入字符串可能是 O(1) 或 O(N)。 O(N) 是正确的，我想，但它是一个松散的界限，可能会产生误导。

事实上，Daniel Krügler 在 LWG 876: basic_string access operations should give stronger guarantees 中和你想的一样。并且还引用了写时复制作为遗迹:

Due to earlier support for copy-on-write, we find the following unnecessary limitations for C++0x:
... 2. Missing complexity guarantees: data() and c_str() simply return a pointer to their guts, which is guaranteed O(1). This should be spelled out.

所以它看起来像是允许实现者的灵活性、支持写时复制字符串的废弃想法以及缺乏考虑它的人的混合体。

随意为缺少的 basic_string 函数提出时间复杂度。标准可能会更好:-)