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

Это не разрешено, потому что согласно стандарту 21.4.1 p6 аннулирование итераторов/ссылок разрешено только для

— в качестве аргумента любой стандартной библиотечной функции, принимающей в качестве аргумента ссылку на неконстантную базовую_строку.

— Вызов неконстантных функций-членов, кроме operator[], at, front, back, begin, rbegin, end и rend.

Для строки COW вызов неконстантной operator[] потребует создания копии (и аннулирования ссылок), что запрещено абзацем выше. Следовательно, в С++ 11 больше не разрешено иметь строку COW.

Ответы Dave S и gbjbaanb правильно. (И Люк Дантон тоже прав, хотя это скорее побочный эффект запрета строк COW, чем исходное правило, которое запрещает это.)

Но чтобы прояснить некоторую путаницу, я собираюсь добавить еще несколько экспозиций. Различные комментарии ссылаются на мой комментарий об ошибке GCC, который дает следующий пример:

std::string s("str");
const char* p = s.data();
{
    std::string s2(s);
    (void) s[0];
}
std::cout << *p << '\n';  // p is dangling

Смысл этого примера в том, чтобы продемонстрировать, почему строка с подсчетом ссылок (COW) GCC недействительна в C++11. Стандарт C++11 требует, чтобы этот код работал правильно. Ничто в коде не позволяет сделать p недействительным в C++11.

Используя старую реализацию std::string с подсчетом ссылок в GCC, этот код имеет неопределенное поведение, потому что p является недействительным, становясь висячим указателем. (Происходит следующее: когда создается s2, он разделяет данные с s, но получение неконстантной ссылки через s[0] требует, чтобы данные не были разделены, поэтому s выполняет «копирование при записи», потому что ссылка s[0] потенциально может использоваться для запись в s, затем s2 выходит за пределы области видимости, уничтожая массив, на который указывает p).

Стандарт C++03 явно разрешает такое поведение в 21.3 [lib.basic.string] p5, где говорится, что после вызова data() первый вызов operator[]() может сделать указатели, ссылки и итераторы недействительными. Таким образом, строка COW GCC была корректной реализацией C++03.

Стандарт C++11 больше не разрешает такое поведение, потому что ни один вызов operator[]() не может сделать недействительными указатели, ссылки или итераторы, независимо от того, следуют ли они за вызовом data().

Таким образом, приведенный выше пример должен работать в C++11, но не работает со строкой COW типа libstdc++, поэтому такая строка COW не разрешена в C++. 11.

Да, CoW — приемлемый механизм для создания более быстрых строк... но...

это делает многопоточный код медленнее (все эти блокировки для проверки того, что вы единственный, кто пишет, убивает производительность при использовании большого количества строк). Это было основной причиной, по которой CoW был уничтожен много лет назад.

Другие причины заключаются в том, что оператор [] вернет вам строковые данные без какой-либо защиты для вас от перезаписи строки, которую кто-то другой считает неизменной. То же самое относится к c_str() и data().

Быстрый Google говорит, что многопоточность в основном является причиной, по которой она была фактически запрещена (не явно).

В предложении сказано:

Предложение

Мы предлагаем сделать все операции доступа к итераторам и элементам безопасными и одновременно выполняемыми.

Мы повышаем стабильность операций даже в последовательном коде.

Это изменение эффективно запрещает реализацию копирования при записи.

с последующим

Самая большая потенциальная потеря производительности из-за отказа от реализации копирования при записи — это повышенное потребление памяти для приложений с очень большими строками, предназначенными в основном для чтения. Однако мы считаем, что для этих приложений веревки являются лучшим техническим решением, и рекомендуем рассмотреть предложение о веревках для включения в библиотеку TR2.

Веревки являются частью STLPort и SGI STL.

Из 21.4.2 конструкторы basic_string и операторы присваивания [string.cons]

basic_string(const basic_string<charT,traits,Allocator>& str);

[...]

2 Эффекты: создает объект класса basic_string, как указано в таблице 64. [...]

В таблице 64 полезно показано, что после построения объекта с помощью этого (копирующего) конструктора this->data() имеет значение:

указывает на первый элемент выделенной копии массива, на первый элемент которого указывает str.data()

Аналогичные требования предъявляются и к другим подобным конструкторам.

Поскольку теперь гарантируется, что строки хранятся непрерывно, и теперь вам разрешено брать указатель на внутреннее хранилище строки (т.е. &str[0] работает так же, как и для массива), невозможно сделать полезный COW выполнение. Вы должны были бы сделать копию для слишком многих вещей. Даже простое использование operator[] или begin() для неконстантной строки потребует копирования.

Запрещен ли COW basic_string в C++11 и более поздних версиях?

Касательно

Правильно ли я понимаю, что C++11 не поддерживает реализацию std::string на основе COW?

Да.

Касательно

Если да, указано ли это ограничение явно где-то в новом стандарте (где)?

Почти напрямую, по требованиям постоянной сложности для ряда операций, которые потребуют O(n) физического копирования строковых данных в COW выполнение.

Например, для функций-членов

auto operator[](size_type pos) const -> const_reference;
auto operator[](size_type pos) -> reference;

что в реализации COW ¹оба инициируют копирование строковых данных, чтобы отменить совместное использование строкового значения, стандарт C++11 требует

Сложность: постоянное время.

что исключает такое копирование данных и, следовательно, COW.

C++03 поддерживал реализации COW, отсутствие этих требований к постоянной сложности и, при определенных ограничительных условиях, разрешая вызовы operator[](), at(), begin(), rbegin(), end() или rend() для аннулирования ссылок, указателей. итераторы, относящиеся к элементам строки, т.е. для возможного копирования данных COW. Эта поддержка была удалена в C++11.

Запрещен ли COW также правилами аннулирования C++11?

В другом ответе, который на момент написания был выбран в качестве решения, за который активно проголосовали и, следовательно, по-видимому, ему поверили, утверждается, что

Для строки COW вызов non-const operator[] потребует создания копии (и аннулирования ссылок), что запрещено абзацем [в кавычках] выше [C++11 §21.4.1/6]. . Следовательно, в С++ 11 больше не разрешено иметь строку COW.

Это утверждение неверно и вводит в заблуждение по двум основным причинам:

• Это неверно указывает, что только методы доступа к элементам, отличные от const, должны инициировать копирование данных COW.
  Но также методы доступа к элементам const должны запускать копирование данных, поскольку они позволяют клиентскому коду формировать ссылки или указатели, которые (в C++11) не разрешается позже аннулировать с помощью операций, которые могут инициировать копирование данных COW.
• Ошибочно предполагается, что копирование данных COW может привести к аннулированию ссылки.
  Но в правильной реализации копирование данных COW, отменяющее совместное использование строкового значения, выполняется до того, как появятся какие-либо ссылки, которые могут быть признан недействительным.

Чтобы увидеть, как будет работать правильная реализация C++11 COW для basic_string, когда игнорируются требования O(1), делающие это недействительным, подумайте о реализации, в которой строка может переключаться между политиками владения. Экземпляр строки начинается с политики Sharable. Если эта политика активна, ссылки на внешние элементы быть не могут. Экземпляр может перейти к уникальной политике, и он должен сделать это, когда потенциально создается ссылка на элемент, например, при вызове .c_str() (по крайней мере, если это создает указатель на внутренний буфер). В общем случае, когда несколько экземпляров совместно владеют значением, это влечет за собой копирование строковых данных. После этого перехода к уникальной политике экземпляр может вернуться обратно к совместно используемому только с помощью операции, которая делает недействительными все ссылки, например назначение.

Таким образом, хотя вывод этого ответа о том, что строки COW исключены, является правильным, предлагаемое рассуждение неверно и сильно вводит в заблуждение.

Я подозреваю, что причиной этого недоразумения является ненормативное примечание в приложении C C++11:

Изменение: требования basic_string больше не допускают использование строк с подсчетом ссылок
Обоснование: недействительность строк с подсчетом ссылок немного отличается. Это изменение упорядочивает поведение (так в оригинале) для этого международного стандарта.
Влияние на исходную функцию: Действительный код C++ 2003 может выполняться по-другому в этом международном стандарте.

Здесь обоснование объясняет основную почему было решено удалить специальную поддержку COW C++03. Это обоснование, почему, не является тем, как стандарт эффективно запрещает внедрение COW. Стандарт запрещает COW через требования O(1).

Короче говоря, правила аннулирования C++11 не исключают COW-реализации std::basic_string. Но они исключают достаточно эффективную неограниченную реализацию COW в стиле C++03, подобную той, что используется по крайней мере в одной из реализаций стандартной библиотеки g++. Специальная поддержка C++03 COW обеспечила практическую эффективность, в частности использование методов доступа к элементам const, за счет тонких, сложных правил аннулирования:

Ссылки, указатели и итераторы, относящиеся к элементам последовательности 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(), которые возвращают итераторы, первый вызов не-36_ функций-членов operator[](), at(), begin(), rbegin(), end() или rend().

Эти правила настолько сложны и изощренны, что я сомневаюсь, что многие программисты, если вообще найдутся, смогут дать точную сводку. Я не могу.

Что делать, если требования O(1) игнорируются?

Если требования постоянного времени С++ 11, например. operator[] игнорируются, то COW для basic_string может быть технически осуществимым, но сложным в реализации.

Операции, которые могут получить доступ к содержимому строки без копирования данных COW, включают:

• Объединение через +.
• Выход через <<.
• Использование basic_string в качестве аргумента для функций стандартной библиотеки.

Последнее потому, что стандартной библиотеке разрешено полагаться на знания и конструкции, специфичные для реализации.

Кроме того, реализация может предлагать различные нестандартные функции для доступа к содержимому строки без запуска копирования данных COW.

Основным усложняющим фактором является то, что в С++ 11 basic_string доступ к элементу должен инициировать копирование данных (отмена совместного использования строковых данных), но требуется не бросать, например. C++11 §21.4.5/3 Выдает: Ничего.. Таким образом, он не может использовать обычное динамическое выделение для создания нового буфера для копирования данных COW. Один из способов обойти это — использовать специальную кучу, в которой можно зарезервировать память без ее фактического выделения, а затем резервировать необходимый объем для каждой логической ссылки на строковое значение. Резервирование и разрезервирование в такой куче может быть постоянным временем, O(1), а выделение суммы, которая уже зарезервирована, может быть noexcept. Чтобы соответствовать требованиям стандарта, при таком подходе кажется, что должна быть одна такая специальная куча на основе резервирования для каждого отдельного распределителя.

^{Примечания.
¹ Метод доступа к элементу const инициирует копирование данных COW, поскольку он позволяет клиентскому коду получить ссылку или указатель на данные, которые нельзя аннулировать более поздним копирование данных, вызванное, например, метод доступа к элементу, отличный от const.}