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

Ответ 1

Ключевым моментом является последний пункт в стандарте С++ 03. формулировка может быть намного яснее, но цель состоит в том, что первая вызовите [], at и т.д. (но только первый вызов) после то, что создало новые итераторы (и, таким образом, признано недействительным старые) могли бы аннулировать итераторы, но только первые. формулировка на С++ 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] недействительным, поскольку ссылка, возвращаемая одним из [], будет недействительным другим. Последнее, что вы указали в С++ 03, было добавлено, чтобы обходить этот вызов, только первый вызов [] et и др. может привести к недействительности итераторов.

Я не думаю, что кто-то был полностью доволен результатами. формулировка была выполнена быстро, и, хотя было ясно, что те, кто знал историю и оригинальную проблему, Я не думаю, что это было полностью ясно из стандарта. К тому же, некоторые эксперты начали подвергать сомнению ценность COW для начала, учитывая относительную невозможность самого класса строк надежно обнаруживать все записи. (Если a[i] == a[j] является полным выражения, нет записи. Но сам класс строки должен предположим, что возвращаемое значение a[i] может привести к записи.) И в многопоточной среде затраты на управление количество ссылок, необходимое для копирования при записи, считалось относительно высокая стоимость за то, что вам обычно не нужно. В результате что большинство реализаций (которые поддерживали потоки задолго до С++ 11) все равно отходят от COW; насколько я знаю, единственная крупная реализация, использующая COW, была g++ (но там была известной ошибкой в ​​их многопоточной реализации) и (возможно) Sun CC (который в последний раз, когда я смотрел на него, был чрезмерно медленный, из-за стоимости управления счетчиком). Я думаю, комитет просто взял то, что им казалось простейший способ очистки вещей, запрещая COW.

EDIT:

Несколько разъяснений относительно того, почему реализация 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 будет одним (и изображение будет uncopyable). Итак, a[i] == a[j] работает; независимо от того, компилятор фактически оценивает сначала (a[i] или a[j]), второй найдется a useCount of 1 и не придется дублировать. И из-за флага uncopyable

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

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

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