c++ - 在C++ 11中实现COW std::string的可能性

Question

今天我通过了这个SO问题:Legality of COW std::string implementation in C++11

该问题的投票最多(35票赞成):

It's not allowed, because as per the standard 21.4.1 p6, invalidation of iterators/references is only allowed for

— as an argument to any standard library function taking a reference to non-const basic_string as an argument.

— Calling non-const member functions, except operator[], at, front, back, begin, rbegin, end, and rend.

For a COW string, calling non-const operator[] would require making a copy (and invalidating references), which is disallowed by the paragraph above. Hence, it's no longer legal to have a COW string in C++11.

我想知道这种调整是否有效，因为似乎C++ 03对字符串迭代器无效有类似的要求:

References, pointers, and iterators referring to the elements of a basic_string sequence may be invalidated by the following uses of that basic_string object:

• As an argument to non-member functions swap() (21.3.7.8), operator>>() (21.3.7.9), and getline() (21.3.7.9).
• As an argument to basic_string::swap().
• Calling data() and c_str() member functions.
• Calling non-const member functions, except operator[](), at(), begin(), rbegin(), end(), and rend().
• Subsequent to any of the above uses except the forms of insert() and erase() which return iterators, the first call to non-const member functions operator[](), at(), begin(), rbegin(), end(), or rend().

这些与C++ 11的代码不完全相同，但是对于 operator[]()的部分至少相同，原始答案被当作主要理由。所以我想，为了证明C++ 11中COW std::string实现的非法性，还需要引用其他一些标准要求。这里需要帮助。

这个问题已经闲置了一年多，所以我决定将其作为一个单独的问题提出。请让我知道这是否不合适，我将找到其他方法来消除我的疑问。

Answer 1

关键点是C++ 03标准中的最后一点。的
措词可能更清晰，但目的是第一个
在之后调用[]，at等(但仅限第一个调用)
建立了新迭代器的东西(因此无效)
旧版本)可以使迭代器无效，但只能是第一个。的
实际上，C++ 03中的措词是一个快速的技巧，
回应法国国家机构对CD2的评论
C++ 98。最初的问题很简单:考虑:

std::string a( "some text" );
std::string b( a );
char& rc = a[2];

此时，通过 rc进行的修改必须影响 a，但是
不是 b。但是，如果使用的是COW，则在调用 a[2]时， a和 b共享一个表示；为了通过写
返回的引用不影响 b， a[2]必须为
被视为“写入”，并被允许使
引用。 CD2所说的是:对非常量的任何调用 []， at或 begin或 end函数之一
使迭代器和引用无效。法国国家机构
评论指出此 a[i] == a[j]无效，
因为 []之一返回的引用是
被对方无效。您引用C++ 03的最后一点是
添加了规避此功能的方法-仅第一个调用 []等
等可能会使迭代器无效。

我认为没有人会对结果感到完全满意。的
措词很快完成，尽管意图很明显
那些知道历史和原始问题的人，
我认为从标准来看还不是很清楚。此外，
一些专家开始质疑COW的值(value)，
考虑到字符串类本身相对不可能
可靠地检测所有写入。 (如果 a[i] == a[j]是完整的
表达式，没有写。但是字符串类本身必须
假设 a[i]的返回值可能会导致写入。)
在多线程环境中，
写时复制所需的引用计数被认为是相对的
通常不需要的东西的成本很高。结果是
大多数实现(早就支持线程
C++ 11)无论如何都已经远离了COW；据我所知，
唯一仍在使用COW的主要实现是g++(但在那里
是其多线程实现中的已知错误)和
(也许)Sun CC(我上次看的是
由于管理计数器的成本而变得异常缓慢)。
我认为委员会只是把他们认为的
禁止COW进行清理的最简单方法。

编辑:

关于为何实现COW的更多说明
必须在第一次调用 []时使迭代器无效。考虑
天真的执行COW。 (我将其称为String，
忽略所有涉及特征和分配器的问题
在这里并不重要。我还将忽略异常，
线程安全，只是为了使事情尽可能简单。)

class String
{
    struct StringRep
    {
        int useCount;
        size_t size;
        char* data;
        StringRep( char const* text, size_t size )
            : useCount( 1 )
            , size( size )
            , data( ::operator new( size + 1 ) )
        {
            std::memcpy( data, text, size ):
            data[size] = '\0';
        }
        ~StringRep()
        {
            ::operator delete( data );
        }
    };

    StringRep* myRep;
public:
    String( char const* initial_text )
        : myRep( new StringRep( initial_text, strlen( initial_text ) ) )
    {
    }
    String( String const& other )
        : myRep( other.myRep )
    {
        ++ myRep->useCount;
    }
    ~String()
    {
        -- myRep->useCount;
        if ( myRep->useCount == 0 ) {
            delete myRep;
        }
    }
    char& operator[]( size_t index )
    {
        return myRep->data[index];
    }
};

现在想象一下，如果我写:

String a( "some text" );
String b( a );
a[4] = '-';

此后 b的值是什么？ (通过
(如果不确定的话)。)

显然，这是行不通的。解决方法是添加一个标志， bool uncopyable;到 StringRep，已初始化为 false，并修改以下功能:

String::String( String const& other )
{
    if ( other.myRep->uncopyable ) {
        myRep = new StringRep( other.myRep->data, other.myRep->size );
    } else {
        myRep = other.myRep;
        ++ myRep->useCount;
    }
}

char& String::operator[]( size_t index )
{
    if ( myRep->useCount > 1 ) {
        -- myRep->useCount;
        myRep = new StringRep( myRep->data, myRep->size );
    }
    myRep->uncopyable = true;
    return myRep->data[index];
}

当然，这意味着 []将使迭代器无效，并且
引用，但仅限于第一次在对象上调用它。
下次， useCount将为1(图像将为
无法复制)。因此， a[i] == a[j]有效；不管哪个
编译器实际上首先评估( a[i]或 a[j])，然后评估第二个
人们会发现 useCount为1，并且不必重复。
而且由于 uncopyable标志，

String a( "some text" );
char& c = a[4];
String b( a );
c = '-';

也将起作用，并且不会修改 b。

当然，以上内容大大简化了。到达
在多线程环境中工作非常困难，
除非您简单地为任何功能获取整个功能的互斥量
可能会修改任何内容的函数(在这种情况下，
结果课非常慢)。 G++尝试过，并且
失败-在特定的用例中，它会中断。
(让它处理我忽略的其他问题不是
特别困难，但确实代表了很多方面
码。)