Würde diese Optimierung bei der Implementierung von std :: string erlaubt sein?

StackOverflow https://stackoverflow.com/questions/4682603

Frage

Ich dachte gerade über die Implementierung von std::string::substr. Es gibt ein neues std::string Objekt, das ein bisschen verschwenderisch mir scheint. Warum nicht wieder ein Objekt, das den Inhalt der ursprünglichen Zeichenkette bezieht sich und kann implizit in einem std::string zugeordnet werden? Eine Art faul Auswertung des tatsächlichen Kopierens. Eine solche Klasse wie folgt aussehen könnte: 

template <class Ch, class Tr, class A>
class string_ref {
public:
    // not important yet, but *looks* like basic_string's for the most part

private:
    const basic_string<Ch, Tr, A> &s_;
    const size_type pos_;
    const size_type len_;    
};

Die öffentliche Schnittstelle dieser Klasse würden alle der Nur-Lese-Operationen eines echten std::string imitieren, so wäre die Nutzung nahtlos. std::string könnte dann einen neuen Konstruktor, der eine string_ref dauert so würde der Benutzer nie klüger sein. In dem Moment, Sie zu „speichern“ versuchen, das Ergebnis, eine Kopie am Ende zu schaffen, so dass keine wirklichen Probleme mit der Bezugnahme auf Daten zeigen und dann mit ihm hinter seinem Rücken geändert.

Die Idee, dass Code wie folgt sein: 

std::string s1 = "hello world";
std::string s2 = "world";
if(s1.substr(6) == s2) {
    std::cout << "match!" << std::endl;
}

hätte nicht mehr als 2 std::string insgesamt konstruierten Objekte. Dies scheint eine nützliche Optimierung für Code, dass eine Menge von String-Manipulationen durchführt. Natürlich gilt dies nicht, nur zu std::string, sondern auf jede Art, die eine Teilmenge seines Inhalts zurückkehren kann.

Soweit ich weiß, keine Implementierungen tun.

ich den Kern der Frage annehmen, lautet:

eine Klasse gegeben, die implizit in einem std::string umgewandelt werden können je nach Bedarf, wäre es für eine Bibliothek Schriftsteller zum Standard wird konform den Prototyp eines zurückzukehren Typ-Mitglieds zu ändern? Oder allgemeiner, tun die Bibliothek Autoren den Spielraum haben zurückzukehren „Proxy-Objekte“ anstelle von regulären Objekte in dieser Art von Fällen als Optimierungs?

Mein Bauch ist, dass dies nicht erlaubt ist, und dass die Prototypen müssen genau übereinstimmen. Vorausgesetzt, dass Sie allein auf Rückgabetyp nicht überlastet werden können, das würde keinen Raum läßt für Bibliothek Autoren der Vorteile dieser Art von Situationen zu nehmen. Wie ich schon sagte, ich denke, die Antwort ist nein, aber ich dachte, ich würde fragen: -).

War es hilfreich?

Lösung

Diese Idee ist copy-on-write , sondern den gesamten Puffer von COW'ing, halten Sie verfolgen, welche Teilmenge des Puffers die „echte“ string ist. (KUH, in seiner normalen Form war (ist?) In einigen Bibliothek Implementierungen verwendet.)

Damit Sie keine Proxy-Objekt oder eine Änderung der Schnittstelle überhaupt brauchen, weil diese Angaben vollständig intern gemacht werden können. Konzeptionell, müssen Sie den Überblick über vier Dinge halten: einen Quellenpuffer, einen Referenzzähler für den Puffer und den Beginn und das Ende der Zeichenfolge innerhalb dieses Puffers

.

Immer wenn eine Operation ändert der Puffer überhaupt, erstellt er seine eigene Kopie ( von dem Start- und End-Trennzeichen ), nimmt den alten Referenzzähler des Puffers nach der anderen, und setzt die Hinweis der neuen Pufferzählung einer. Der Rest der Referenzzählung Regeln sind die gleichen: Kopie und eine Erhöhung um Eins, einen String und Abnahme Zahl Zerstörung durch eine, Null erreichen und löschen, etc

.

substr macht gerade eine neue String-Instanz, mit der Ausnahme des Start- und End-Trennzeichen explizit angegeben.

Andere Tipps

Dies ist eine recht bekannte Optimierung, die relativ weit verbreitet ist, copy-on-write oder COW genannt. Die grundlegende Sache ist nicht einmal mit Teil zu tun, aber mit etwas so einfachen wie 

s1 = s2;

Nun, das Problem mit dieser Optimierung ist, dass für C ++ Bibliotheken, die auf Ziele verwendet werden sollen mehrere Threads unterstützt, der Referenzzähler für die Zeichenfolge atomare Operationen werden muss zugegriffen (oder noch schlimmer, geschützt mit einem Mutex bei die Zielplattform liefert keine atomare Operationen). Das ist teuer genug, dass in den meisten Fällen die einfache Nicht-KUH-String-Implementierung ist schneller.

Siehe GOTW # 43-45:

http://www.gotw.ca/gotw/043.htm

http://www.gotw.ca/gotw/044.htm

http://www.gotw.ca/gotw/045.htm

Erschwerend kommt hinzu, Bibliotheken, die gebrauchte COW haben, wie das GNU C ++ Bibliothek, kann nicht einfach zurück wechselt die einfache Implementierung, da das würde das ABI brechen. (Obwohl, C ++ 0x zur Rettung, wie das wird ein ABI stößt ohnehin erforderlich! :))

Da substr kehrt std::string, gibt es keine Möglichkeit, ein Proxy-Objekt zurück, und sie können nicht nur die Rückkehr ändern Typ oder Überlastung es (aus den Gründen, die Sie erwähnt).

Sie könnten dies tun, indem string macht sich der Lage, eine Unter einer anderen Zeichenfolge zu sein. Dies würde eine Speicher Strafe für alle Nutzungen bedeutet (eine zusätzliche Zeichenkette und zwei size_types zu halten). Außerdem würde jede Operation überprüfen müssen, ob sie die Zeichen hat oder ist ein Proxy. Vielleicht ist dies mit einem Implementierung Zeiger getan werden könnte -. Das Problem ist, jetzt sind wir eine Allzweck-Klasse langsamer für einen möglichen Rand Fall machen

Wenn Sie diese benötigen, ist der beste Weg ist, eine andere Klasse, substring zu schaffen, dass die Konstrukte aus einem String, pos, und die Länge und Obdach zu bespannen. Sie können es nicht als s1.substr(6) verwenden, aber Sie können tun 

 substring sub(s1, 6);

Sie würden auch brauchen, um gemeinsame Operationen zu erstellen, die eine Teil und Zeichenfolge, um die Konvertierung zu vermeiden (da dies der springende Punkt ist).

In Bezug auf Ihre speziellen Beispiel, das ist für mich gearbeitet: 

if (&s1[6] == s2) {
    std::cout << "match!" << std::endl;
}

Das kann Ihre Frage nicht für eine Allzwecklösung beantworten. Dafür würden Sie Sub-string CoW benötigen, wie @GMan vermuten lässt.

Was Sie sprechen, ist über (oder war) eine des Kerns von Java java.lang.String Klasse verfügt ( http://fishbowl.pastiche.org/2005/04/27/the_string_memory_gotcha/ ). In vielerlei Hinsicht werden die Entwürfe von Java String Klasse und C ++ 's basic_string Vorlage ähnlich sind, so könnte ich mir vorstellen, dass eine Implementierung der basic_string Schablone schreiben Verwendung dieser ‚Teiloptimierung‘ ist möglich.

Eine Sache, die Sie beachten müssen, ist, wie die Umsetzung des c_str() const Mitglieds zu schreiben. Je nach Standort eines Strings als Teil eines anderen, kann es eine neue Kopie erstellen. Es wäre auf jeden Fall eine neue Kopie der internen Array zu erstellen, wenn die Zeichenfolge, für die die c_str angefordert wurde keinen Hinterstring ist. Ich denke, dass dies erfordert auf den meisten das mutable Schlüsselwort, wenn nicht alle der Datenelemente der basic_string Implementierung erheblich die Umsetzung anderer const Verfahren verkompliziert, da der Compiler nicht mehr in der Lage ist, den Programmierer mit const Korrektheit zu unterstützen.

EDIT: Eigentlich aufzunehmen c_str() const und data() const, Sie ein einzelnes wandelbar Feld vom Typ const charT* nutzen könnten. Zunächst auf NULL gesetzt, könnte es pro Instanz sein, initialisiert auf einen Zeiger auf ein neues charT Array, wenn c_str() const oder data() const genannt werden, und in der basic_string destructor, wenn nicht-NULL gelöscht.

Wenn und nur, wenn Sie wirklich mehr Leistung als std :: string müssen dann weiter und schreiben etwas bietet gehen, die die Art und Weise funktioniert, wie Sie es brauchen. Ich habe mit Varianten von Streichern gearbeitet, bevor.

Meine eigene Präferenz ist nicht wandelbar Strings zu verwenden, anstatt copy-on-write, und Verwendung boost :: shared_ptr oder gleichwertig, aber nur dann, wenn die Zeichenfolge tatsächlich über 16 in der Länge, so auch die String-Klasse ein eigenes hat Puffer für kurze Strings.

Das bedeutet, dass die String-Klasse könnte ein wenig Gewicht tragen.

Ich habe auch in meiner Sammlung Liste eine „Scheibe“ Klasse, die auf einem „Teilmenge“ eine Klasse aussehen kann, die anderswo so lange, wie die Lebensdauer des ursprünglichen Objekts lebt intakt ist. Also in Ihrem Fall könnte ich die Zeichenfolge in Scheiben schneidet einen Teil zu sehen. Natürlich wäre es nicht null-terminiert sein, noch gibt es eine Möglichkeit, es so zu machen, ohne sie zu kopieren. Und es ist kein String-Klasse.

Lizenziert unter: CC-BY-SA mit Zuschreibung
Nicht verbunden mit StackOverflow
scroll top