Ich brauche ein "String Pool" -Objekt, in das ich wiederholt eine "Folge von Zeichen" einfügen kann (ich benutze diesen Ausdruck als "String", ohne ihn mit std :: string oder einem C-String zu verwechseln), erhalte einen Zeiger zu der Sequenz und garantiert werden, dass der Zeiger nicht ungültig wird, wenn / wenn der Pool wachsen muss. Die Verwendung eines einfachen std::string als Pool funktioniert nicht, da der String neu zugeordnet werden kann, wenn seine ursprüngliche Kapazität überschritten wird, wodurch alle vorherigen Zeiger ungültig werden.
Der Pool wird nicht ohne Grenzen wachsen - es gibt klar definierte Punkte, an denen ich eine clear() Methode nennen werde - aber ich möchte auch keine maximale Kapazität dafür reservieren. Es sollte wachsen können, ohne sich zu bewegen.
Eine Möglichkeit, die ich in Betracht ziehe, ist, jede neue Zeichenfolge in ein forward_list<string> einzufügen und begin()->c_str() zu erhalten. Ein anderer fügt in ein unordered_set<string> ein, aber ich habe Schwierigkeiten, herauszufinden, was passiert, wenn ein unordered_set wachsen muss. Die dritte Möglichkeit, die ich in Betracht ziehe (weniger enthusiastisch), ist das Rollen meiner eigenen Kette von 1K-Puffern, in die ich die Folge von Zeichen verkette. Das hat den Vorteil (denke ich), die höchste Leistung zu haben, was eine Voraussetzung für dieses Projekt ist.
Ich wäre daran interessiert zu hören, wie andere empfehlen würden, sich diesem Thema zu nähern.
UPDATE 1: bearbeitet, um meine Verwendung der Phrase "Folge von Zeichen" zu verdeutlichen, um dem allgemeinen Begriff einer "Zeichenfolge" zu entsprechen, ohne entweder std :: string oder null-terminiertes Zeichen zu implizieren Array.
Ich habe diesen Ansatz in der Vergangenheit benutzt:
%Vor%Offensichtlich, wenn Sie das Set löschen möchten / müssen, würden Sie es in einem größeren Umfang verfügbar machen.
Für noch mehr Effizienz bewegen / setzen Sie die Strings in das Set.
Aktualisieren Ich habe diesen Ansatz der Vollständigkeit halber hinzugefügt. Sehen Sie Live auf Coliru
%Vor%Ja, Sie müssen eine Pufferliste schreiben. Nein, mach nicht all die harte Arbeit selbst.
Die zugrunde liegende Datenstruktur sollte ein std::vector<std::string> sein. Mit einer (Vorwärts-) Liste kaufen Sie nicht viel. Wenn der Vektor in der Größe geändert wird, werden die Zeichenfolgen effizient verschoben. std::forward_list<std::string> . Selbst wenn die Größe der Liste geändert wird, bleiben die Zeichenfolgen selbst erhalten. Das Iterieren der Liste wird nur für .clear benötigt, sodass die Listenleistung nicht kritisch ist.
Die Wrapperklasse sollte die Hinzufügung neuer Zeichenfolgen abstrahieren. Eine neue Zeichenfolge sollte hinzugefügt werden, wenn die Kapazität der letzten Zeichenfolge nicht ausreicht, um die neue Zeichenfolge hinzuzufügen. Wenn Sie eine neue Zeichenfolge hinzufügen, muss reserve der gesamte Speicher sein, den ein Chunk benötigt - dies stellt sicher, dass die Kapazität groß genug ist, um spätere Neuzuweisungen zu verhindern.
Dieses Setup kann Speicherplatz verschwenden, wenn eine große neue Zuweisung die Verwendung eines neuen Chunks erzwingt, wodurch ein Teil eines älteren Chunks nicht verwendet wird. Sie könnten sich natürlich die verbleibende Größe in den letzten N Blöcken für einen kleinen Wert von N merken, so dass diese Blöcke möglicherweise noch im Cache sind. Aber es ist durchaus möglich, dass in deiner App N = 5 schon zu groß wäre.
Überarbeiten Sie Ihre Anforderungen:
clear der Sequenz Es scheint, dass std::list<char> perfekt in diese Liste von Anforderungen passt. Natürlich brauchen Sie vielleicht einen Wrapper um die Klasse, damit sie sich genauso verhält wie std::string , aber das hängt wirklich davon ab, wie Sie die Daten manipulieren.
Und hier ist, wie gut es den Anforderungen entspricht:
Um Elemente zu verschieben, können Sie die Funktionen push_back und emplace_back verwenden.
std::begin(container) oder die Memberfunktion begin ruft den Iterator auf das erste Element der Sequenz ab.
Das Hinzufügen, Entfernen und Verschieben der Elemente in der Liste oder über mehrere Listen macht die Iteratoren nicht ungültig. Ein Iterator wird nur dann ungültig gemacht, wenn das entsprechende Element gelöscht wird.
Um die Reihenfolge zu löschen, können Sie die Elementfunktion clear verwenden.
Die meiste Zeit ist es als doppelt verknüpfte Liste implementiert, daher ist keine Kapazität reserviert.
Seit std::list scheint Speicher ineffizient zu sein (obwohl der Standard weder die Größe noch seine Implementierung angibt), es ist richtig hinzuzufügen, dass Sie auch std::deque<char> mit fast die gleiche Schnittstelle wie oben. Der einzige Unterschied ist, dass std::deque möglicherweise ungenutzten Speicher reserviert.
Tags und Links string c++ c++-standard-library string-pool