Suche nach C ++ STL-wie Vektor-Klasse, aber mit Stapelspeicher

stimmen
44

Bevor ich meine eigene schreiben werde ich alle y'all fragen.

Ich suche nach einer C ++ Klasse, die wie ein STL-Vektor ist fast genau sondern speichert die Daten in ein Array auf dem Stapel. Irgendeine Art von STL Allocator Klasse würde auch, aber ich versuche, jede Art von Haufen zu vermeiden, auch statisch zugewiesen pro Thread Haufen (obwohl einer von denen, meine zweite Wahl ist). Der Stapel ist nur effizienter.

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

Für das, was ich war über mich selbst zu schreiben, war ich von so etwas wie diese zu 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

Chromium stack_container.h Mit funktioniert super!

Der Grund, warum ich nicht gedacht hatte, es so zu tun, mich ist, dass ich immer die allocator Objektparameter an die STL Sammlung Konstrukteurs übersehen haben. Ich habe die Template-Parameter ein paar Mal verwendet, um statische Pools zu tun, aber ich würde nie eine, die tatsächlich gesehen verwendet, um den Objektparameter Code oder geschrieben. Ich lernte etwas Neues. Sehr cool!

Der Code ist ein bisschen chaotisch und aus irgendeinem Grunde GCC hat mich gezwungen, das allocator als eigentliches Element zu erklären, anstatt sie in dem Vektor des allocator 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 zu:

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 genauso wie ich wollte.

Ich bemerkte, dass stack_container.h eine StackVector hat definiert und ich versuchte, es zu benutzen. Aber es erbt nicht von Vektor oder die gleichen Methoden definieren, so dass es Ersatz nicht ein Drop-in war. Ich wollte nicht den ganzen Code unter Verwendung des Vektors neu zu schreiben, damit ich auf sie aufgab.

Veröffentlicht am 09/12/2008 um 23:15
quelle vom benutzer
In anderen Sprachen...                            


10 antworten

stimmen
38

Sie müssen nicht eine völlig neue Container - Klasse schreiben. Sie können mit Ihren STL - Container stecken, aber der zweite Parameter von ändern zum Beispiel std::vectores Ihre benutzerdefinierten allocator zu geben , die aus einem Stapel-Puffer zuordnet. Die Chrom Autoren schrieben einen allocator nur für diese:

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 legen den Behälter und Anruf container.reserve(buffer_size);. Wenn Sie diese Größe überlaufen, wird der allocator automatisch Elemente aus dem Heap bekommen (da es abgeleitet ist std::allocator, wird es in diesem Fall nur die Einrichtungen des Standard allocator verwenden). Ich habe es nicht ausprobiert, aber es sieht aus wie es von Google ist , so dass ich denke , es ist ein Versuch wert.

Die Nutzung ist wie folgt aus:

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;
Beantwortet am 09/12/2008 um 23:27
quelle vom benutzer

stimmen
15

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 Adam Wulkiewicz und High-Performance-VARRAY Klasse Andrew Hundt.

Die Anzahl der Elemente in einem static_vector variieren kann dynamisch bis zu einem festgelegten Kapazitäts weil Elementen innerhalb des Objekts selbst ähnlich wie in einem Array gespeichert werden.

Beantwortet am 16/01/2014 um 14:23
quelle vom benutzer

stimmen
11

Einige Optionen können Sie wollen, betrachten:

STLSoft von Matthew Wilson (Autor von Unvollkommen C ++) eine auto_buffer Template - Klasse , die einen Standard - Array auf dem Stapel legt , aber wenn es größer ist als der Stapel wächst Zuordnung wird den Speicher aus dem Heap greifen. Ich mag diese Klasse - wenn Sie wissen , dass Ihre Behältergrößen werden in der Regel durch eine eher niedrige Grenze begrenzt werden, dann erhalten Sie die Geschwindigkeit eines lokalen, Stapel zugeordnete Array. Doch für die Ecke Fälle , in denen Sie mehr Speicher benötigen, es funktioniert alles noch richtig.

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.

„The Lazy Programmer“ hat einen Beitrag für eine Implementierung eines Behälters, der verwendet alloca()für die Lagerung. 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 noch boost::arraydie keiner der dynamischen Sizing Verhalten der ersten zwei, sondern gibt Ihnen mehr von der vectorSchnittstelle als nur Zeiger als Iteratoren verwenden , die Sie mit einem in die Arrays erhalten (dh Sie erhalten. begin(), end(), size()Usw.):

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

Beantwortet am 10/12/2008 um 02:18
quelle vom benutzer

stimmen
4

Wenn die Geschwindigkeit ankommt, sehe ich 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 schieben, v [0] v [1], 2 pop, auf einer Plattform, mac ppc, gcc-4.2-O3 nur. (Ich habe keine Ahnung, ob Apple ihre stl optimiert haben.)

Akzeptieren Sie keine Timings Sie nicht selbst gefälscht haben. Und natürlich ist jedes Nutzungsmuster unterschiedlich. Dennoch Faktoren> 2 überrascht 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 );

}
Beantwortet am 29/07/2009 um 12:20
quelle vom benutzer

stimmen
4

Sie können Ihr eigenes Allocator für std :: vector verwenden und haben sie Stücke von Ihren Stack-basierten Speichern, ähnlich wie bei Ihrem Beispiel zuordnen. Die allocator Klasse ist der zweite Teil der Vorlage.

Edit: Ich habe nie versucht, diese, und in der Dokumentation suche weiter führt mich nicht zu glauben, können Sie Ihr eigenes allocator schreiben. Ich suche noch hinein.

Beantwortet am 09/12/2008 um 23:18
quelle vom benutzer

stimmen
3

tr1 :: Array entspricht zum Teil Ihrer Beschreibung. Es fehlt Dinge wie Push ___ zurück () usw., aber es könnte sich ein Blick auf als Ausgangspunkt wert sein. Wickeln Sie es und das Hinzufügen eines Index auf den „zurück“ unterstützen push_back () usw. sollte recht einfach sein.

Beantwortet am 09/12/2008 um 23:39
quelle vom benutzer

stimmen
2

Es kann der Fall sein , dass Sie Qt verwenden. Dann könnten Sie möchten gehen QVarLengthArray( docs ). Er sitzt im Grunde zwischen std::vectorund std::arraystatisch für eine gewisse Aufteilung und zurück zu Heapzuordnung ggf. fallen.

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

Beantwortet am 13/05/2014 um 21:00
quelle vom benutzer

stimmen
2

Warum wollen Sie es auf dem setzen Stapel besonders? Wenn Sie eine Implementierung von alloca () haben, könnten Sie eine Klasse allocator buld mit , dass anstelle von malloc (), aber Ihre Idee , eine statisch zugewiesene Array zu verwenden , ist noch besser: es auf den meisten Architekturen genauso schnell ist, und Sie nicht Risikostapelbeschädigung von Ihnen vermasseln.

Beantwortet am 09/12/2008 um 23:25
quelle vom benutzer

stimmen
1

Auftrieb haben diese. Seine genannt small_vector

small_vector ist ein Vektor artiger Behälter für den Fall optimiert, wenn es wenige Elemente enthält. Es enthält einige vorreservierten Elemente an Ort und Stelle, die sie die Verwendung von dynamischer Speicherzuweisung vermieden werden kann, wenn die tatsächliche Anzahl der Elemente unterhalb dieser vorreservierten Schwelle liegt. small_vector ist inspiriert von der LLVM SmallVector Behälter. Im Gegensatz zu static_vector, Kapazität des small_vector kann über die ursprüngliche vorreservierten Kapazität wachsen.

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

Beantwortet am 21/04/2016 um 08:50
quelle vom benutzer

stimmen
0

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

new_stack_vector(Type, name, size)

wo Typeist, die Art des Elements in dem Vektor nameist der Variablenname des Vektors, und sizedie maximale Anzahl der Elemente in dem Vektor zu erlauben.

sizekann variabel sein und muss nicht ein Kompilierung-Konstante 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: Nie sehr große Feldgrößen auf dem Stapel im Allgemeinen verwenden. Wie Sie nicht verwenden sollten int var[9999999], sollten Sie ebenfalls nicht verwenden new_stack_vector(int, vec, 9999999)! Verwenden Sie verantwortungsvoll .

Beantwortet am 07/03/2018 um 13:27
quelle vom benutzer

Cookies help us deliver our services. By using our services, you agree to our use of cookies. Learn more