kleine String-Optimierung für Vektor?

Ich weiß, mehrere (alle?) STL-Implementierungen implementieren eine "kleine String" -Optimierung, wo statt der üblichen 3 Zeiger für Anfang, Ende und Kapazität eine Zeichenfolge speichert die tatsächlichen Zeichendaten in den Speicher für die Zeiger verwendet, wenn sizeof (Zeichen) < = sizeof (Zeiger). Ich bin in einer Situation, in der ich viele kleine Vektoren mit einer Elementgröße < = sizeof (Zeiger) habe. Ich kann keine Arrays fester Größe verwenden, da die Vektoren in der Lage sein müssen, die Größe dynamisch zu ändern und möglicherweise ziemlich groß werden können. Die mittlere (nicht die mittlere) Größe der Vektoren wird jedoch nur 4-12 Bytes betragen. Daher wäre eine "kleine String" -Optimierung, die an Vektoren angepasst ist, für mich sehr nützlich. Gibt es so etwas?kleine String-Optimierung für Vektor?

Ich denke darüber nach, meine eigenen zu rollen, indem ich einfach einen Brute-Force-Vektor in eine Zeichenkette umwandelt, d. H. Eine Vektorschnittstelle für eine Zeichenkette bereitstellt. Gute Idee?

Quelle

2010-02-01 BuschnicK

Ihre Frage ist nicht sehr klar. Was meinen Sie mit einer "Vektor" -Schnittstelle zu einer "Zeichenkette"? Sprechen Sie über eine spezielle "Svector" -Klasse, um kleine Saiten zu halten? – dirkgently

Nein. Ich meine eine Zeichenfolge mit willkürlichen Werten anstelle von char-Typen - genau wie ein Vektor. Eine Vektorschnittstelle zu einer Zeichenfolge bedeutet, dass das Zeichenfolgenobjekt umhüllt und eine vektorkompatible Schnittstelle verfügbar gemacht wird, indem die fehlenden Funktionen wie push_back hinzugefügt werden. – BuschnicK

Wäre es nicht eher möglich, etwas mit dem Allokator zu tun? Sie würden nicht einmal 3 Zeiger im Wert von Speicher bekommen, da der Vektor auch einen Weg braucht, um zu wissen, ob er im "kleinen" oder "großen" Modus ist. – UncleBens

Sie können die SmallVector Implementierung von LLVM ausleihen. (nur Header, befindet sich in LLVM \ include \ llvm \ ADT)

Quelle

2010-02-01 17:29:49

Es ist nicht mehr nur Header-Only. – rightfold

Header ist hier: https://github.com/llvm-mirror/llvm/blob/master/include/llvm/ADT/SmallVector.h – Nick

Es war discussed Jahren (und ein paar der Namen in diesem Thread kann ein wenig vertraut aussehen :-)), aber ich kenne keine vorhandene Implementierung. Ich glaube nicht, dass ich versuchen würde, std :: string an die Aufgabe anzupassen. Die genauen Anforderungen an den Typ, über den std :: basic_string nicht gut angegeben ist, aber der Standard ist ziemlich klar, dass es nur für etwas gedacht ist, das stark wie char funktioniert. Für Typen, die wesentlich anders sind, könnte es immer noch funktionieren, aber es ist schwer zu sagen, was passieren würde - es war nie für andere Typen als kleine Ganzzahlen gedacht und wurde wahrscheinlich auch nicht getestet.

Wenn Sie damit anfangen, wird die Implementierung std::vector von Grund auf neu (sogar mit einer kleinen Vektor-Optimierung) nicht sehr schwierig sein.

Quelle

2010-02-01 16:47:49

+11

Die Implementierung von 'std :: vector' * * von Grund auf neu ist überraschend schwierig. Wenn Sie die Ausnahmesicherheit ignorieren, wird es natürlich viel einfacher, aber dann ist es keine sinnvolle (oder nützliche) Vektorimplementierung mehr. – jalf

Danke für den Zeiger - leider ist die Diskussion nie wirklich zu einem Abschluss gekommen. Die Implementierung meines eigenen Vektors wäre nicht so schwierig, da stimme ich Ihnen zu. Ich hatte jedoch gehofft, dass ich nur eine fertige Klasse einstecken und den Effekt auf den Speicherverbrauch sehen könnte. Ich spiele derzeit mit verschiedenen Ideen zur Reduzierung unseres Speicherabdrucks, und das ist nur einer von ihnen. – BuschnicK

Wenn das gesagt wird, denke ich, eine benutzerdefinierte Vektorimplementierung wäre der beste Weg, dies zu erreichen. Das Umhüllen der vorhandenen Vektorklasse würde es schwierig machen, die Größe des Objekts effizient zu nutzen, und ein benutzerdefinierter Vektor ist keine Hexenware, solange Sie vorsichtig sind und wissen, was Sie tun. – jalf

Wenn T ein POD-Typ ist, warum nicht basic_string anstelle von Vektor?

Quelle

2010-03-14 18:21:11

Beachten Sie, dass Sie eine Spezialisierung "Std :: char_traits" schreiben müssten (oder eine äquivalente Merkmalsklasse) für den POD-Typ. Die Anforderungen sind nicht so streng, abgesehen von der Notwendigkeit, einen speziellen "eof" -Wert zu nominieren, aber ich erwarte, dass es etwas mühsam ist. –

Darüber hinaus gibt es keine Garantie, dass 'basic_string ' kleine String-Optimierung verwenden wird, und keine portable Möglichkeit zur Angabe, wie viele Elemente, auch wenn es tut. –

Boost 1.58 wurde gerade veröffentlicht und es ist Container Bibliothek hat eine small_vector Klasse basierend auf der LLVM SmallVector.

Es gibt auch eine static_vector, die nicht über die ursprünglich angegebene Größe hinaus wachsen kann. Beide Container sind Nur-Header.

facebooks folly Bibliothek hat auch einige tolle Container.

Es hat eine small_vector, die mit einem Template-Parameter wie Boost static oder small Vektoren konfiguriert werden kann. Es kann auch konfiguriert werden, um kleine Integer-Typen für die interne Größe Buchhaltung zu verwenden, die sie sind facebook ist keine Überraschung :)

Es ist Arbeit im Gange, um die Bibliothek Cross-Plattform so Windows/MSVC-Unterstützung sollte eines Tages landen ...

Quelle

2015-04-17 10:47:24 onqtam

kleine String-Optimierung für Vektor?

Antwort

Verwandte Themen