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重载是为了返回一个你可以修改的非const字符数组,这样的修改与使用operator[]它们相同,这进一步巩固了实现(FWIW存储仍然依赖于实现,但是没有办法满足时间复杂度要求.

您可以看到C++ 03的唯一性能要求已经开启swap,这很长一段时间反映了该标准的理念; 更喜欢只指定对象的行为,并让实现负责性能保证.这使库实现者可以更灵活地优化他们认为合适的任何内容.

历史上发生了什么

当您深入研究添加复杂性措辞的提案时(如n2923:指定大小()的复杂性),您会发现这些复杂性要求随着人们的考虑逐渐增加.

哎呀,非const data()是在C++ 17中添加的,因为之前没有提出过(链接到关于此事的std讨论(实际上只是链接回我们的朋友Howard Hinnant 在StackOverflow上发布的答案))

写入时复制

Int n8215,作者详细讨论basic_string了引用copy-on-write作为其设计背后的最初哲学之一(虽然它没有完全实现)

另一方面,basic_string的当前规范旨在允许引用计数的字符串,其中写时复制(COW)是必不可少的.

(维基百科,引用Scott Meyers的同意).

如果标准允许写入时复制,则在标准中不进行性能保证是有意义的,因为对字符串的写入可以是O(1)或O(N).我想O(N)是正确的,但这是一个可能会产生误导的松散界限.

事实上,DanielKrügler在LWG 876中想到了和你一样的事情:basic_string访问操作应该提供更强的保证,并且还引用了写时复制作为遗迹:

由于对写入时复制早期的支持,我们找到的C++ 0x以下不必要的限制:
... 2.缺失的复杂度保证:data()与c_str()只是一个指针回到自己的胆量,这是保证O(1).这应该拼写出来.

因此,它看起来像是允许实现者灵活性,支持写入时写入字符串的丢弃想法,以及缺乏人们思考它的混合物.

随意为缺少它们的basic_string函数提出时间复杂性.该标准可能会更好:-)