Pre-allocare spazio per coda C++ STL

Question

Sto scrivendo un algoritmo di ordinamento radix utilizzando le code e vorrei che una coda STL allocasse spazio prima di iniziare ad aggiungere elementi alla coda in modo da evitare operazioni di ridimensionamento dinamico costante.

Anche se questo non esiste, voglio qualcosa con l'effetto di ...

queue<int> qs(N); 
for(int i=0;i<N;++i) 
    qs.push(rand()); 

in modo tale che non allocare dinamicamente la memoria durante il ciclo.

Il codice effettivo in questione ...

void radix_sort() 
{ 
// Biggest number? 
int max=-1; 
for(int i=0;i<N;++i) 
    if(a[i]>max) 
     max = a[i]; 

// How many digits in it 
int maxdigits=1; 
while(max /= 10) maxdigits++; 

// Create some buckets. 
deque<int> b[10]; 
for(int i=0;i<10;++i) 
    b[i] = deque<int>(N); 

int div=1; 
// Radix Sort by digits 
for(int d=1;d<=maxdigits;++d) 
{ 
    if(d>1) 
     div*=10; 

    // Queue 
    for(int i=0;i<N;++i) 
     b[ (a[i]/div) % 10 ].push_front(a[i]); 

    // Dequeue 
    int k=0;  
    for(int q=0;q<10;++q) 
     while(b[q].size() > 0) 
     { 
      a[k++] = b[q].back(); 
      b[q].pop_back(); 
     } 
} 
} 

Answer 1

Le probabilità sono che questo non sia un problema. L'allocazione di Deque avviene comunque in blocchi, quindi sarà possibile riallocarne solo poche volte. Hai determinato che questo è un collo di bottiglia?

Ad ogni modo, lo standard non fornisce un accessor al contenitore `queue ', perché ciò vanificherebbe lo scopo dell'incapsulamento.

Se sei davvero preoccupato, il pool si alloca. Ciò significa preallocare la memoria in anticipo, quindi quando il contenitore richiede memoria, è già lì. Non riesco a superare gli allocatori e parenti, sarebbe eccessivo per una risposta SO, ma cercare allocators on Google.

Fondamentalmente, puoi dire al tuo contenitore da dove ottenere la memoria. Normalmente, questo è l'allocatore predefinito, che usa new e delete.

Boost fornisce un pool allocator, e sarebbe più o meno così:

#include <list> 
#include <queue> 

// pool 
#include <boost/pool/pool_alloc.hpp> 

// helpful typedef's 
typedef boost::fast_pool_allocator<int> BoostIntAllocator; 
typedef boost::singleton_pool<boost::fast_pool_allocator_tag, sizeof(int)> BoostIntAllocatorPool; 

int main(void) 
{ 
    // specify the list as the underlying container, and inside of that, 
    // specify fast_pool_allocator as the allocator. by default, it preallocates 
    // 32 elements. 
    std::queue<int, std::list<int, BoostIntAllocator > > q; 

    /* No memory allocations take place below this comment */ 

    for (int i = 0; i < 31; ++i) 
    { 
     q.push(i); 
    } 

    /* End no allocation */ 

    // normally, the memory used by the singleton will 
    // not be free'd until after the program is complete, 
    // but we can purge the memory manually, if desired: 
    BoostIntAllocatorPool::purge_memory(); 
}; 

La piscina alloca la memoria up-front, quindi non allocazione di memoria effettiva è fatto durante push()/pop().

Ho utilizzato uno list anziché uno deque perché è più semplice. Normalmente, un deque is superior to a list, ma con un allocatore, le cose che davano il vantaggio di deque, come il rendimento della cache e il costo di allocazione, non esistono più.Pertanto, un list è molto più semplice da usare.

È inoltre possibile utilizzare un circular buffer, come ad esempio:

#include <queue> 

// ring 
#include <boost/circular_buffer.hpp> 

int main(void) 
{ 
    // use a circular buffer as the container. no allocations take place, 
    // but be sure not to overflow it. this will allocate room for 32 elements. 
    std::queue<int, boost::circular_buffer<int> > q(boost::circular_buffer<int>(32)); 

    /* No memory allocations take place below this comment */ 

    for (int i = 0; i < 31; ++i) 
    { 
     q.push(i); 
    } 

    /* End no allocation */ 
}; 

Answer 2

Se si utilizza una delle strutture per comporre la coda che supporta la funzione di "riserva" Chiamata si dovrebbe essere buono. Se questa struttura dati non supporta le tue esigenze, potresti volerne cercare un'altra.

Detto questo, sei sicuro che ci sia un problema di prestazioni qui?

Jacob

Answer 3

Si potrebbe provare a utilizzare uno std :: deque invece ...

Answer 4

Invece di una coda, che ne dite di usare una lista, invece?

Answer 5

vedere se questo aiuta: http://www.cs.sunysb.edu/~skiena/392/programs/queue.c

Answer 6

Sembra che tu abbia bisogno di una struttura di dati con un metodo di riserva(), e "push" efficiente e le operazioni "pop" da estremità opposte. Che ne dici di un buffer ad anello, avvolto attorno a un vettore std ::? È possibile riservare() lo spazio necessario nel costruttore, quindi mantenere indici "frontali" e "finali" nell'implementazione per tradurre operazioni "push" e "pop" nell'interfaccia pubblica in operazioni O (1) sullo std sottostante ::vettore.