Возможность реализации COW std :: string в C ++ 11

Ключевым моментом является последний пункт стандарта 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, который вы цитируете, был добавлен, чтобы обойти это только при первом обращении к [] 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; к 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]), второй найдет useCount, равный 1, и ему не придется дублировать. И из-за флага uncopyable,

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

тоже будет работать, а не изменять b.

Конечно, вышесказанное чрезвычайно упрощено. Заставить его работать в многопоточной среде чрезвычайно сложно, если вы просто не захватите мьютекс для всей функции для любой функции, которая может что-либо изменить (в этом случае результирующий класс будет чрезвычайно медленным). G ++ пытался, но потерпел неудачу, в одном конкретном случае он ломается. (Заставить его справиться с другими проблемами, которые я проигнорировал, не особенно сложно, но представляет собой множество строк кода.)