COW std :: string在C ++ 11中的合法性
我的理解是copy-on-write不是在C ++ 11中实现符合std::string
的可行方法,但是最近在讨论中提到时,我发现自己无法直接支持该语句。
我正确的说C ++ 11不承认基于COW的std::string
吗?
如果是这样,这个限制在新标准(哪里)的某个地方明确表示?
或者这个限制是暗示的,就是说这是std::string
的新的需求的组合效果,它排除了基于COW的std::string
。 在这种情况下,我会对“C ++ 11有效地禁止基于COW的std::string
实现”的章节和经文样式派生感兴趣。
这是不允许的,因为按照标准21.4.1 p6,迭代器/引用的失效只允许使用
– 作为任何引用非const basic_string作为参数的标准库函数的参数。
– 调用非const成员函数,除了operator [],at,front,back,begin,rbegin,end和rend。
对于一个COWstring来说,调用非常量operator[]
将需要复制(并使引用无效),这是上面的段落所不允许的。 因此,在C ++ 11中使用COWstring已经不合法了。
Dave S和gbjbaanb的答案是正确的 。 (Luc Danton也是正确的,尽pipe这更多的是禁止COWstring的副作用,而不是禁止COWstring的原始规则。)
但是为了澄清一些混淆,我打算再补充一点。 各种评论链接到我的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)string在C ++ 11中是无效的。 C ++ 11标准要求此代码正常工作。 代码中的任何内容都不允许在C ++ 11中使p
失效。
使用GCC的旧引用计数std::string
实现,该代码具有未定义的行为,因为p
是无效的,成为一个悬挂指针。 (会发生什么情况是,当s2
被构造时,它与s
共享数据,但是通过s[0]
获得一个非const引用,要求数据是不共享的,所以s
执行“copy on write”,因为引用s[0]
可能被用来写入s
,然后s2
超出范围,破坏p
指向的数组)。
C ++ 03标准明确地允许在21.3 [lib.basic.string] p5中的行为 ,其中它表示在调用data()
,对operator[]()
的第一次调用可能使指针,引用和迭代器无效。 所以GCC的COWstring是一个有效的C ++ 03实现。
C ++ 11标准不再允许这种行为,因为对operator[]()
调用可能会使指针,引用或迭代器无效,而不pipe它们是否遵循对data()
的调用。
所以上面的例子必须在C ++ 11 中工作,但是不能和libstdc ++的COWstring一起工作,因此这种COWstring在C ++ 11中是不允许的。
就是说,CoW是制造更快弦乐的可接受机制…但是…
它使multithreading代码更慢(所有的locking,以检查是否你是唯一一个使用大量string杀死性能)。 这是几年前CoW被杀的主要原因。
其他的原因是[]
运算符会返回string数据,没有任何保护措施来覆盖别人希望不变的string。 这同样适用于c_str()
和data()
。
快速谷歌说,multithreading基本上是它被有效地禁止 (不明确)的原因。
该提案说:
提案
我们build议使所有的迭代器和元素访问操作安全地同时执行。
即使在连续代码中,我们也在增加操作的稳定性。
此更改有效地禁止写入时复制实现。
其次是
由于从写时复制实施切换而导致的性能损失最大的原因是对于具有非常大的大部分读取string的应用程序而言,存储器消耗的增加。 但是,我们认为,对于这些应用绳索是一个更好的技术解决scheme,并build议考虑列入图书馆TR2绳索的build议。
绳索是STLPort和SGIs STL的一部分。
从21.4.2 basic_string构造函数和赋值运算符[string.cons]
basic_string(const basic_string<charT,traits,Allocator>& str);
[…]
2 作用 :按表64所示构造
basic_string
类的对象。[…]
表64通过这个(复制)构造函数build立一个对象之后有用地logging了this->data()
值:
指向第一个元素由str.data()指向的数组分配副本的第一个元素,
对于其他类似的构造函数也有类似的要求。
由于现在可以保证string是连续存储的,现在你可以使用一个指向string内部存储器的指针(例如,&str [0]就像数组一样),所以不可能创build一个有用的COW实现。 你将不得不复制太多的东西。 即使对非conststring使用operator[]
或begin()
也需要一个副本。
在C ++ 11及更高版本中禁止COW basic_string
?
关于
“我正确地认为C ++ 11不承认基于COW的
std::string
吗?
是。
关于
“如果是这样,这个限制在新标准(哪里)的某个地方明确表示?
几乎直接地,对于需要在COW实现中对string数据进行O( n )物理复制的多个操作的持续复杂性要求。
例如,对于成员函数
auto operator[](size_type pos) const -> const_reference; auto operator[](size_type pos) -> reference;
…在COW实现中,将触发string数据复制以取消string值,C ++ 11标准要求
C ++ 11§21.4.5/ 4 :
“ 复杂性:不变的时间。
…这排除了这种数据复制,因此,COW。
at()
, begin()
, rbegin()
, end()
或者rend()
end()
调用,C ++ 03支持COW实现, rend()
使引用string项的引用,指针和迭代器无效,即可能导致COW数据复制。 这个支持在C ++ 11中被删除了。
COW是否也通过C ++ 11无效规则被禁止?
在撰写本文时select的另一个答案是解决scheme,而且这个答案在很大程度上被高估,因此显然被认为是相信的,
“对于一个COWstring,调用非
const
operator[]
将需要复制(并且使引用无效),这是[C ++ 11§21.4.1/ 6]上面[引用的]段落所不允许的。 因此,在C ++ 11中使用COWstring已经不合法了。
这种断言在两个主要方面是不正确和误导的:
- 它错误地表示只有非常量项访问器需要触发一个COW数据复制。
但是,const
item访问器也需要触发数据复制,因为它们允许客户端代码形成引用或指针(在C ++ 11中),它不允许通过可以触发COW数据复制的操作在以后失效。 - 它错误地假定COW数据复制可能导致引用无效。
但是在一个正确的实现中,COW数据复制,不共享string值,是在有任何引用可以失效之前的一个点完成的。
为了看到basic_string
的正确C ++ 11 COW实现是如何工作的,当忽略这个无效的O(1)需求时,可以考虑一个string可以在所有权策略之间切换的实现。 string实例从策略Sharable开始。 在这个策略激活的情况下,不能有外部项目引用。 实例可以转换到唯一策略,并且必须在可能创build项引用时(例如调用.c_str()
(至less在产生指向内部缓冲区的指针)时这样做。 在多个实例共享该值的所有权的一般情况下,这需要复制string数据。 在转换到唯一策略之后,实例只能通过使所有引用无效的操作(如赋值)转换回可共享。
所以,虽然这个答案的结论是,COWstring被排除,是正确的,提供的理由是不正确的,强烈的误导。
我怀疑这个误解的原因是C ++ 11的附录C中的一个不规范的注释:
C ++ 11§C.2.11[diff.cpp03.strings],关于§21.3:
更改 :
basic_string
要求不再允许引用计数的string
理由:无效与引用计数的string有细微的差别。 这种变化正常化了这个国际标准的行为(原文如此)。
对原始function的影响:在此国际标准中,有效的C ++ 2003代码可能会有不同的执行
这里的基本原理解释了为什么人们决定删除C ++ 03特殊的COW支持。 这个原因, 原因并不在于标准如何有效地禁止COW的实施。 该标准通过O(1)的要求不允许COW。
简而言之,C ++ 11失效规则并不排除std::basic_string
的COW实现。 但是他们确实排除了一个相当有效的无限制的C ++ 03风格的COW实现,就像g ++的标准库实现中的至less一个一样。 特殊的C ++ 03 COW支持允许实际的效率,尤其是使用const
item访问器,代价是微妙的,复杂的失效规则:
C ++ 03§21.3/ 5其中包括“第一个呼叫”COW支持:
引用
basic_string
序列元素的引用,指针和迭代器可能会被basic_string
对象的下列用法所取消:
– 作为非成员函数swap()
(21.3.7.8),operator>>()
(21.3.7.9)和getline()
(21.3.7.9)的一个参数。
– 作为basic_string::swap()
的参数。
– 调用data()
和c_str()
成员函数。
–at()
,begin()
,rbegin()
,end()
和rend()
调用非const
成员函数,除了operator[]()
rend()
。
– 除了返回迭代器的insert()
和erase()
forms之外的上述任何用法之后,第一次调用非const
成员函数operator[]()
,at()
,begin()
,rbegin()
end()
或rend()
。
这些规则如此复杂和微妙,以至于我怀疑许多程序员是否可以给出精确的总结。 我不能。
如果O(1)的要求被忽视呢?
如果忽略operator[]
上的C ++ 11常量时间要求,那么basic_string
COW在技术上可行,但难以实现。
可以访问string内容的操作,而不会产生COW数据复制,包括:
- 通过
+
连接。 - 通过
<<
输出。 - 使用
basic_string
作为标准库函数的参数。
后者是因为标准库被允许依赖实现特定的知识和构造。
此外,一个实现可以提供各种非标准函数来访问string内容,而不会触发COW数据复制。
一个主要的复杂因素是在C ++ 11中basic_string
项访问必须触发数据复制(不共享string数据),但是不要抛出 ,例如C ++ 11§21.4.5/ 3“ 抛出: Nothing”。 。 所以它不能使用普通的dynamic分配来为COW数据复制创build一个新的缓冲区。 解决这个问题的一个方法就是使用一个特殊的堆,在这个堆中可以保留内存,而不必实际分配内存,然后为每个逻辑引用保留必要的金额,以得到一个string值。 在这样一个堆中保留和取消保留可以是恒定的时间,O(1),并且分配已经保留的数量,可以是noexcept
。 为了符合标准的要求,采用这种方法,似乎每个不同的分配器需要有一个这样的特殊的基于预留的堆。
笔记:
¹ const
项访问器触发COW数据复制,因为它允许客户端代码获取数据的引用或指针,不允许通过例如非常量项访问器触发的后续数据复制来使其无效。