Suche nach C++ STL-like Vektor-Klasse, aber mit Stack-Speicher

Question

Bevor ich mein eigenes schreibe, werde ich euch alle fragen.

Ich bin auf der Suche nach einer C++ - Klasse, die fast genau wie ein STL-Vektor ist, aber Daten in einem Array auf dem Stapel speichert. Eine Art von STL-Zuweisungs-Klasse würde auch funktionieren, aber ich versuche, jede Art von Heap zu vermeiden, sogar statische zugewiesene Pro-Thread-Heaps (obwohl einer von diesen meine zweite Wahl ist). Der Stapel ist nur effizienter.

Es muss fast ein Ersatz für den aktuellen Code sein, der einen Vektor verwendet.

Für das, was ich wollte mich selbst schreiben war ich von so etwas wie dieses Denken:

char buffer[4096]; 
stack_vector<match_item> matches(buffer, sizeof(buffer)); 

Oder die Klasse könnte Pufferraum intern zugeordnet hat. Dann würde es wie folgt aussehen:

stack_vector<match_item, 256> matches; 

Ich dachte, es wäre std :: bad_alloc werfen, wenn es der Platz ausgeht, obwohl das nicht immer passieren.

aktualisieren

Mit stack_container.h Chromium funktioniert super!

Der Grund, warum ich nicht daran gedacht hatte, es auf diese Weise selbst zu machen, ist, dass ich den Zuweisungsobjektparameter für die STL-Sammlungskonstruktoren immer übersehen habe. Ich habe den Vorlagenparameter ein paar Mal benutzt, um statische Pools zu machen, aber ich habe nie Code gesehen oder geschrieben, der tatsächlich den Objektparameter benutzte. Ich habe etwas Neues gelernt. Sehr cool!

Der Code ist ein bisschen chaotisch und aus irgendeinem Grund zwingt GCC mich, den Allokator als ein tatsächliches Element zu deklarieren, anstatt es in Vektor-Allokator-Parameter zu konstruieren. Es ging von etwas wie folgt aus:

typedef std::pair< const char *, const char * > comp_list_item; 
typedef std::vector<comp_list_item> comp_list_type; 

comp_list_type match_list; 
match_list.reserve(32); 

Um dies:

static const size_t comp_list_alloc_size = 128; 
typedef std::pair< const char *, const char * > comp_list_item; 
typedef StackAllocator< comp_list_item, comp_list_alloc_size > comp_list_alloc_type; 
typedef std::vector< comp_list_item, comp_list_alloc_type > comp_list_type; 

comp_list_alloc_type::Source match_list_buffer; 
comp_list_alloc_type match_list_alloc(&match_list_buffer); 
comp_list_type match_list(match_list_alloc); 
match_list.reserve(comp_list_alloc_size); 

Und ich muss wiederholen, dass, wenn ich ein neues erklären. Aber es funktioniert so, wie ich es wollte.

Ich habe festgestellt, dass stack_container.h hat einen StackVector definiert und ich habe es versucht. Aber es erbt nicht vom Vektor oder definiert die gleichen Methoden, also war es kein Ersatz. Ich wollte nicht den ganzen Code mit dem Vektor umschreiben, also gab ich es auf.

Answer 1

Sie müssen keine komplett neue Containerklasse schreiben.Sie können bei Ihren STL-Containern bleiben, aber ändern Sie den zweiten Parameter von zum Beispiel std::vector, um es Ihren benutzerdefinierten Zuordner zu geben, der aus einem Stapelpuffer reserviert. Die Chrom Autoren schrieb einen allocator nur dafür:

https://chromium.googlesource.com/chromium/chromium/+/master/base/stack_container.h

Es funktioniert durch einen Puffer Zuteilung, wo Sie sagen, wie groß es ist. Sie erstellen den Container und rufen container.reserve(buffer_size); auf. Wenn Sie diese Größe überschreiten, erhält der Allokator automatisch Elemente aus dem Heap (da er von std::allocator abgeleitet ist, wird er in diesem Fall nur die Funktionen des Standard-Allokators verwenden). Ich habe es nicht ausprobiert, aber es sieht so aus, als wäre es von Google, also denke ich, dass es einen Versuch wert ist.

Verwendung ist wie folgt:

StackVector<int, 128> s; 
s->push_back(42); // overloaded operator-> 
s->push_back(43); 

// to get the real std::vector. 
StackVector<int, 128>::ContainerType & v = s.container(); 
std::cout << v[0] << " " << v[1] << std::endl; 

Answer 2

Sie können Ihren eigenen Zuordner für std :: vector verwenden und ihm Teile Ihres stapelbasierten Speichers zuweisen, ähnlich wie in Ihrem Beispiel. Die Zuweisungsklasse ist der zweite Teil der Vorlage.

Edit: Ich habe das nie ausprobiert, und wenn ich mir die Dokumentation anschaue, glaube ich, dass du deinen eigenen Allokator nicht schreiben kannst. Ich schaue immer noch darauf.

Answer 3

Warum möchten Sie es auf den Stapel besonders setzen? Wenn Sie eine Implementierung von alloca() haben, könnten Sie einen Klassenzuordner mithilfe von statt malloc() erstellen, aber Ihre Idee, ein statisch zugewiesenes Array zu verwenden, ist noch besser: Es ist auf den meisten Architekturen genauso schnell, und Sie nicht Risiko Stack Korruption von dir durcheinander.

Answer 4

tr1 :: array Ihre Beschreibung teilweise übereinstimmt. Es fehlen Dinge wie Push ___ back(), etc., aber es lohnt sich, einen Blick darauf zu werfen. Es zu wickeln und einen Index zu "back" hinzuzufügen, um push_back() usw. zu unterstützen, sollte ziemlich einfach sein.

Answer 5

Einige Optionen, die Sie wollen, betrachten können:

STLSoft von Matthew Wilson (Autor von Imperfect C++) hat eine auto_buffer Template-Klasse, die einen Standard-Array auf dem Stapel legt, aber wenn es größer ist als der Stapel Zuteilung wächst wird Nimm die Erinnerung vom Haufen. Ich mag diese Klasse - wenn Sie wissen, dass Ihre Containergrößen in der Regel von einem eher niedrigen Limit begrenzt werden, dann erhalten Sie die Geschwindigkeit eines lokalen, Stack zugeordneten Array. Für die Fälle, in denen Sie jedoch mehr Speicher benötigen, funktioniert alles noch immer einwandfrei.

http://www.stlsoft.org/doc-1.9/classstlsoft_1_1auto__buffer.html

Beachten Sie, dass die Umsetzung Ich selbst benutze nicht STLSoft ist, sondern eine Umsetzung, die stark von ihm entlehnt.

"Der Lazy Programmer" hat einen Beitrag für eine Implementierung eines Containers, der alloca() für den Speicher verwendet. Ich bin kein Fan von dieser Technik, aber ich werde Sie für sich selbst entscheiden lassen, ob es was Sie wollen:

http://tlzprgmr.wordpress.com/2008/04/02/c-how-to-create-variable-length-arrays-on-the-stack/

Dann gibt es boost::array, die keine der dynamischen Sizing Verhalten der ersten zwei, sondern gibt Ihnen mehr von der vector Schnittstelle als nur Zeiger als Iteratoren verwenden, die Sie mit einem in die Arrays erhalten (dh Sie erhalten begin(), end(), size() etc..):

http://www.boost.org/doc/libs/1_37_0/doc/html/boost/array.html

Answer 6

Wenn die Geschwindigkeit Angelegenheiten , ICH siehe Laufzeiten

• 4 ns int [10], feste Größe auf dem Stapel
• 40 ns <vector>
• 1300 ns <stlsoft/containers/pod_vector.hpp>

für einen dummen Test unten - nur 2 push, v [0] v [1], 2 pop, auf einer Plattform, nur Mac ppc, gcc-4.2 -O3. (Ich habe keine Ahnung, ob Apple ihren stl.)

Akzeptieren Sie keine Timings, die Sie nicht selbst gefälscht haben. Und natürlich ist jedes Nutzungsmuster anders. Dennoch überraschen Faktoren> 2 mich.

(Wenn mems, Speicherzugriffe, sind der dominierende Faktor in Runtimes, was sind alle zusätzlichen mems in den verschiedenen Implementierungen?)

#include <stlsoft/containers/pod_vector.hpp> 
#include <stdio.h> 
using namespace std; 

int main(int argc, char* argv[]) 
{ 
     // times for 2 push, v[0] v[1], 2 pop, mac g4 ppc gcc-4.2 -O3 -- 
    // Vecint10 v; // stack int[10]: 4 ns 
    vector<int> v; // 40 ns 
    // stlsoft::pod_vector<int> v; // 1300 ns 
    // stlsoft::pod_vector<int, std::allocator<int>, 64> v; 

    int n = (argv[1] ? atoi(argv[1]) : 10) * 1000000; 
    int sum = 0; 

    while(--n >= 0){ 
     v.push_back(n); 
     v.push_back(n); 
     sum += v[0] + v[1]; 
     v.pop_back(); 
     v.pop_back(); 
    } 
    printf("sum: %d\n", sum); 

} 

Answer 7

Es scheint, dass boost::static_vector ist das, was Sie suchen. Aus der Dokumentation:

static_vector ist eine Hybrid zwischen Vektor- und Array: wie Vektor, es ist eine Folge Behälter mit sequenziellen Speichern, die in Größe, zusammen mit der statischen Zuweisung, niedriger Overhead und fester Kapazität des Arrays verändern können. static_vector basiert auf der Hochleistungs-Varray-Klasse von Adam Wulkiewicz und Andrew Hundt.

Die Anzahl der Elemente in einem statischen_Vektor kann dynamisch bis zu einer festen Kapazität variieren, da Elemente ähnlich wie ein Array im Objekt selbst gespeichert werden.

Answer 8

Es kann der Fall sein, dass Sie Qt verwenden. Dann möchten Sie vielleicht QVarLengthArray (docs) gehen. Es befindet sich grundsätzlich zwischen std::vector und , statisch für einen bestimmten Betrag zuzuteilen und bei Bedarf auf Heap-Zuweisung zurückzufallen.

Ich würde die Boost-Version bevorzugen, wenn ich es verwenden würde.

Answer 9

Boost haben dies. Seine genannt small_vector

small_vector ist ein Vektor artigen Behälter für den Fall optimiert, wenn es wenige Elemente enthält. Es enthält einige vorab zugeordnete Elemente in-place, die es ermöglichen, die Verwendung der dynamischen Speicherzuweisung zu vermeiden, wenn die tatsächliche Anzahl der Elemente unter diesem vorbelegten Schwellenwert liegt. small_vector ist inspiriert von LLVMs SmallVector Container. Im Gegensatz zu static_vector kann die Kapazität von small_vector über die anfänglich vorbelegte Kapazität hinaus wachsen.

small_vector ist umwandelbar in small_vector_base, einen Typ, der von der vorab zugeordneten Elemente Zahl unabhängig ist, Client-Code ermöglicht, die auf diesem N Argumente templated wird nicht müssen. small_vector erbt alle Member-Funktionen des Vektors, so dass es alle Standard-Features wie Einlagerungs unterstützt, Stateful Verteilern, usw.

Answer 10

Wenn Sie auf dem Stapel zuweisen möchten, wollen aber nicht auf eine maximale Größe bei der Kompilierung vordefinieren -Zeit, können Sie StackVector verwenden, eine kleine Implementierung, die wie folgt verwendet werden kann:

new_stack_vector(Type, name, size) 

wo Type ist die Art von Element in dem Vektor, name ist der Variablenname des Vektors, und size ist die maximale Anzahl der Elemente zu al niedrig im Vektor.

size kann variabel sein und muss keine Kompilierzeitkonstante sein!: D

Beispiel:

new_stack_vector(int, vec, 100); //like vector<int> vec; vec.reserve(100); but on the stack :) 
vec.push_back(10); //added "10" as the first item in the vector 

... und das ist alles!

Haftungsausschluss: Verwenden Sie niemals sehr große Array-Größen auf dem Stack im Allgemeinen. Wie Sie nicht int var[9999999] verwenden sollten, sollten Sie auch nicht new_stack_vector(int, vec, 9999999) verwenden! Verwenden Sie verantwortungsbewusst.