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

Question

今天我通过了这个问题:C++ 11中COW std :: string实现的合法性

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

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

- 作为任何标准库函数的参数,将非const basic_string作为参数引用.

- 调用非const成员函数,除了operator [],at,front,back,begin,rbegin,end和rend.

对于COW字符串,调用非const运算符[]将需要复制(并使引用无效),上面的段落不允许这样做.因此,在C++ 11中拥有COW字符串已不再合法.

我想知道这种理由是否有效,因为C++ 03似乎对字符串迭代器失效有类似的要求:

引用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()成员函数.
• 调用非const成员函数,除了operator [](),at(),begin(),rbegin(),end()和rend().
• 除了返回迭代器的insert()和erase()形式之外的任何上述用法之后,第一次调用非const成员函数operator [](),at(),begin(),rbegin(),end ()或rend().

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

---

这个SO问题已经停止了一年多,所以我决定将其作为一个单独的问题提出来.如果这不合适,请告诉我,我会找到其他方法来澄清我的疑问.

Answer 1

关键点是C++ 03标准的最后一点.措辞可以更加清晰,但目的是,在第一次调用[],at等(但只有第一次调用),它建立了新的迭代器(因而无效旧的)东西后可能无效迭代器,但只有第一个.事实上,C++ 03中的措辞是一个快速入侵,插入是为了回应法国国家机构对C++ 98 CD2的评论.最初的问题很简单:考虑:

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说:到一个非const任何呼叫 [],at或的一个begin或end功能可能失效迭代器和引用.法国国家机构的评论指出,这使得a[i] == a[j]无效,因为其中一个返回的引用将被另一个[]无效.你引用C++ 03的最后一点是为了绕过这个 - 只是对[]et al 的第一次调用.可以使迭代器无效.

我认为没有人对结果完全满意.措辞很快就完成了,虽然对那些了解历史和原始问题的人的意图很清楚,但我认为从标准来看并不完全清楚.此外,鉴于字符串类本身无法可靠地检测所有写入,一些专家开始质疑COW的价值.(如果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;to 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将是一个(图像将是不可复制的).所以a[i] == a[j]工作; 无论编译器实际上首先评估(a[i]或a[j]),第二个将找到useCount1,并且不必复制.而且由于uncopyable国旗,

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

也会工作,而不是修改b.

当然,上述内容极大地简化了.让它在多线程环境中工作是非常困难的,除非你只是为任何可能修改任何东西的函数获取整个函数的互斥量(在这种情况下,结果类非常慢).G ++尝试过,但失败了 - 特定的用例在它中断了.(让它处理我忽略的其他问题并不是特别困难,但确实代表了许多代码行.)