Rechtmäßigkeit der Implementierung von COW std :: string in C ++ 11

117

Ich hatte verstanden, dass Copy-on-Write kein praktikabler Weg ist, um eine Konformität std::stringin C ++ 11 zu implementieren , aber als es kürzlich in der Diskussion auftauchte, war ich nicht in der Lage, diese Aussage direkt zu unterstützen.

Stimmt es, dass C ++ 11 keine COW-basierten Implementierungen von zulässt std::string?

Wenn ja, wird diese Einschränkung ausdrücklich irgendwo in der neuen Norm angegeben (wo)?

Oder ist diese Einschränkung impliziert, in dem Sinne , dass es die kombinierte Wirkung der neuen Anforderungen an ist , std::stringdass verbietet eine KUH - basierte Implementierung von std::string. In diesem Fall würde mich eine Kapitel- und Versstilableitung von "C ++ 11 verbietet COW-basierte std::stringImplementierungen" interessieren .

acm
quelle
5
Der GCC-Fehler für die COW-Zeichenfolge lautet gcc.gnu.org/bugzilla/show_bug.cgi?id=21334#c45 . Einer der Fehler, der eine neue C ++ 11-Compilant-Implementierung von std :: string in libstdc ++ verfolgt, ist gcc.gnu.org/bugzilla/show_bug.cgi?id=53221
user7610

Antworten:

120

Dies ist nicht zulässig, da gemäß Standard 21.4.1 p6 die Ungültigmachung von Iteratoren / Referenzen nur zulässig ist

- als Argument für eine Standardbibliotheksfunktion, die einen Verweis auf non-const basic_string als Argument verwendet.

- Aufrufen von Nicht-Konstanten-Elementfunktionen, außer Operator [], an, vorne, hinten, Anfang, Anfang, Ende und Wiedergabe.

Für eine COW-Zeichenfolge würde das Aufrufen von non-const operator[]das Erstellen einer Kopie (und das Ungültigmachen von Verweisen) erfordern, was im obigen Absatz nicht zulässig ist. Daher ist es in C ++ 11 nicht mehr legal, eine COW-Zeichenfolge zu haben.

Dave S.
quelle
4
Einige Gründe
MM
8
-1 Die Logik hält kein Wasser. Zum Zeitpunkt eines COW-Kopierens gibt es keine Referenzen oder Iteratoren, die ungültig gemacht werden können. Der springende Punkt beim Kopieren ist, dass solche Referenzen oder Iteratoren jetzt abgerufen werden, sodass ein Kopieren erforderlich ist. Es kann jedoch sein, dass C ++ 11 COW-Implementierungen nicht zulässt.
Prost und hth. - Alf
11
@ Cheersandhth.-Alf: Die Logik kann im Folgenden gesehen werden, wenn COW erlaubt wäre: std::string a("something"); char& c1 = a[0]; std::string b(a); char& c2 = a[1]; c1 ist eine Referenz auf a. Sie "kopieren" dann a. Wenn Sie dann versuchen, die Referenz das zweite Mal zu übernehmen, muss eine Kopie erstellt werden, um eine nicht konstante Referenz zu erhalten, da zwei Zeichenfolgen auf denselben Puffer verweisen. Dies müsste die erste Referenz ungültig machen und widerspricht dem oben zitierten Abschnitt.
Dave S
9
@ Cheersandhth.-Alf, nach dieser , zumindest COW Implementierung des GCC ist genau das tun , was DaveS sagt. Zumindest diese Art der Kuh ist also durch den Standard verboten.
Tavian Barnes
4
@Alf: Diese Antwort argumentiert, dass Nicht-Konstante operator[](1) eine Kopie erstellen muss und dass (2) dies illegal ist. Mit welchem ​​dieser beiden Punkte sind Sie nicht einverstanden? Wenn Sie sich Ihren ersten Kommentar ansehen, scheint es, dass eine Implementierung die Zeichenfolge zumindest unter dieser Anforderung bis zum Zeitpunkt des Zugriffs gemeinsam nutzen könnte, aber dass sowohl Lese- als auch Schreibzugriffe die Freigabe aufheben müssten. Ist das deine Argumentation?
Ben Voigt
48

Die Antworten von Dave S und gbjbaanb sind richtig . (Und Luc Dantons ist auch richtig, obwohl es eher ein Nebeneffekt des Verbots von COW-Strings ist als die ursprüngliche Regel, die es verbietet.)

Aber um einige Verwirrung zu beseitigen, werde ich eine weitere Darstellung hinzufügen. Verschiedene Kommentare verweisen auf einen meiner Kommentare zum GCC-Bugzilla, der das folgende Beispiel enthält:

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

In diesem Beispiel soll gezeigt werden, warum die COW-Zeichenfolge (Reference Counted) von GCC in C ++ 11 nicht gültig ist. Der C ++ 11-Standard erfordert, dass dieser Code ordnungsgemäß funktioniert. Nichts im Code erlaubt pes, das in C ++ 11 ungültig zu machen.

Mit GCC alten Referenzzählung std::stringImplementierung hat , dass Code nicht definiertes Verhalten, da p wird für ungültig erklärt, zu einem baumelnden Zeiger. (Was passiert ist, dass, wenn es erstellt s2wird, es die Daten mit teilt s, aber um eine nicht konstante Referenz über zu erhalten, s[0]müssen die Daten nicht freigegeben werden, ebenso swie eine "Kopie beim Schreiben", da die Referenz s[0]möglicherweise zum Schreiben verwendet werden könnte s, und dann s2geht außerhalb des Gültigkeitsbereichs, Zerstörung des Arrays, auf das durch gezeigt wird p).

Der C ++ 03-Standard erlaubt dieses Verhalten explizit in 21.3 [lib.basic.string] p5, wo er besagt, dass nach einem Aufruf data()des ersten Aufrufs an operator[]()Zeiger, Referenzen und Iteratoren ungültig werden können. Die COW-Zeichenfolge von GCC war also eine gültige C ++ 03-Implementierung.

Der C ++ 11-Standard erlaubt dieses Verhalten nicht mehr , da kein Aufruf von operator[]()Zeigern, Referenzen oder Iteratoren ungültig machen kann, unabhängig davon, ob sie einem Aufruf von folgen data().

Das obige Beispiel muss also in C ++ 11 funktionieren, funktioniert jedoch nicht mit der Art der COW-Zeichenfolge von libstdc ++. Daher ist diese Art der COW-Zeichenfolge in C ++ 11 nicht zulässig.

Jonathan Wakely
quelle
3
Eine Implementierung, die beim Aufruf von .data()(und bei jeder Rückgabe von Zeiger, Referenz oder Iterator) die Freigabe aufhebt , leidet nicht unter diesem Problem. Das heißt (invariant), dass ein Puffer jederzeit nicht freigegeben oder ohne externe Verweise freigegeben wird. Ich dachte, Sie hätten den Kommentar zu diesem Beispiel als informellen Fehlerbericht als Kommentar gedacht. Es tut mir sehr leid, dass Sie ihn falsch verstanden haben! Wie Sie jedoch sehen können, wenn Sie die hier beschriebene Implementierung in Betracht ziehen, die in C ++ 11 gut funktioniert, wenn noexceptAnforderungen ignoriert werden, sagt das Beispiel nichts über das Formale aus. Ich kann Code bereitstellen, wenn Sie möchten.
Prost und hth. - Alf
7
Wenn Sie bei fast jedem Zugriff auf die Zeichenfolge die Freigabe aufheben, verlieren Sie alle Vorteile der Freigabe. Eine COW-Implementierung muss praktisch sein, damit sich eine Standardbibliothek darum kümmert std::string, und ich bezweifle aufrichtig, dass Sie eine nützliche, performante COW-Zeichenfolge demonstrieren können, die die C ++ 11-Ungültigkeitsanforderungen erfüllt. Daher behaupte ich, dass die noexceptSpezifikationen, die in letzter Minute hinzugefügt wurden, eine Folge des Verbots von COW-Zeichenfolgen sind und nicht der zugrunde liegende Grund. N2668 scheint völlig klar zu sein, warum bestreiten Sie weiterhin die eindeutigen Beweise für die dort skizzierte Absicht des Ausschusses?
Jonathan Wakely
Denken Sie auch daran, dass dies data()eine const-Member-Funktion ist. Sie müssen also sicher sein, gleichzeitig mit anderen const-Mitgliedern aufzurufen und beispielsweise data()gleichzeitig mit einem anderen Thread aufzurufen , der eine Kopie der Zeichenfolge erstellt. Sie benötigen also den gesamten Overhead eines Mutex für jede Zeichenfolgenoperation, auch für konstante, oder die Komplexität einer sperrenfreien, veränderbaren Struktur mit Referenzzählung, und schließlich erhalten Sie nur dann eine Freigabe, wenn Sie nie Änderungen vornehmen oder darauf zugreifen Ihre Zeichenfolgen, so viele, viele Zeichenfolgen, haben eine Referenzanzahl von eins. Bitte geben Sie Code an, ignorieren Sie noexceptGarantien.
Jonathan Wakely
2
Ich habe gerade Code zusammengeschustert und festgestellt, dass es 129 basic_stringMitgliedsfunktionen und freie Funktionen gibt. Abstraktionskosten: Dieser nicht optimierte frische nullte Versionscode von der Stange ist sowohl mit g ++ als auch mit MSVC 50 bis 100% langsamer. Es bietet keine Thread-Sicherheit ( shared_ptrich denke, es ist einfach genug, es zu nutzen ) und es reicht gerade aus, um das Sortieren eines Wörterbuchs zum Zwecke des Timings zu unterstützen, aber Modulo-Fehler beweisen, dass eine gezählte Referenz basic_stringzulässig ist, mit Ausnahme der C ++ - noexceptAnforderungen. github.com/alfps/In-principle-demo-of-ref-counted-basic_string
Prost und hth. - Alf
1
Lassen Sie uns diese Diskussion im Chat fortsetzen .
Jonathan Wakely
20

CoW ist ein akzeptabler Mechanismus, um schnellere Strings zu erstellen ... aber ...

Dadurch wird Multithreading-Code langsamer (all diese Sperren, um zu überprüfen, ob Sie der einzige sind, der die Leistung beeinträchtigt, wenn viele Zeichenfolgen verwendet werden). Dies war der Hauptgrund, warum CoW vor Jahren getötet wurde.

Die anderen Gründe sind, dass der []Operator Ihnen die Zeichenfolgendaten zurückgibt, ohne dass Sie eine Zeichenfolge überschreiben müssen, von der jemand anderes erwartet, dass sie sich nicht ändert. Gleiches gilt für c_str()und data().

Laut Quick Google ist das Multithreading im Grunde der Grund, warum es effektiv nicht zugelassen wurde (nicht explizit).

Der Vorschlag lautet:

Vorschlag

Wir schlagen vor, alle Iterator- und Elementzugriffsvorgänge sicher gleichzeitig ausführbar zu machen.

Wir erhöhen die Stabilität von Operationen auch im sequentiellen Code.

Diese Änderung verbietet effektiv Copy-on-Write-Implementierungen.

gefolgt von

Der größte potenzielle Leistungsverlust aufgrund einer Abkehr von Copy-on-Write-Implementierungen ist der erhöhte Speicherverbrauch für Anwendungen mit sehr großen, meist lesbaren Zeichenfolgen. Wir glauben jedoch, dass Seile für diese Anwendungen eine bessere technische Lösung darstellen, und empfehlen, einen Seilvorschlag für die Aufnahme in die Bibliothek TR2 in Betracht zu ziehen.

Seile sind Teil von STLPort und SGIs STL.

gbjbaanb
quelle
2
Das Operator [] Problem ist nicht wirklich ein Problem. Die const-Variante bietet Schutz, und die nicht-const-Variante hat immer die Möglichkeit, die CoW zu diesem Zeitpunkt auszuführen (oder wirklich verrückt zu sein und einen Seitenfehler einzurichten, um ihn auszulösen).
Christopher Smith
+1 Geht zu den Themen.
Prost und hth. - Alf
5
Es ist nur albern, dass eine std :: cow_string-Klasse nicht enthalten war, mit lock_buffer () usw. Ich weiß oft, dass Threading kein Problem ist. eigentlich meistens.
Erik Aronesty
Ich mag den Vorschlag einer Alternative, ig Seile. Ich frage mich, ob es andere alternative Typen und Implementierungen gibt.
Voltaire
5

Ab 21.4.2 basic_string Konstruktoren und Zuweisungsoperatoren [string.cons]

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

[...]

2 Effekte : Konstruiert ein Klassenobjekt basic_stringwie in Tabelle 64 angegeben. [...]

Tabelle 64 dokumentiert hilfreich, dass nach der Erstellung eines Objekts über diesen (Kopier-) Konstruktor folgender this->data()Wert vorliegt:

zeigt auf das erste Element einer zugewiesenen Kopie des Arrays, auf dessen erstes Element str.data () zeigt

Es gibt ähnliche Anforderungen für andere ähnliche Konstruktoren.

Luc Danton
quelle
+1 Erklärt, wie C ++ 11 (zumindest teilweise) COW verbietet.
Prost und hth. - Alf
Entschuldigung, ich war müde. Es erklärt nichts weiter als, dass ein Aufruf von .data () das Kopieren von COW auslösen muss, wenn der Puffer derzeit gemeinsam genutzt wird. Trotzdem sind es nützliche Informationen, also lasse ich die Gegenstimme stehen.
Prost und hth. - Alf
1

Da jetzt garantiert ist, dass Zeichenfolgen zusammenhängend gespeichert werden und Sie jetzt einen Zeiger auf den internen Speicher einer Zeichenfolge nehmen dürfen (dh & str [0] funktioniert wie bei einem Array), ist es nicht möglich, eine nützliche COW zu erstellen Implementierung. Sie müssten eine Kopie für viel zu viele Dinge machen. Selbst wenn nur operator[]oder begin()eine nicht konstante Zeichenfolge verwendet wird, ist eine Kopie erforderlich.

Dirk Holsopple
quelle
1
Ich denke, dass Strings in C ++ 11 garantiert zusammenhängend gespeichert werden.
Mfontanini
4
In der Vergangenheit musste man die Kopien in all diesen Situationen machen und es war kein Problem ...
David Rodríguez - Dribeas
@mfontanini ja, aber sie waren vorher nicht
Dirk Holsopple
3
Obwohl C ++ 11 garantiert, dass Zeichenfolgen zusammenhängend sind, ist dies orthogonal zum Verbot von COW-Zeichenfolgen. Die COW-Zeichenfolge von GCC ist zusammenhängend. Ihre Behauptung, dass "eine nützliche COW-Implementierung nicht möglich ist", ist also eindeutig falsch.
Jonathan Wakely
1
@supercat, das Nach dem Backing Store fragt (z. B. durch Aufrufen c_str()), muss O (1) sein und darf nicht werfen und darf keine Datenrennen einführen. Daher ist es sehr schwierig, diese Anforderungen zu erfüllen, wenn Sie träge verketten. In der Praxis besteht die einzig sinnvolle Option darin, immer zusammenhängende Daten zu speichern.
Jonathan Wakely
1

Ist COW basic_stringin C ++ 11 und höher verboten?

Hinsichtlich

Bin ich richtig, dass C ++ 11 keine COW-basierten Implementierungen von zulässt std::string?

Ja.

Hinsichtlich

Wenn ja, wird diese Einschränkung ausdrücklich irgendwo in dem neuen Standard angegeben (wo)?

Fast direkt durch Anforderungen konstanter Komplexität für eine Reihe von Operationen, die ein O ( n ) physisches Kopieren der Zeichenfolgendaten in einer COW-Implementierungerfordern würden.

Zum Beispiel für die Mitgliedsfunktionen

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

… Was in einer COW-Implementierung ¹ sowohl das Kopieren von Zeichenfolgendaten auslösen würde, um die Freigabe des Zeichenfolgenwerts aufzuheben, erfordert der C ++ 11-Standard

C ++ 11 §21.4.5 / 4 :

Komplexität: konstante Zeit.

… Was ein solches Kopieren von Daten und damit COW ausschließt.

C ++ 03 unterstützt COW Implementierungen nicht diese ständigen Komplexitätsanforderungen haben, und durch unter bestimmten restriktiven Bedingungen, so dass Anrufe operator[](), at(), begin(), rbegin(), end(), oderrend() ungültig zu machen , Referenzen, Zeiger und Iteratoren auf die Zeichenfolge Posten beziehen, dh auf möglicherweise incur a Kopieren von COW-Daten. Diese Unterstützung wurde in C ++ 11 entfernt.


Ist COW auch über die C ++ 11-Ungültigkeitsregeln verboten?

In einer anderen Antwort, die zum Zeitpunkt des Schreibens als Lösung ausgewählt wurde und die stark positiv bewertet und daher anscheinend geglaubt wird, wird dies behauptet

Für eine COW-Zeichenfolge const operator[]würde das Aufrufen von non- das Erstellen einer Kopie (und das Ungültigmachen von Referenzen) erfordern, was im obigen [zitierten] Absatz [C ++ 11 §21.4.1 / 6] nicht zulässig ist. Daher ist es in C ++ 11 nicht mehr legal, eine COW-Zeichenfolge zu haben.

Diese Behauptung ist in zweierlei Hinsicht falsch und irreführend:

  • Es zeigt fälschlicherweise an, dass nur die Nicht- constItem-Accessoren eine COW-Datenkopie auslösen müssen.
    Aber auch die constElementzugriffsberechtigten müssen das Kopieren von Daten auslösen, da sie es dem Clientcode ermöglichen, Referenzen oder Zeiger zu bilden, die (in C ++ 11) später nicht über die Vorgänge ungültig gemacht werden dürfen, die das Kopieren von COW-Daten auslösen können.
  • Es wird fälschlicherweise davon ausgegangen, dass das Kopieren von COW-Daten zu einer Ungültigmachung der Referenz führen kann.
    Bei einer korrekten Implementierung erfolgt das Kopieren von COW-Daten, wobei die Freigabe des Zeichenfolgenwerts aufgehoben wird, zu einem Zeitpunkt, bevor Referenzen vorhanden sind, die ungültig gemacht werden können.

Um zu sehen, wie eine korrekte C ++ 11 COW-Implementierung von basic_stringfunktionieren würde, wenn die O (1) -Anforderungen, die dies ungültig machen, ignoriert werden, stellen Sie sich eine Implementierung vor, bei der eine Zeichenfolge zwischen Eigentumsrichtlinien wechseln kann. Eine Zeichenfolgeninstanz beginnt mit der Richtlinie Sharable. Wenn diese Richtlinie aktiv ist, können keine externen Elementreferenzen vorhanden sein. Die Instanz kann zu einer eindeutigen Richtlinie übergehen und muss dies tun, wenn möglicherweise eine Elementreferenz erstellt wird, z. B. bei einem Aufruf von.c_str() (zumindest, wenn dadurch ein Zeiger auf den internen Puffer erzeugt wird). Im allgemeinen Fall, dass mehrere Instanzen das Eigentum an dem Wert teilen, müssen die Zeichenfolgendaten kopiert werden. Nach diesem Übergang zur Richtlinie "Eindeutig" kann die Instanz nur durch einen Vorgang, der alle Verweise ungültig macht, z. B. die Zuweisung, wieder zu "Freigabefähig" zurückkehren.

Obwohl die Schlussfolgerung dieser Antwort, dass COW-Zeichenfolgen ausgeschlossen sind, richtig ist, ist die angebotene Argumentation falsch und stark irreführend.

Ich vermute, die Ursache für dieses Missverständnis ist ein nicht normativer Hinweis in Anhang C von C ++ 11:

C ++ 11 §C.2.11 [diff.cpp03.strings], ungefähr §21.3:

Änderung : basic_stringAnforderungen erlauben keine Zeichenfolgen mit Referenzzählung mehr.
Begründung: Die Invalidierung unterscheidet sich geringfügig mit Zeichenfolgen mit Referenzzählung. Diese Änderung reguliert das Verhalten für diesen internationalen Standard.
Auswirkung auf die ursprüngliche Funktion: Gültiger C ++ 2003-Code kann in dieser internationalen Norm anders ausgeführt werden

Hier erklärt die Begründung den Hauptgrund, warum man sich entschied, die spezielle COW-Unterstützung für C ++ 03 zu entfernen. Diese Begründung, das Warum , ist nicht, wie der Standard die COW-Implementierung effektiv verbietet. Der Standard verbietet COW über die O (1) -Anforderungen.

Kurz gesagt, die C ++ 11-Ungültigkeitsregeln schließen eine COW-Implementierung von nicht aus std::basic_string. Sie schließen jedoch eine einigermaßen effiziente, uneingeschränkte COW-Implementierung im C ++ 03-Stil aus, wie sie in mindestens einer der Standardbibliotheksimplementierungen von g ++ enthalten ist. Die spezielle COW-Unterstützung für C ++ 03 ermöglichte eine praktische Effizienz, insbesondere unter Verwendung von constElementzugriffsmethoden, auf Kosten subtiler, komplexer Regeln für die Ungültigmachung:

C ++ 03 §21.3 / 5 mit COW-Unterstützung für den ersten Anruf:

Verweise, Zeiger und Iteratoren, die sich auf die Elemente einer basic_stringSequenz beziehen, können durch die folgenden Verwendungen dieses basic_stringObjekts ungültig gemacht werden :
- Als Argument für Nichtmitgliedsfunktionen swap()(21.3.7.8), operator>>()(21.3.7.9) und getline()(21.3. 7.9).
- Als Argument für basic_string::swap().
- Anruf- data()und c_str()Mitgliedsfunktionen.
- Aufruf nicht constFunktionen Mitglied, außer operator[](), at(), begin(), rbegin(), end(), und rend().
- Im Anschluss an einen der oben genannten Verwendungen außer den Formen insert()und erase()das Iteratoren zurück, der erste Anruf nicht constMitgliederfunktionen operator[](), at(), begin(), rbegin(),end()oder rend().

Diese Regeln sind so komplex und subtil, dass ich bezweifle, dass viele Programmierer, wenn überhaupt, eine genaue Zusammenfassung geben könnten. Ich könnte nicht.


Was ist, wenn O (1) -Anforderungen nicht berücksichtigt werden?

Wenn die konstanten operator[]Zeitanforderungen für C ++ 11 für z. B. nicht berücksichtigt werden, ist COW for basic_stringmöglicherweise technisch machbar, aber schwierig zu implementieren.

Zu den Vorgängen, die auf den Inhalt einer Zeichenfolge zugreifen können, ohne dass COW-Daten kopiert werden müssen, gehören:

  • Verkettung über +.
  • Ausgabe über <<.
  • Verwenden eines basic_stringals Argument für Standardbibliotheksfunktionen.

Letzteres, weil die Standardbibliothek sich auf implementierungsspezifische Kenntnisse und Konstrukte stützen darf.

Zusätzlich könnte eine Implementierung verschiedene nicht standardmäßige Funktionen für den Zugriff auf Zeichenfolgeninhalte bieten, ohne das Kopieren von COW-Daten auszulösen.

Ein Hauptkomplikationsfaktor ist, dass in C ++ 11 der Elementzugriff das basic_stringKopieren von Daten auslösen muss (Aufheben der Freigabe der Zeichenfolgendaten), jedoch nicht ausgelöst werden muss , z. B. C ++ 11 §21.4.5 / 3 „ Throws: Nothing“. Daher kann keine normale dynamische Zuordnung verwendet werden, um einen neuen Puffer für das Kopieren von COW-Daten zu erstellen. Eine Möglichkeit, dies zu umgehen, besteht darin, einen speziellen Heap zu verwenden, in dem Speicher reserviert werden kann, ohne tatsächlich zugewiesen zu werden, und dann den erforderlichen Betrag für jede logische Referenz auf einen Zeichenfolgenwert zu reservieren . Das Reservieren und Aufheben der Reservierung in einem solchen Haufen kann eine konstante Zeit sein, O (1), und das Zuweisen des Betrags, den man bereits reserviert hat, kann seinnoexcept. Um die Anforderungen des Standards zu erfüllen, scheint es bei diesem Ansatz einen solchen speziellen reservierungsbasierten Heap pro eindeutigem Allokator zu geben.


Hinweise:
¹ Der constElementzugriffsauslöser löst eine COW-Datenkopie aus, da der Clientcode einen Verweis oder Zeiger auf die Daten erhalten kann, die durch eine spätere Datenkopie, die beispielsweise vom Nicht- constArtikelzugriffsgeber ausgelöst wird, nicht ungültig werden dürfen .

Prost und hth. - Alf
quelle
3
" Ihr Beispiel ist ein gutes Beispiel für eine für C ++ 11 falsche Implementierung. Möglicherweise war es für C ++ 03 korrekt." Ja , darum geht es im Beispiel . Es zeigt eine COW-Zeichenfolge, die in C ++ 03 legal war, weil sie die alten Iterator-Ungültigkeitsregeln nicht verletzt, und in C ++ 11 nicht legal ist, weil sie die neuen Iterator-Invalidierungsregeln verletzt. Und es widerspricht auch der Aussage, die ich im obigen Kommentar zitiert habe.
Jonathan Wakely
2
Wenn Sie gesagt hätten, dass Sharable ursprünglich nicht geteilt wurde, hätte ich nicht argumentiert. Zu sagen, dass etwas anfangs geteilt wird, ist nur verwirrend. Mit sich selbst geteilt? Das bedeutet das Wort nicht. Aber ich wiederhole: Ihr Versuch zu argumentieren, dass die C ++ 11-Iterator-Invalidierungsregeln keine hypothetische COW-Zeichenfolge verbieten, die in der Praxis nie verwendet wurde (und eine inakzeptable Leistung hätte), wenn sie mit Sicherheit die Art der COW-Zeichenfolge verbieten das wurde in der Praxis verwendet, ist etwas akademisch und sinnlos.
Jonathan Wakely
5
Ihre vorgeschlagene COW-Zeichenfolge ist interessant, aber ich bin mir nicht sicher, wie nützlich sie wäre. Der Zweck einer COW-Zeichenfolge besteht darin, die Zeichenfolgendaten nur für den Fall zu kopieren, dass in die beiden Zeichenfolgen geschrieben wird. Ihre vorgeschlagene Implementierung erfordert das Kopieren, wenn ein benutzerdefinierter Lesevorgang ausgeführt wird. Auch wenn der Compiler weiß, dass er nur gelesen wird, muss er dennoch kopieren. Darüber hinaus führt das Kopieren einer eindeutigen Zeichenfolge zu einer Kopie ihrer Zeichenfolgendaten (vermutlich in einen gemeinsam nutzbaren Zustand), was COW wiederum ziemlich sinnlos macht. Ohne die Komplexitätsgarantien könnten Sie also ... einen wirklich beschissenen COW-String schreiben .
Nicol Bolas
2
Während Sie technisch korrekt sind, dass die Komplexitätsgarantien Sie daran hindern, irgendeine Form von COW zu schreiben , ist es wirklich [basic.string] / 5, die Sie daran hindert, irgendeine wirklich nützliche Form von COW-String zu schreiben .
Nicol Bolas
4
@ JonathanWakely: (1) Ihr Zitat ist nicht die Frage. Hier ist die Frage: „Stimmt es, dass C ++ 11 keine COW-basierten Implementierungen von std :: string zulässt? Wenn ja, wird diese Einschränkung ausdrücklich irgendwo in der neuen Norm angegeben (wo)? “ (2) Ihre Meinung, dass eine Kuh std::stringunter Missachtung der O (1) -Anforderungen ineffizient wäre, ist Ihre Meinung. Ich weiß nicht, wie die Aufführung aussehen könnte, aber ich denke, dass diese Behauptung mehr für das Gefühl, für die Stimmung, die sie vermittelt, als für irgendeine Relevanz für diese Antwort vorgebracht wird.
Prost und hth. - Alf
0

Ich habe mich immer über unveränderliche Kühe gewundert: Sobald eine Kuh geschaffen wurde, konnte ich nur durch Zuweisung von einer anderen Kuh geändert werden, daher wird sie dem Standard entsprechen.

Ich hatte heute Zeit, es für einen einfachen Vergleichstest zu versuchen: eine Karte der Größe N, die mit einer Zeichenfolge / Kuh verschlüsselt ist, wobei jeder Knoten eine Reihe aller Zeichenfolgen in der Karte enthält (wir haben eine NxN-Anzahl von Objekten).

Mit Strings mit einer Größe von ~ 300 Bytes und N = 2000 Kühen sind die Kühe etwas schneller und verbrauchen fast eine Größenordnung weniger Speicher. Siehe unten, Größen sind in kbs angegeben, Lauf b ist mit Kühen.

~/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
quelle