Alla ricerca di classi vettoriali simili a C ++ in formato STL ma utilizzando l’archiviazione dello stack

Prima di scrivere il mio, chiederò a tutti voi.

Sto cercando una class C ++ che sia quasi esattamente come un vettore STL ma memorizzi i dati in una matrice sullo stack. Qualche tipo di class di allocatore STL funzionerebbe anche, ma sto cercando di evitare ogni tipo di heap, anche gli heap per-thread allocati staticamente (anche se uno di questi è la mia seconda scelta). Lo stack è solo più efficiente.

Deve essere quasi una goccia in sostituzione del codice corrente che utilizza un vettore.

Per quello che stavo per scrivere, stavo pensando a qualcosa del genere:

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

Oppure la class potrebbe avere spazio buffer allocato internamente. Quindi sembrerebbe:

 stack_vector matches; 

Pensavo che avrebbe lanciato std :: bad_alloc se si esaurisse lo spazio, anche se non dovrebbe mai accadere.

Aggiornare

L’utilizzo di stack_container.h di Chromium funziona alla grande!

Il motivo per cui non avevo pensato di farlo in questo modo è che ho sempre trascurato il parametro dell’object allocator per i costruttori di raccolte STL. Ho usato il parametro template alcune volte per fare pool statici ma non avevo mai visto codice o scritto alcuno che usasse effettivamente il parametro object. Ho imparato qualcosa di nuovo. Molto bello!

Il codice è un po ‘caotico e per qualche ragione GCC mi ha costretto a dichiarare l’allocatore come un object reale invece di costruirlo nel parametro allocatore di vettore. È passato da qualcosa del genere:

 typedef std::pair comp_list_item; typedef std::vector comp_list_type; comp_list_type match_list; match_list.reserve(32); 

A questa:

 static const size_t comp_list_alloc_size = 128; typedef std::pair comp_list_item; typedef StackAllocator comp_list_alloc_type; typedef std::vector 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 ); 

E devo ripeterlo ogni volta che ne dichiaro uno nuovo. Ma funziona proprio come volevo.

Ho notato che stack_container.h ha definito StackVector e ho provato ad usarlo. Ma non eredita dal vettore o definisce gli stessi metodi quindi non era una sostituzione drop-in. Non volevo riscrivere tutto il codice usando il vettore, quindi ho rinunciato a farlo.

Non è necessario scrivere una class contenitore completamente nuova. È ansible rimanere con i contenitori STL, ma modificare il secondo parametro di esempio std::vector per assegnargli l’allocatore personalizzato che assegna da uno stack-buffer. Gli autori di cromo hanno scritto un allocatore proprio per questo:

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

Funziona allocando un buffer dove dici quanto è grande. Si crea il contenitore e si chiama container.reserve(buffer_size); . Se si esegue il overflow di tale dimensione, l’allocatore otterrà automaticamente gli elementi dall’heap (poiché è derivato da std::allocator , in tal caso verrà utilizzato solo le funzionalità dello standard allocator). Non l’ho provato, ma sembra che provenga da Google, quindi penso che valga la pena provare.

L’utilizzo è come questo:

 StackVector s; s->push_back(42); // overloaded operator-> s->push_back(43); // to get the real std::vector. StackVector::ContainerType & v = s.container(); std::cout < < v[0] << " " << v[1] << std::endl; 

Sembra che boost :: static_vector sia quello che stai cercando. Dalla documentazione:

static_vector è un ibrido tra vettore e array: come vettore, è un contenitore di sequenza con storage contiguo che può cambiare in dimensione, insieme all’assegnazione statica, al sovraccarico e alla capacità fissa dell’array. static_vector è basato su Adam Wulkiewicz e sulla class varray ad alte prestazioni di Andrew Hundt.

Il numero di elementi in un static_vector può variare dynamicmente fino a una capacità fissa poiché gli elementi vengono memorizzati all’interno dell’object stesso in modo simile a un array.

Alcune opzioni che potresti voler vedere:

STLSoft di Matthew Wilson (autore di Imperfect C ++) ha una class template auto_buffer che mette una matrice predefinita nello stack, ma se diventa più grande dell’allocazione dello stack prenderà la memoria dall’heap. Mi piace questa class – se sai che le dimensioni del tuo contenitore saranno generalmente limitate da un limite piuttosto basso, otterrai la velocità di un array locale, assegnato allo stack. Tuttavia, per i casi d’angolo in cui hai bisogno di più memoria, tutto funziona ancora correttamente.

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

Si noti che l’implementazione che uso io non è STLSoft, ma un’implementazione che prende a prestito pesantemente da esso.

“The Lazy Programmer” ha realizzato un post per l’implementazione di un contenitore che utilizza alloca() per l’archiviazione. Non sono un fan di questa tecnica, ma ti permetterò di decidere da solo se è quello che vuoi:

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

Poi c’è boost::array che non ha il comportamento di dimensionamento dinamico dei primi due, ma fornisce più dell’interfaccia vector che solo usando i puntatori come iteratori che si ottengono con gli array incorporati (es., Si begin() , end() , size() , ecc.):

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

È ansible utilizzare il proprio allocatore per std :: vector e farlo allocare blocchi dello storage basato su stack, in modo simile al proprio esempio. La class allocatore è la seconda parte del modello.

Edit: Non ho mai provato questo, e guardando la documentazione mi porta a credere che non puoi scrivere il tuo allocatore. Ci sto ancora guardando.

Se la velocità conta, vedo i tempi di esecuzione

  • 4 ns int [10], dimensione fissa nello stack
  • 40 ns
  • 1300 ns

per uno stupido test qui sotto – solo 2 push, v [0] v [1], 2 pop, su una piattaforma, mac ppc, solo gcc-4.2 -O3. (Non ho idea se Apple abbia ottimizzato la loro stl.)

Non accettare orari che non hai falsificato te stesso. E ovviamente ogni schema di utilizzo è diverso. Ciò nonostante> 2 mi sorprendono.

(Se i mem, gli accessi alla memoria, sono il fattore dominante in runtime, quali sono tutti i mem extra nelle varie implementazioni?)

 #include  #include  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 v; // 40 ns // stlsoft::pod_vector v; // 1300 ns // stlsoft::pod_vector, 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 ); } 

tr1 :: array corrisponde parzialmente alla tua descrizione. Mancano cose come push ___ back (), ecc., Ma potrebbe valere la pena dare un’occhiata come punto di partenza. Racchiuderlo e aggiungere un indice al “dietro” per supportare push_back (), ecc. Dovrebbe essere abbastanza facile.

Perché vuoi metterlo in pila in particolare? Se hai un’implementazione di alloca (), potresti usare un allocatore di class usando quello invece di malloc (), ma la tua idea di usare un array assegnato staticamente è ancora meglio: è altrettanto veloce sulla maggior parte delle architetture, e non lo fai rischio di corruzione dello stack di voi incasinato.

Potrebbe essere il caso che stai usando Qt. Quindi potresti voler andare a QVarLengthArray ( docs ). Si trova fondamentalmente tra std::vector e std::array , allocando staticamente per un certo importo e ricadendo sull’allocazione dell’heap, se necessario.

Preferirei la versione boost se la usassi comunque.

Boost avere questo. Si chiama small_vector

small_vector è un contenitore di tipo vettoriale ottimizzato per il caso quando contiene pochi elementi. Contiene elementi preallocati sul posto, che consentono di evitare l’utilizzo dell’allocazione di memoria dynamic quando il numero effettivo di elementi è inferiore alla soglia preallata. small_vector è ispirato al contenitore SmallVector di LLVM. A differenza di static_vector, la capacità di small_vector può superare la capacità iniziale preallata.

small_vector è convertibile in small_vector_base, un tipo che è indipendente dal conteggio degli elementi preallocati, consentendo al codice client che non deve essere rappresentato da un modello su quell’argomento N. small_vector eredita tutte le funzioni membro di tutti i vettori in modo tale che supporti tutte le funzioni standard come emplacement, allocators stateful, ecc.

Se si desidera allocare nello stack ma non si desidera definire una dimensione massima in fase di compilazione, è ansible utilizzare StackVector , una piccola implementazione che può essere utilizzata in questo modo:

 new_stack_vector(Type, name, size) 

dove Type è il tipo di elemento nel vettore, name è il nome della variabile del vettore e size è il numero massimo di elementi da consentire nel vettore.

size può essere variabile e non deve necessariamente essere una costante in fase di compilazione! : D

Esempio:

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

…e questo è tutto!

Dichiarazione di non responsabilità: in generale non utilizzare mai array di dimensioni molto grandi. Come non dovresti usare int var[9999999] , non dovresti usare anche new_stack_vector(int, vec, 9999999) ! Usare responsabilmente