126

我的理解是写时复制不是std::string在 C++11 中实现一致性的可行方法，但是当它最近在讨论中出现时，我发现自己无法直接支持该声明。

我是否正确 C++11 不承认基于 COW 的实现std::string？

如果是这样，这个限制是否在新标准的某处明确说明（在哪里）？

还是暗示了这种限制，因为新要求的综合影响std::string排除了基于 COW 的std::string. std::string在这种情况下，我会对“C++11 有效禁止基于 COW 的实现”的章节风格派生感兴趣。

4

7 回答 7

123

这是不允许的，因为根据标准 21.4.1 p6，迭代器/引用的无效只允许

— 作为任何标准库函数的参数，将非常量 basic_string 的引用作为参数。

— 调用非常量成员函数，除了 operator[]、at、front、back、begin、rbegin、end 和 rend。

对于 COW 字符串，调用 non-constoperator[]将需要制作副本（并使引用无效），这在上面的段落中是不允许的。因此，在 C++11 中使用 COW 字符串不再合法。

于 2012-08-30T15:06:12.427 回答
53

Dave S和 gbjbaanb的答案是正确的。（而且 Luc Danton 的说法也是正确的，尽管它更像是禁止 COW 字符串的副作用，而不是禁止它的原始规则。）

但是为了消除一些混乱，我将添加一些进一步的说明。各种评论链接到我在 GCC bugzilla 上的评论，其中给出了以下示例：

std::string s("str");
const char* p = s.data();
{
    std::string s2(s);
    (void) s[0];
}
std::cout << *p << '\n';  // p is dangling

该示例的重点是说明为什么 GCC 的引用计数 (COW) 字符串在 C++11 中无效。C++11 标准要求此代码正常工作。代码中的任何内容p都不允许在 C++11 中无效。

使用 GCC 的旧引用计数std::string实现，该代码具有未定义的行为，因为p 已失效，成为一个悬空指针。（发生的情况是，在s2构造时它与 共享数据s，但通过获取非常量引用s[0]需要取消共享数据，“写入时复制”也是如此，因为s引用s[0]可能用于写入超出范围，破坏 ) 指向的数组。ss2p

C++03 标准在 21.3 [lib.basic.string] p5 中明确允许这种行为，它说在调用data()第一次调用之后operator[]()可能会使指针、引用和迭代器无效。所以 GCC 的 COW 字符串是一个有效的 C++03 实现。

C++11 标准不再允许这种行为，因为没有调用operator[]()可能会使指针、引用或迭代器无效，无论它们是否遵循对data().

所以上面的例子必须在 C++11 中工作，但不适用于 libstdc++ 的那种 COW 字符串，因此这种 COW 字符串在 C++11 中是不允许的。

于 2015-03-22T20:55:21.843 回答
20

确实，CoW 是一种可接受的机制来制作更快的字符串……但是……

它使多线程代码变慢（在使用大量字符串时，所有用于检查您是否是唯一一个编写代码的锁定都会降低性能）。这是几年前 CoW 被杀的主要原因。

其他原因是[]操作员将返回字符串数据，而不会保护您覆盖其他人期望不变的字符串。这同样适用于c_str()和data()。

快速谷歌说，多线程基本上是它被有效禁止的原因（未明确）。

该提案说：

提议

我们建议使所有迭代器和元素访问操作可以安全地并发执行。

即使在顺序代码中，我们也在提高操作的稳定性。

此更改有效地禁止了写时复制实现。

其次是

由于从写时复制实现切换而导致的最大潜在性能损失是具有非常大的以读取为主的字符串的应用程序的内存消耗增加。但是，我们认为对于这些应用，绳索是更好的技术解决方案，并建议考虑将绳索提案纳入图书馆 TR2。

绳索是 STLPort 和 SGIs STL 的一部分。

于 2012-08-30T15:01:54.997 回答
5

从 21.4.2 basic_string 构造函数和赋值运算符 [string.cons]

basic_string(const basic_string<charT,traits,Allocator>& str);

[...]

2效果：构造一个类的对象，basic_string如表 64 所示。 [...]

表 64 有用地记录了在通过此（复制）构造函数构造对象后，this->data()具有作为值：

指向数组的已分配副本的第一个元素，其第一个元素由 str.data() 指向

其他类似的构造函数也有类似的要求。

于 2012-08-30T15:02:40.470 回答
4

basic_stringC++11 及更高版本是否禁止使用COW ？

关于

” C++11 不承认基于 COW 的实现我是否正确std::string？

是的。

关于

”如果是这样，这个限制是否在新标准的某处（哪里）明确说明？

几乎直接地，由于需要在 COW 实现中对字符串数据进行 O( n ) 物理复制的许多操作的恒定复杂性要求

例如，对于成员函数

auto operator[](size_type pos) const -> const_reference;
auto operator[](size_type pos) -> reference;

…在 COW 实现中会 ¹触发字符串数据复制以取消共享字符串值，C++11 标准要求

C++11 §21.4.5/4：

” 复杂性：恒定的时间。

......这排除了这种数据复制，因此，COW。

C++03 支持 COW 实现，没有这些恒定的复杂性要求，并且在某些限制条件下，允许调用operator[](), at(), begin(), rbegin(), end(), 或rend()使引用字符串项的引用、指针和迭代器无效，即可能导致牛数据复制。在 C++11 中删除了此支持。

C++11 失效规则是否也禁止 COW？

在另一个答案中，在撰写本文时被选为解决方案，并且受到高度支持，因此显然相信，它断言

”对于 COW 字符串，调用 non-const operator[]需要制作副本（并使引用无效），这是 [C++11 §21.4.1/6] 上面的 [quoted] 段落所不允许的。因此，在 C++11 中使用 COW 字符串不再合法。

该断言在两个主要方面是不正确和误导的：

  • 它错误地表明只有非const项目访问者需要触发 COW 数据复制。
    但const项目访问器也需要触发数据复制，因为它们允许客户端代码形成引用或指针（在 C++11 中），以后不允许通过可触发 COW 数据复制的操作使其无效。
  • 它错误地假设 COW 数据复制会导致引用失效。
    但在正确的实现中，COW 数据复制、取消共享字符串值是在任何引用可能无效之前完成的。

要了解正确的 C++11 COW 实现如何basic_string工作，当忽略使此无效的 O(1) 要求时，请考虑一个字符串可以在所有权策略之间切换的实现。字符串实例以策略共享开始。启用此策略后，将没有外部项目引用。实例可以转换为唯一策略，并且它必须在可能创建项目引用时这样做，例如通过调用.c_str()（至少如果这会产生指向内部缓冲区的指针）。在多个实例共享值所有权的一般情况下，这需要复制字符串数据。在转换为唯一策略之后，实例只能通过使所有引用无效的操作（例如分配）转换回共享。

因此，虽然该答案的结论（即排除了 COW 字符串）是正确的，但所提供的推理是不正确的并且具有很强的误导性。

我怀疑造成这种误解的原因是 C++11 的附件 C 中的非规范注释：

C++11 §C.2.11 [diff.cpp03.strings]，关于 §21.3：

更改：basic_string要求不再允许引用计数字符串
理由：失效与引用计数字符串略有不同。此更改规范了本国际标准的行为（原文如此）。
对原始功能的影响：有效的 C++ 2003 代码在本国际标准中的执行方式可能不同

这里的基本原理解释了决定删除 C++03 特殊 COW 支持的主要原因。这个理由，为什么，不是标准如何有效地禁止 COW 实施。该标准通过 O(1) 要求禁止 COW。

简而言之，C++11 失效规则不排除std::basic_string. 但他们确实排除了一种相当有效的不受限制的 C++03 风格的 COW 实现，例如至少一个 g++ 的标准库实现中的一种。特殊的 C++03 COW 支持允许实际效率，特别是使用const项访问器，但代价是微妙、复杂的无效规则：

C++03 §21.3/5包括“首次调用”COW 支持：

”引用序列元素的引用、指针和迭代器basic_string可能会因该basic_string对象的以下用途而失效：
— 作为非成员函数swap()(21.3.7.8)、 (21. operator>>()​​3.7.9) 和getline()(21.3) 的参数。 7.9)。
— 作为 的论据basic_string::swap()。
— 调用data()和c_str()成员函数。
— 调用非const成员函数，除了operator[](), at(), begin(), rbegin(), end(), 和rend().
— 在上述任何使用之后，除了返回迭代器的形式insert()和erase()返回迭代器，第一次调用非const成员函数operator[](), at(), begin(), rbegin(),end(), 或rend().

这些规则是如此复杂和微妙，以至于我怀疑许多程序员（如果有的话）能否给出准确的总结。我不能。

如果忽略 O(1) 要求怎么办？

operator[]如果忽略对 eg 的 C++11 恒定时间要求，那么 COW forbasic_string在技术上可能是可行的，但难以实现。

无需复制 COW 数据即可访问字符串内容的操作包括：

  • 通过连接+。
  • 通过输出<<。
  • 使用basic_string标准库函数的 as 参数。

后者是因为允许标准库依赖于实现特定的知识和结构。

此外，实现可以提供各种非标准函数来访问字符串内容，而不会触发 COW 数据复制。

一个主要的复杂因素是，在 C++11 中，basic_string项目访问必须触发数据复制（取消共享字符串数据）但要求不抛出，例如 C++11 §21.4.5/3 “ Throws: Nothing.”。所以它不能使用普通的动态分配来创建一个新的缓冲区来复制COW数据。解决此问题的一种方法是使用一个特殊的堆，其中可以保留内存而无需实际分配，然后为每个对字符串值的逻辑引用保留必要的数量。在这样的堆中保留和取消保留可以是常数时间，O(1)，分配一个已经保留的数量，可以是noexcept. 为了符合标准的要求，使用这种方法，似乎每个不同的分配器都需要一个这样的特殊的基于预留的堆。

注意：
¹const项目访问器触发 COW 数据复制，因为它允许客户端代码获取数据的引用或指针，不允许由例如非const项目访问器触发的后续数据复制使其无效。

于 2016-07-29T05:53:27.857 回答
2

由于现在可以保证字符串是连续存储的，并且您现在可以获取指向字符串内部存储的指针（即 &str[0] 就像数组一样工作），所以不可能制作有用的 COW执行。您将不得不为太多事情制作副本。即使只是在非常量字符串上使用operator[]orbegin()也需要一个副本。

于 2012-08-30T15:00:07.417 回答
-1

我一直在想不可变的奶牛：一旦奶牛被创建，我只能通过另一头奶牛的分配来改变，因此它将符合标准。

今天我有时间尝试了一个简单的比较测试：一个大小为 N 的映射，由字符串/牛键入，每个节点在映射中保存一组所有字符串（我们有 NxN 个对象）。

字符串大小约为 300 字节且 N=2000 头牛稍微快一些，并且使用的内存几乎减少了一个数量级。见下文，大小以 kbs 为单位，运行 b 是奶牛。

~/icow$ ./tst 2000
preparation a
run
done a: time-delta=6 mem-delta=1563276
preparation b
run
done a: time-delta=3 mem-delta=186384
于 2019-10-16T01:06:52.597 回答