Законност на внедряването на COW std::string в C++11

Не е позволено, тъй като съгласно стандарта 21.4.1 p6, анулирането на итератори/препратки е разрешено само за

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

— Извикване на неконстантни членски функции, с изключение на operator[], at, front, back, begin, rbegin, end и rend.

За низ COW извикването на non-const operator[] ще изисква правене на копие (и обезсилване на препратки), което е забранено от параграфа по-горе. Следователно вече не е законно да имате COW низ в C++11.

Отговорите на Dave S и gbjbaanb са правилни. (И това на Люк Дантон също е правилно, въпреки че е по-скоро страничен ефект от забраната на низовете COW, отколкото първоначалното правило, което го забранява.)

Но за да изясня някои обърквания, ще добавя още малко изложение. Различни коментари препращат към мой коментар за GCC bugzilla, който дава следния пример:

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().

Quick google казва, че многонишковостта е основно причината, поради която е ефективно забранено (не изрично).

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

Предложение

Ние предлагаме да направим всички итератори и операции за достъп до елемент безопасно едновременно изпълними.

Увеличаваме стабилността на операциите дори в последователен код.

Тази промяна ефективно забранява внедряването на копиране при запис.

следван от

Най-голямата потенциална загуба на производителност, дължаща се на преминаване от реализации на копиране при запис, е увеличеното потребление на памет за приложения с много големи низове, предимно за четене. Ние обаче вярваме, че за тези приложения въжетата са по-добро техническо решение и препоръчваме да се разгледа предложение за въже за включване в библиотека TR2.

Въжетата са част от STLPort и SGIs 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 извикването на не-const operator[] ще изисква правене на копие (и обезсилване на препратки), което е забранено от [цитирания] параграф по-горе [C++11 §21.4.1/6] . Следователно вече не е законно да имате COW низ в C++11.

Това твърдение е неправилно и подвеждащо по два основни начина:

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

За да видите как би работило правилно C++11 COW изпълнение на basic_string, когато изискванията на O(1), които правят това невалидно, се игнорират, помислете за изпълнение, при което низ може да превключва между правилата за собственост. Екземплярът на низ започва с правило Споделяемо. Когато тази политика е активна, не може да има препратки към външни елементи. Екземплярът може да премине към уникална политика и трябва да го направи, когато е потенциално създадена препратка към елемент, като например с извикване на .c_str() (поне ако това създава указател към вътрешния буфер). В общия случай на множество екземпляри, споделящи собствеността върху стойността, това води до копиране на низовите данни. След този преход към Уникална политика екземплярът може да премине обратно към Споделяем само чрез операция, която прави невалидни всички препратки, като например присвояване.

Така че, докато заключението на този отговор, че низовете COW са изключени, е правилно, предложеното разсъждение е неправилно и силно подвеждащо.

Подозирам, че причината за това недоразумение е ненормативна бележка в приложение C на C++11:

Промяна: Изискванията на basic_string вече не позволяват низове с преброени препратки
Обосновка: Невалидността е леко различна при низове с преброени препратки. Тази промяна регулира поведението (sic) за този международен стандарт.
Ефект върху оригиналната характеристика: Валиден C ++ 2003 код може да се изпълнява по различен начин в този международен стандарт

Тук обосновката обяснява основната защо човек реши да премахне специалната поддръжка на C++03 COW. Тази обосновка, защо, не е как стандартът ефективно забранява прилагането на 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(), които връщат итератори, първото извикване на не-const членски функции operator[](), at(), begin(), rbegin(), end() или rend().

Тези правила са толкова сложни и фини, че се съмнявам, че много програмисти, ако има такива, биха могли да дадат точно обобщение. Аз не можах.

Ами ако изискванията O(1) не бъдат взети предвид?

Ако C++11 изискванията за постоянно време на напр. operator[] се пренебрегват, тогава COW за basic_string може да бъде технически осъществимо, но трудно за изпълнение.

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

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

Последното, защото на стандартната библиотека е разрешено да разчита на специфични знания и конструкции за изпълнение.

Освен това внедряването може да предложи различни нестандартни функции за достъп до съдържанието на низове, без да задейства копиране на COW данни.

Основен усложняващ фактор е, че в C++11 basic_string достъпът до елемент трябва да задейства копиране на данни (прекратяване на споделянето на низовите данни), но се изисква да не се хвърля, напр. C++11 §21.4.5/3 Хвърля: Нищо.. И така не може да използва обикновено динамично разпределение, за да създаде нов буфер за копиране на COW данни. Един от начините за заобикаляне на това е да се използва специална купчина, където паметта може да бъде резервирана, без да бъде действително разпределена, и след това да се запази необходимата сума за всяка логическа препратка към стойност на низ. Резервирането и премахването на резервирането в такава купчина може да бъде постоянно време, O(1), а разпределянето на сумата, която вече е резервирана, може да бъде noexcept. За да се спазват изискванията на стандарта, с този подход изглежда, че ще трябва да има една такава специална купчина, базирана на резервации, за всеки отделен разпределител.

^{Бележки:
¹ Инструментът за достъп до елемент const задейства копиране на COW данни, тъй като позволява на клиентския код да получи препратка или указател към данните, които не е разрешено да обезсилва от по-късен копиране на данни, задействано от напр. не-const елементът за достъп.}