14

我刚刚注意到，根据最新的 C++ ISO 标准，string::pop_backand string::erase（仅举两例，可能还有其他）成员函数具有未指定的复杂性。将复杂性留给图书馆编码员选择的原因是什么？实际上是否存在任何人都知道的具有非恒定复杂性的实现string::pop_back？

4

2 回答 2

19

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唯一的性能要求是on swap，这体现了标准长期以来的理念；更喜欢只指定对象的行为，让实现来处理性能保证。这为库实现者提供了更大的灵活性，可以针对他们认为合适的任何内容进行优化。

历史上发生了什么

当您深入研究添加复杂性措辞的提案时（例如n2923：指定 size() 的复杂性），您会发现这些复杂性要求随着人们的考虑而逐渐增加。

哎呀，非常量data()是在 C++17 中添加的，仅仅是因为它之前没有被提出（链接到关于此事的标准讨论（实际上只是链接回我们的朋友 Howard Hinnant在 StackOverflow 上发布的答案））

写时复制

Int n8215，作者详细讨论basic_string，引用写时复制作为其设计背后的初始理念之一（尽管它并没有完全实现）

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

（维基百科，引用斯科特迈耶斯同意）。

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

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

由于早期对写时复制的支持，我们发现 C++0x 存在以下不必要的限制：
... 2. 缺少复杂性保证：data()并c_str()简单地返回指向其内脏的指针，这保证了 O(1)。这应该说清楚。

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

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

于 2017-07-19T19:50:50.553 回答
1

很久以前，有一种想法可以std::string使用ropes来实现。SGI STL 甚至包含一个具有非常相似界面的rope模板。string

但事实证明，人们c_str()大量使用下标运算符和方法，而不是有效的连接，这就是为什么基于绳索的实现std::string在实践中没有竞争力的原因。

于 2017-07-23T16:50:12.383 回答