Legalność COW std:: implementacja string w C++11

Odpowiedzi autorstwa Dave ' a S i gbjbaanb są poprawne . (I Luc Danton też jest poprawny, chociaż to raczej efekt uboczny zakazywania sznurków krów niż oryginalna zasada, która tego zabrania.)

Ale aby wyjaśnić pewne zamieszanie, dodam trochę dalszej ekspozycji. Różne komentarze link do mojego komentarza na Bugzilli GCC który daje następujący przykład:

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

Celem tego przykładu jest wykazanie, dlaczego GCC ' s reference counted (COW) string is not valid in C++11. Standard C++11 wymaga poprawnego działania tego kodu. Nic w kodzie nie pozwala na unieważnienie p W C++11.

Używając starej implementacji GCC z liczeniem referencji std::string, kod ten Ma nieokreślone zachowanie, ponieważ p jest unieważniony, stając się zwisającym wskaźnikiem. (Dzieje się tak, że gdy s2 jest skonstruowany, dzieli dane z s, ale uzyskanie odniesienia non-const poprzez s[0] wymaga dane nie będą udostępniane, więc s wykonuje "kopię przy zapisie", ponieważ Referencja s[0] może potencjalnie zostać użyta do zapisu do s, a następnie s2 wychodzi poza zakres, niszcząc tablicę wskazywaną przez p).

Standard C++03 wyraźnie zezwala na takie zachowanie w 21.3 [lib.podstawowe.string] p5, gdzie mówi, że po wywołaniu data() pierwsze wywołanie operator[]() może unieważnić wskaźniki, referencje i Iteratory. Więc ciąg krowy GCC był poprawnym C++03 wdrożenie.

Standard C++11 nie pozwala już na takie zachowanie, ponieważ żadne wywołanie do operator[]() nie może unieważnić wskaźników, odniesień lub iteratorów, niezależnie od tego, czy wykonują one wywołanie do data().

Tak więc powyższy przykład musi działać w C++11, ale nie działa z rodzajem COW string libstdc++, dlatego taki rodzaj COW string nie jest dozwolony w C++11.

Jest, krowa jest akceptowalnym mechanizmem do tworzenia szybszych strun... ale...

To sprawia, że wielowątkowość kodu jest wolniejsza (całe to blokowanie, aby sprawdzić, czy tylko ty piszesz zabija wydajność przy użyciu wielu ciągów). To był główny powód, dla którego Krowa została zabita lata temu.

Inne powody są takie, że operator [] zwróci ci dane ciągu znaków, bez żadnej ochrony przed nadpisaniem ciągu, którego ktoś inny oczekuje, że będzie niezmienny. To samo dotyczy c_str() i data().

Szybkie Google mówi, że wielowątkowość jest w zasadzie powodem, dla którego została skutecznie wykluczona (nie wprost).

Propozycja mówi:

Propozycja

Proponujemy, aby wszystkie operacje dostępu do iteratora i elementu były bezpieczne jednocześnie wykonywalny.

Zwiększamy stabilność operacji nawet w kodzie sekwencyjnym.

Ta zmiana skutecznie uniemożliwia kopiowanie przy zapisie wdrożenia.

Po którym następuje

Największa potencjalna strata w wydajności spowodowana odejściem od implementacje typu copy-on-write to zwiększone zużycie pamięci dla aplikacji z bardzo dużymi odczytami-głównie ciągami znaków. Jednak my wierzę, że do tych zastosowań liny są lepszym technicznym rozwiązanie, i zalecają rozważenie propozycji linowej do włączenia w Biblioteka TR2.

Liny są częścią STLPort i SGI STL.

Z 21.4.2 konstruktory basic_string i operatory przypisania [string.cons]

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

[...]

2 efekty : konstruuje obiekt klasy {[1] } Jak wskazano w tabeli 64. [...]

Tabela 64 pomocnie dokumentuje, że po zbudowaniu obiektu za pomocą tego (kopiującego) konstruktora, this->data() ma jako wartość:

Wskazuje na pierwszy element przydzielonej kopii tablicy, na której pierwszy element jest wskazywany przez str.data ()

Istnieją podobne wymagania dla innych podobnych konstruktorów.

Ponieważ jest teraz gwarantowane, że łańcuchy są przechowywane równolegle i możesz teraz wziąć wskaźnik do wewnętrznej pamięci łańcucha (tzn. & str[0] działa tak, jak w przypadku tablicy), nie jest możliwe stworzenie użytecznej implementacji COW. Musiałbyś zrobić kopię za dużo rzeczy. Nawet samo użycie operator[] LUB begin() na niekonstowym łańcuchu wymagałoby kopii.

czy krowa basic_string jest zabroniona w C++11 i późniejszych?

Odnośnie

" Czy mam rację, że C++11 nie dopuszcza implementacji std::string?

Tak.

Odnośnie

" Jeśli tak, to czy to ograniczenie jest wyraźnie określone gdzieś w nowym standardzie (gdzie)?

prawie bezpośrednio, przez wymagania stałej złożoności dla liczba operacji, które wymagałyby o (N) fizycznego kopiowania danych łańcuchowych w implementacji COW.

Na przykład dla funkcji Członkowskich

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

" złożoność: stały czas.

... co wyklucza takie kopiowanie danych, a co za tym idzie, Krowa.

C++03 obsługiwał implementacje cow przez nie mające te stałe wymagania złożoności, oraz przez, pod pewnymi restrykcyjnymi warunkami, zezwalające na wywołania do operator[](), at(), begin(), rbegin(), end(), lub rend() unieważnić referencje, wskaźniki i Iteratory odnoszące się do pozycji łańcuchowych, tzn. ewentualnie ponieść kopiowanie danych COW. Ta obsługa została usunięta w C++11.

czy krowa jest również zabroniona przez zasady unieważniania C++11?

W w 2011 roku, po raz pierwszy w Polsce, w 2015 roku, w Polsce i na świecie, w 2017 roku, w Polsce i na świecie, w 2018 roku, w Polsce i na świecie, w 2019 roku, w Polsce i na świecie.]}

" dla krowiego Sznurka, nazywającego non-const operator[] wymagałoby wykonania kopii (i unieważnienia odniesień), co jest zabronione przez [cytowany] akapit powyżej [C++11 §21.4.1/6]. Z tego powodu nie jest już legalne posiadanie Cow string w C++11.

Twierdzenie to jest nieprawidłowe i wprowadzające w błąd w dwóch głównych sposoby:

• błędnie wskazuje, że tylko nie-const Accesory elementów muszą uruchomić kopiowanie danych COW.
  Ale również Accesory pozycji const muszą wyzwalać kopiowanie danych, ponieważ pozwalają kodowi klienta tworzyć referencje lub wskaźniki, które (w C++11) nie mogą być później unieważniane poprzez operacje, które mogą wyzwalać kopiowanie danych COW.
• błędnie zakłada się, że kopiowanie danych krów może spowodować unieważnienie.
  Jednak w poprawnej implementacji kopiowanie danych, nie dzielenie wartości ciągu, odbywa się w punkcie przed pojawieniem się jakichkolwiek odwołań, które mogą zostać unieważnione.

Aby zobaczyć, jak poprawna implementacja basic_string C++11 Cow będzie działać, gdy wymagania O(1), Które Sprawiają, że jest to nieprawidłowe są ignorowane, pomyśl o implementacji, w której łańcuch znaków może przełączać się między politykami własności. Instancja łańcuchowa zaczyna się od funkcji "policy Sharable". Przy aktywnej polityce można brak zewnętrznych odniesień do pozycji. Instancja może przejść do unikalnej polityki i musi to zrobić, gdy potencjalnie zostanie utworzona Referencja do elementu, na przykład wywołanie .c_str() (przynajmniej jeśli spowoduje to powstanie wskaźnika do wewnętrznego bufora). W ogólnym przypadku wielu instancji współdzielących własność wartości, wiąże się to z kopiowaniem danych łańcuchowych. Po przejściu do unique policy instancja może powrócić do Sharable tylko przez operację, która unieważnia wszystkie odwołania, takie jak zadanie.

Tak więc, podczas gdy wniosek tej odpowiedzi, że sznurki krów są wykluczone, jest poprawny, przedstawione rozumowanie jest błędne i silnie mylące.

Podejrzewam, że przyczyną tego nieporozumienia jest notatka nienormatywna w C++11 W załączniku C:

Zmień: basic_string Wymagania nie zezwalają już na ciągi z liczeniem referencji
uzasadnienie: unieważnienie jest subtelnie odmienne od reference-policzone ciągi. Zmiana ta reguluje zachowanie (SIC) dla tego międzynarodowego standardu.
wpływ na oryginalną funkcję: poprawny kod C ++ 2003 może być wykonywany inaczej w tym międzynarodowym standardzie

Tutaj uzasadnienie wyjaśnia podstawowe dlaczego zdecydowano się usunąć specjalne Wsparcie dla krów C++03. To uzasadnienie, dlaczego , nie jest jak norma skutecznie uniemożliwia wdrożenie krów. Standard zakazuje Krowa poprzez wymagania O(1).

W skrócie, Zasady C++11 nie wykluczają implementacji std::basic_string. Jednak wykluczają dość wydajną, nieskrępowaną implementację C++03 W Stylu COW, taką jak ta w co najmniej jednej ze standardowych implementacji biblioteki g++. W 1999 roku, w wyniku prac nad nowym systemem C++, wprowadzono nową wersję C++, która została wprowadzona w 1999 roku.]} C++03 §21.3/5 który obejmuje obsługa krów" first call":

" odniesienia, wskaźniki i Iteratory odnoszące się do elementów sekwencji basic_string mogą być unieważnione przez następujące zastosowania tego basic_string obiektu:
- Jako argument do funkcji nieczłonkowychswap() (21.3.7.8), operator>>() (21.3.7.9), i getline() (21.3.7.9).
- Jako argument do basic_string::swap().
- Wywołanie data() i c_str() funkcji Członkowskich.
- Wywołanie funkcji Nie - const członkowskich, z wyjątkiem operator[](), at(), begin(), rbegin(), end(), oraz rend().
- Po którymkolwiek z powyższych zastosowań, z wyjątkiem form insert() i erase(), które zwracają Iteratory, pierwsze wywołanie funkcji Nie-const operator[](), at(), begin(), rbegin(), end(), lub rend().

Te zasady są tak złożone i subtelne, że wątpię, aby wielu programistów, jeśli w ogóle, mogło podać dokładne podsumowanie. Nie mogłem.

Co zrobić, jeśli wymagania O(1) nie są brane pod uwagę?

Jeśli wymagania dotyczące czasu stałego C++11 na np. operator[] są 2012-01-23 15: 00:00

Operacje, które mogłyby uzyskać dostęp do zawartości łańcucha bez konieczności kopiowania danych COW obejmują:

• konkatenacja przez +.
• wyjście przez <<.
• używanie basic_string jako argumentu do standardowych funkcji bibliotecznych.

Ten ostatni, ponieważ biblioteka standardowa może opierać się na specyficznej wiedzy implementacyjnej i konstrukcje.

Dodatkowo implementacja może oferować różne niestandardowe funkcje dostępu do zawartości łańcuchów bez uruchamiania kopiowania danych COW.

Głównym czynnikiem komplikującym jest to, że w C++11 basic_string dostęp do pozycji musi wyzwalać kopiowanie danych (nie-dzielenie danych łańcuchowych), ale jest wymagany nie rzucać , np.++11 §21.4.5/3 " nic.". Nie można więc użyć zwykłej dynamicznej alokacji do utworzenia nowego bufora do kopiowania danych krów. One way around jest to użycie specjalnej sterty, w której pamięć może być zarezerwowana bez rzeczywistego przydzielania, a następnie zarezerwować wymaganą ilość dla każdego odniesienia logicznego na wartość łańcuchową. Rezerwowanie i nie-rezerwowanie w takiej stercie może być czasem stałym, O (1), A przydzielenie kwoty, którą już zarezerwowano, może być noexcept. Aby spełnić wymagania normy, przy takim podejściu wydaje się, że musiałaby istnieć jedna taka specjalna sterta oparta na zastrzeżeniach na odrębnych allocator.

^{uwagi:
1 const item accessor uruchamia kopiowanie danych COW, ponieważ pozwala kodowi klienta uzyskać odniesienie lub wskaźnik do danych, których nie można unieważnić przez późniejsze kopiowanie danych wywołane np. przez nie-const item accessor.}