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

117

Zrozumiałem, że kopiowanie przy zapisie nie jest realnym sposobem implementacji zgodności std::stringw C ++ 11, ale kiedy pojawiło się to niedawno w dyskusji, nie mogłem bezpośrednio poprzeć tego stwierdzenia.

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

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

Czy też to ograniczenie jest implikowane w tym sensie, że jest to połączony efekt nowych wymagań, std::stringktóry wyklucza implementację opartą na COW std::string. W tym przypadku byłbym zainteresowany wyprowadzeniem stylu rozdziałów i wersetów „C ++ 11 skutecznie zabrania std::stringimplementacji opartych na COW ”.

acm
źródło
5
Błąd GCC dla ich ciągu COW to gcc.gnu.org/bugzilla/show_bug.cgi?id=21334#c45 . Jednym z błędów śledzących nową implementację std :: string w libstdc ++ zgodną z
user7610

Odpowiedzi:

120

Nie jest to dozwolone, ponieważ zgodnie ze standardem 21.4.1 p6 unieważnienie iteratorów / referencji jest dozwolone tylko dla

- jako argument dla dowolnej standardowej funkcji bibliotecznej, przyjmującej jako argument odwołanie do non-const basic_string.

- Wywoływanie funkcji składowych innych niż const, z wyjątkiem operatora [], at, front, back, begin, rbegin, end i rend.

W przypadku łańcucha COW wywołanie wartości innej niż const operator[]wymagałoby wykonania kopii (i unieważnienia odniesień), co jest zabronione w powyższym akapicie. Dlatego nie jest już legalne posiadanie ciągu COW w C ++ 11.

Dave S.
źródło
4
Pewne uzasadnienie: N2534
MM
8
-1 Logika nie wytrzymuje. W czasie kopiowania COW nie ma żadnych odniesień ani iteratorów, które można unieważnić, cały sens kopiowania polega na tym, że takie odniesienia lub iteratory są teraz uzyskiwane, więc kopiowanie jest konieczne. Ale nadal może być tak, że C ++ 11 nie zezwala na implementacje COW.
Pozdrawiam i hth. - Alf,
11
@ Cheersandhth.-Alf: Logikę można zobaczyć poniżej, jeśli COW były dozwolone: std::string a("something"); char& c1 = a[0]; std::string b(a); char& c2 = a[1]; c1 jest odniesieniem do a. Następnie „skopiuj” a. Następnie, gdy spróbujesz wziąć referencję po raz drugi, musi wykonać kopię, aby uzyskać referencję inną niż stała, ponieważ istnieją dwa ciągi wskazujące na ten sam bufor. To musiałoby unieważnić pierwsze wzięte odniesienie i jest sprzeczne z cytowaną powyżej sekcją.
Dave S,
9
@ Cheersandhth.-Alf, zgodnie z tym , przynajmniej implementacja COW GCC robi dokładnie to, co mówi DaveS. Tak więc przynajmniej ten styl COW jest zabroniony przez standard.
Tavian Barnes
4
@Alf: Ta odpowiedź twierdzi, że non-const operator[](1) musi wykonać kopię i (2) jest to nielegalne. Z którym z tych dwóch punktów się nie zgadzasz? Patrząc na twój pierwszy komentarz, wydaje się, że implementacja mogłaby udostępniać ciąg, przynajmniej zgodnie z tym wymaganiem, aż do momentu uzyskania do niego dostępu, ale zarówno dostęp do odczytu, jak i do zapisu musiałby cofnąć udostępnianie. Czy to twoje rozumowanie?
Ben Voigt
48

Odpowiedzi udzielone przez Dave S i gbjbaanbprawidłowe . (I Luc Danton też ma rację, chociaż jest to raczej efekt uboczny zakazu ciągów COW niż oryginalna zasada, która zabrania tego).

Ale żeby wyjaśnić pewne nieporozumienia, dodam trochę dalszych wyjaśnień. Różne komentarze odsyłają do mojego komentarza na bugzilli GCC, który podaje 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 ciąg zliczanych referencji (COW) GCC nie jest prawidłowy w C ++ 11. Standard C ++ 11 wymaga, aby ten kod działał poprawnie. Nic w kodzie nie pozwala na punieważnienie w C ++ 11.

Używając starej std::stringimplementacji zliczanej odwołań GCC , ten kod ma niezdefiniowane zachowanie, ponieważ p jest unieważniony, stając się wiszącym wskaźnikiem. (Dzieje się tak, że gdy s2jest skonstruowany, udostępnia dane s, ale uzyskanie odniesienia innego niż const za pośrednictwem s[0]wymaga, aby dane nie były udostępniane, więc s„kopia podczas zapisu”, ponieważ referencja s[0]może potencjalnie zostać użyta do zapisu s, a następnie s2przechodzi poza zakresem, niszcząc tablicę wskazywaną przez p).

Standard C ++ 03 wyraźnie zezwala na takie zachowanie w 21.3 [lib.basic.string] p5, gdzie mówi, że po wywołaniu data()pierwszego wywołania operator[]()może unieważnić wskaźniki, referencje i iteratory. Zatem łańcuch COW GCC był poprawną implementacją C ++ 03.

Standard C ++ 11 nie zezwala już na takie zachowanie, ponieważ żadne wywołanie nie operator[]()może unieważnić wskaźników, odwołań lub iteratorów, niezależnie od tego, czy następują po wywołaniu data().

Zatem powyższy przykład musi działać w C ++ 11, ale nie działa z łańcuchem typu COW typu libstdc ++, dlatego ten rodzaj łańcucha COW nie jest dozwolony w C ++ 11.

Jonathan Wakely
źródło
3
Implementacja, która usuwa udostępnianie w wywołaniu .data()(i przy każdym zwróceniu wskaźnika, odwołania lub iteratora) nie cierpi z powodu tego problemu. To znaczy (niezmienny) bufor jest w dowolnym momencie niewspółdzielony lub współdzielony bez zewnętrznych referencji. Myślałem, że zamierzyłeś komentarz na temat tego przykładu jako nieformalne zgłoszenie błędu jako komentarz, bardzo przepraszam za nieporozumienie! Ale jak widać, rozważając taką implementację, jak tutaj opisuję, która działa dobrze w C ++ 11, gdy noexceptwymagania są ignorowane, przykład nie mówi nic o formalności. Mogę podać kod, jeśli chcesz.
Pozdrawiam i hth. - Alf
7
Jeśli cofniesz udostępnianie przy prawie każdym dostępie do ciągu, stracisz wszystkie korzyści z udostępniania. Implementacja COW musi być praktyczna, aby standardowa biblioteka zawracała sobie głowę używaniem tego jako std::string, i szczerze wątpię, czy możesz zademonstrować przydatny, wydajny ciąg COW, który spełnia wymagania dotyczące unieważniania C ++ 11. Dlatego uważam, że noexceptspecyfikacje dodane w ostatniej chwili są konsekwencją zakazu ciągów COW, a nie przyczyną. N2668 wydaje się zupełnie jasne, dlaczego nadal zaprzeczasz wyraźnym dowodom intencji komitetu, które zostały tam przedstawione?
Jonathan Wakely
Pamiętaj też, że data()jest to stała funkcja składowa, więc musi być bezpieczna, aby wywołać ją jednocześnie z innymi stałymi składowymi i na przykład wywołać data()współbieżnie z innym wątkiem wykonującym kopię ciągu. Będziesz więc potrzebował całego narzutu muteksu dla każdej operacji na łańcuchach, nawet tych stałych, lub złożoności niezabezpieczonej, zmiennej struktury liczonej jako referencje, a po tym wszystkim, udostępniasz tylko wtedy, gdy nigdy nie zmodyfikujesz ani nie uzyskasz dostępu twoje łańcuchy, tak wiele, wiele łańcuchów będzie miało liczbę odwołań równą jeden. Proszę podać kod, nie krępuj się zignorować noexceptgwarancji.
Jonathan Wakely
2
Po prostu łącząc razem jakiś kod, odkryłem, że jest 129 basic_stringfunkcji składowych plus funkcje bezpłatne. Koszt abstrakcji: ten niezoptymalizowany, niezoptymalizowany, świeży kod wersji zerowej jest od 50 do 100% wolniejszy zarówno w przypadku g ++, jak i MSVC. Nie zapewnia bezpieczeństwa wątków ( shared_ptrwydaje mi się, że jest to łatwe do wykorzystania ) i wystarczy, aby obsługiwać sortowanie słownika na potrzeby synchronizacji, ale błędy modulo dowodzą, że zliczane odwołania basic_stringsą dozwolone, z wyjątkiem noexceptwymagań C ++ . github.com/alfps/In-principle-demo-of-ref-counted-basic_string
Pozdrawiam i hth. - Alf
1
Daj nam kontynuować tę dyskusję w czacie .
Jonathan Wakely
20

To znaczy, CoW jest akceptowalnym mechanizmem tworzenia szybszych ciągów ... ale ...

spowalnia wielowątkowość kodu (całe to blokowanie, aby sprawdzić, czy jesteś jedyną osobą piszącą, zabija wydajność, gdy używasz wielu ciągów). To był główny powód, dla którego CoW został zabity lata temu.

Innym powodem jest to, że []operator zwróci ci dane ciągu, bez żadnej ochrony, abyś mógł nadpisać ciąg, którego ktoś inny oczekuje, że będzie niezmienny. To samo dotyczy c_str()i data().

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

Propozycja mówi:

Wniosek

Proponujemy, aby wszystkie operacje iteratora i dostępu do elementów były bezpiecznie wykonywane jednocześnie.

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

Ta zmiana skutecznie uniemożliwia implementacje kopiowania przy zapisie.

śledzony przez

Największa potencjalna utrata wydajności spowodowana odejściem od implementacji kopiowania przy zapisie to zwiększone zużycie pamięci przez aplikacje z bardzo dużymi ciągami znaków do odczytu. Uważamy jednak, że dla tych zastosowań liny są lepszym rozwiązaniem technicznym i zalecamy rozważenie propozycji lin do włączenia do Biblioteki TR2.

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

gbjbaanb
źródło
2
Kwestia operatora [] nie jest tak naprawdę problemem. Wariant const zapewnia ochronę, a wariant inny niż const zawsze ma możliwość wykonania w tym czasie CoW (lub bycia naprawdę szalonym i ustawiania błędu strony, aby go wywołać).
Christopher Smith,
+1 Przechodzi do problemów.
Pozdrawiam i hth. - Alf,
5
to po prostu głupie, że klasa std :: cow_string nie została dołączona, z lock_buffer () itp. jest wiele razy, gdy wiem, że wątkowanie nie stanowi problemu. w rzeczywistości częściej niż nie.
Erik Aronesty,
Podoba mi się sugestia alternatywnych lin igłowych. Zastanawiam się, czy są dostępne inne alternatywne typy i implementacje.
Voltaire
5

Od 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 basic_stringzgodnie z tabelą 64. [...]

Tabela 64 w pomocny sposób dokumentuje, że po skonstruowaniu obiektu za pomocą tego (kopiującego) konstruktora this->data()ma wartość:

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

Podobne wymagania są stawiane innym podobnym konstruktorom.

Luc Danton
źródło
+1 Wyjaśnia, jak C ++ 11 (przynajmniej częściowo) zabrania COW.
Pozdrawiam i hth. - Alf,
Przepraszam, byłem zmęczony. Nie wyjaśnia to niczego poza tym, że wywołanie .data () musi wyzwolić kopiowanie COW, jeśli bufor jest aktualnie współdzielony. Wciąż jest to przydatne informacje, więc pozwoliłem głosować za.
Pozdrawiam i hth. - Alf
1

Ponieważ jest teraz gwarantowane, że ciągi są przechowywane w sposób ciągły i możesz teraz wziąć wskaźnik do wewnętrznej pamięci ciągu (tj. & Str [0] działa tak jak dla tablicy), nie jest możliwe utworzenie użytecznego COW realizacja. Musiałbyś zrobić kopię dla zbyt wielu rzeczy. Nawet samo użycie operator[]lub begin()na łańcuchu innym niż const wymagałoby kopii.

Dirk Holsopple
źródło
1
Myślę, że ciągi znaków w C ++ 11 są przechowywane w sposób ciągły.
mfontanini
4
W przeszłości trzeba było robić kopie we wszystkich tych sytuacjach i nie było to problemem ...
David Rodríguez - dribeas
@mfontanini tak, ale wcześniej nie było
Dirk Holsopple
3
Chociaż C ++ 11 gwarantuje, że ciągi są ciągłe, jest to ortogonalne do zakazu ciągów COW. Ciąg znaków COW w GCC jest ciągły, więc twoje twierdzenie, że „nie jest możliwe stworzenie użytecznej implementacji COW” jest fałszywe.
Jonathan Wakely
1
@supercat, prośba o magazyn zapasowy (np. przez wywołanie c_str()) musi mieć wartość O (1) i nie może rzucać i nie może wprowadzać wyścigów danych, więc bardzo trudno jest spełnić te wymagania, jeśli leniwie łączysz się. W praktyce jedyną rozsądną opcją jest przechowywanie ciągłych danych.
Jonathan Wakely
1

Czy COW jest basic_stringzabronione w C ++ 11 i nowszych?

Jeżeli chodzi o

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

Tak.

Jeżeli chodzi o

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

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

Na przykład dla funkcji składowych

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

… Co w implementacji COW ¹ spowodowałoby kopiowanie danych ciągów w celu cofnięcia udostępniania wartości ciągu, standard C ++ 11 wymaga

C ++ 11 §21.4.5 / 4 :

Złożoność: stały czas.

… Co wyklucza takie kopiowanie danych, a tym samym COW.

C ++ 03 obsługiwane przez implementacje krowa nie posiadające tych wymagań stałą złożoność, oraz, pod pewnymi warunkami ograniczającymi, pozwalając połączeń do operator[](), at(), begin(), rbegin(), end(), lub rend()do unieważnienia piśmiennictwem, wskaźników i iteratory nawiązujących do elementów łańcuchowych, czyli ewentualnie ponieść Kopiowanie danych COW. Ta obsługa została usunięta w C ++ 11.


Czy COW jest również zabronione przez reguły unieważniania C ++ 11?

W innej odpowiedzi, która w chwili pisania tego tekstu została wybrana jako rozwiązanie i która jest silnie przegłosowana i dlatego najwyraźniej wierzy, że

W przypadku łańcucha COW wywołanie 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]. Dlatego nie jest już legalne posiadanie ciągu COW w C ++ 11.

To stwierdzenie jest błędne i mylące z dwóch głównych powodów:

  • Wskazuje niepoprawnie, że tylko metody dostępu niebędące constpozycjami muszą wyzwalać kopiowanie danych COW.
    Ale także constakcesory elementów muszą wyzwalać kopiowanie danych, ponieważ pozwalają one kodowi klienta na tworzenie referencji lub wskaźników, których (w C ++ 11) nie można później unieważnić poprzez operacje, które mogą wywołać kopiowanie danych COW.
  • Niepoprawnie zakłada, że ​​kopiowanie danych COW może spowodować unieważnienie odniesienia.
    Ale w poprawnej implementacji kopiowanie danych COW, cofanie udostępniania wartości ciągu, jest wykonywane w momencie, gdy istnieją jakiekolwiek odwołania, które można unieważnić.

Aby zobaczyć, jak poprawna implementacja COW w C ++ 11 basic_stringdziałałaby, gdy wymagania O (1), które powodują, że jest to nieprawidłowe, są ignorowane, pomyśl o implementacji, w której łańcuch może przełączać się między zasadami własności. Instancja typu string zaczyna się od zasady Sharable. Gdy ta polityka jest aktywna, nie może być żadnych odwołań do elementów zewnętrznych. Instancja może przejść do strategii Unique i musi to zrobić, gdy potencjalnie zostanie utworzone odwołanie do elementu, na przykład z wywołaniem .c_str()(przynajmniej jeśli spowoduje to wyświetlenie wskaźnika do bufora wewnętrznego). W ogólnym przypadku wielu wystąpień współdzielących własność wartości pociąga za sobą kopiowanie danych ciągu. Po przejściu do unikalnej zasady instancja może przejść z powrotem do Sharable tylko przez operację, która unieważnia wszystkie odwołania, takie jak przypisanie.

Tak więc, chociaż wniosek tej odpowiedzi, że łańcuchy COW są wykluczone, jest poprawny, przedstawione rozumowanie jest nieprawidłowe i mocno mylące.

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

C ++ 11 §C.2.11 [diff.cpp03.strings], o §21.3:

Zmiana : basic_stringwymagania nie zezwalają już na ciągi zliczane jako odwołania
Uzasadnienie: Unieważnienie jest nieco inne niż w przypadku ciągów zliczanych jako odwołania. Ta zmiana reguluje zachowanie (sic) dla niniejszej Normy Międzynarodowej.
Wpływ na oryginalną funkcję: Prawidłowy kod C ++ 2003 może działać inaczej w ramach niniejszej Normy Międzynarodowej

Tutaj uzasadnienie wyjaśnia główne, dlaczego zdecydowano się usunąć specjalną obsługę COW C ++ 03. To uzasadnienie, dlaczego , nie jest tym, jak norma skutecznie zabrania implementacji COW. Norma zabrania COW poprzez wymagania O (1).

Krótko mówiąc, reguły unieważnienia C ++ 11 nie wykluczają implementacji COW std::basic_string. Ale wykluczają w miarę wydajną, nieograniczoną implementację COW w stylu C ++ 03, taką jak ta w przynajmniej jednej z implementacji bibliotek standardowych g ++. Specjalna obsługa C ++ 03 COW zapewniła praktyczną wydajność, w szczególności przy użyciu constakcesorów do elementów, kosztem subtelnych, złożonych reguł unieważniania:

C ++ 03 §21.3 / 5, który obejmuje obsługę COW „pierwszego połączenia”:

Referencje, wskazówki i iteratory odnoszące się do elementów basic_stringsekwencji może być unieważnione w następujących zastosowaniach tego basic_stringobiektu
- jako argument funkcji trzecimi swap()(21.3.7.8), operator>>()(21.3.7.9) i getline()(21.3. 7.9).
- Jako argument do basic_string::swap().
- Funkcje wywoławcze data()i c_str()członkowskie.
- Wywołanie innych niż constfunkcje składowe, z wyjątkiem operator[](), at(), begin(), rbegin(), end(), i rend().
- Po dowolnego z powyższych zastosowań, z wyjątkiem form insert()i erase()które zwracają iteratorami, pierwsze połączenie na bez constfunkcji składowych operator[](), at(), begin(), rbegin(),end()lub rend().

Zasady te są tak złożone i subtelne, że wątpię, aby wielu programistów, jeśli w ogóle w ogóle, potrafiło podać dokładne podsumowanie. Nie mógłbym.


Co się stanie, jeśli zignoruje się wymagania O (1)?

Jeśli np. Wymagania dotyczące stałego czasu C ++ 11 operator[]zostaną zignorowane, wówczas COW dla basic_stringmoże być technicznie wykonalne, ale trudne do wdrożenia.

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

  • Łączenie za pośrednictwem +.
  • Wyjście przez <<.
  • Używanie basic_stringjako argumentu do standardowych funkcji bibliotecznych.

To drugie, ponieważ biblioteka standardowa może polegać na specyficznej dla implementacji wiedzy i konstrukcjach.

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

Głównym czynnikiem komplikującym jest to, że w C ++ 11 basic_stringdostęp do pozycji musi wyzwalać kopiowanie danych (cofanie udostępniania danych ciągu), ale nie jest wymagany, aby go nie rzucać , np. C ++ 11 §21.4.5 / 3 „ Zgłasza: Nic.”. Dlatego nie może używać zwykłej alokacji dynamicznej do tworzenia nowego bufora do kopiowania danych COW. Jednym ze sposobów obejścia tego jest użycie specjalnej sterty, w której można zarezerwować pamięć bez faktycznej alokacji, a następnie zarezerwowanie wymaganej ilości dla każdego logicznego odwołania do wartości ciągu. Rezerwowanie i anulowanie rezerwacji w takiej stercie może być stałe w czasie, O (1), a alokowanie kwoty, którą już zarezerwowano, może byćnoexcept. Aby spełnić wymagania normy, przy takim podejściu wydaje się, że potrzebna byłaby jedna taka specjalna sterta oparta na rezerwacji dla każdego rozdzielacza.


Uwagi:
¹ Akcesor constpozycji wyzwala kopiowanie danych COW, ponieważ umożliwia kodowi klienta uzyskanie odniesienia lub wskaźnika do danych, których nie można unieważnić przez późniejsze kopiowanie danych wyzwalane np. Przez constakcesor niebędący elementem.

Pozdrawiam i hth. - Alf
źródło
3
Twój przykład jest dobrym przykładem niepoprawnej implementacji dla C ++ 11. Prawdopodobnie była poprawna dla C ++ 03”. Tak , o to chodzi w tym przykładzie . Pokazuje ciąg COW, który był legalny w C ++ 03, ponieważ nie łamie starych reguł unieważniania iteratorów i nie jest legalny w C ++ 11, ponieważ łamie nowe reguły unieważniania iteratorów. Zaprzecza też stwierdzeniu, które przytoczyłem w powyższym komentarzu.
Jonathan Wakely
2
Gdybyś powiedział udostępnianych nie początkowo wspólne bym nie twierdził. Powiedzenie, że coś jest na początku udostępniane, jest po prostu mylące. Udostępniony sobie? Nie to oznacza to słowo. Ale powtarzam: twoja próba argumentowania, że ​​reguły unieważnienia iteratora C ++ 11 nie zabraniają jakiegoś hipotetycznego ciągu COW, który nigdy nie był używany w praktyce (i miałby niedopuszczalną wydajność), podczas gdy z pewnością zabraniają tego rodzaju ciągów COW zastosowany w praktyce jest nieco akademicki i bezcelowy.
Jonathan Wakely
5
Proponowany przez Ciebie ciąg COW jest interesujący, ale nie jestem pewien, czy byłby użyteczny . Celem ciągu COW jest kopiowanie danych ciągu tylko w przypadku, gdy dwa ciągi są zapisywane. Twoja sugerowana implementacja wymaga kopiowania w przypadku wystąpienia dowolnej operacji odczytu zdefiniowanej przez użytkownika. Nawet jeśli kompilator zna tylko odczyt, musi nadal kopiować. Ponadto skopiowanie ciągu Unique spowoduje skopiowanie jego danych (prawdopodobnie do stanu Sharable), co ponownie sprawia, że ​​COW jest raczej bezcelowe. Więc bez gwarancji złożoności, mógłbyś napisać ... naprawdę kiepski ciąg COW.
Nicol Bolas
2
Więc chociaż jesteś technicznie poprawny, że gwarancje złożoności są tym, co uniemożliwia ci napisanie jakiejkolwiek formy COW, to tak naprawdę to [basic.string] / 5 uniemożliwia ci napisanie jakiejkolwiek naprawdę użytecznej formy ciągu COW.
Nicol Bolas
4
@JonathanWakely: (1) Twój cytat nie jest pytaniem. Oto pytanie: „Czy mam rację, że C ++ 11 nie dopuszcza opartych na COW implementacji std :: string? Jeśli tak, czy to ograniczenie zostało wyraźnie określone gdzieś w nowym standardzie (gdzie)? ” (2) Twoja opinia, że ​​COW std::string, pomijając wymagania O (1), byłaby nieefektywna, jest Twoją opinią. Nie wiem, jaki mógłby być występ, ale myślę, że to stwierdzenie jest wysuwane bardziej ze względu na jego odczucie, ze względu na wibracje, które przekazuje, niż ze względu na jakiekolwiek znaczenie dla tej odpowiedzi.
Pozdrawiam i hth. - Alf
0

Zawsze zastanawiałem się nad niezmiennymi krowami: kiedy krowa zostanie stworzona, mogłem się zmienić tylko poprzez przypisanie z innej krowy, dzięki czemu będzie to zgodne ze standardem.

Miałem dziś czas, aby wypróbować to w celu przeprowadzenia prostego testu porównawczego: mapa o rozmiarze N z kluczem ciąg / krowa, z każdym węzłem zawierającym zestaw wszystkich ciągów na mapie (mamy liczbę obiektów NxN).

Przy łańcuchach o rozmiarze ~ 300 bajtów i N = 2000 krowy są nieco szybsze i używają prawie o rząd wielkości mniej pamięci. Zobacz poniżej, rozmiary podano w kilogramach, wybieg b dotyczy krów.

~/icow$ ./tst 2000
preparation a
run
done a: time-delta=6 mem-delta=1563276
preparation b
run
done a: time-delta=3 mem-delta=186384
zzz777
źródło