Pré-allouer de l'espace pour la file STL

Question

J'écris un algorithme de tri radix utilisant des files d'attente et j'aimerais qu'une file d'attente STL alloue de l'espace avant de commencer à ajouter des choses à la file d'attente.

Même si cela n'existe pas, je veux quelque chose avec l'effet de ...

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

de telle sorte qu'il ne sera pas allouer dynamiquement une mémoire pendant la boucle.

Le code réel en question ...

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

Les chances sont que ce n'est pas un problème. Deque Allouer en morceaux de toute façon, de sorte que vous aurez probablement réaffecter seulement quelques fois. Avez-vous déterminé que cela était un goulot d'étranglement? Quoi qu'il en soit, la norme ne donne pas d'accesseur au conteneur de la file d'attente, car cela annulerait le but de l'encapsulation.

Si vous êtes vraiment inquiet, allouer la piscine. Cela signifie préallouer la mémoire à l'avance, donc quand le conteneur demande de la mémoire, il est déjà là. Je ne peux pas vraiment passer en revue les allocateurs et les parents, ce serait exagéré pour une réponse SO, mais regardez allocators on Google. Fondamentalement, vous pouvez dire à votre conteneur d'où sa mémoire. Normalement, il s'agit de l'allocateur par défaut, qui utilise new et delete.

Boost fournit un pool allocator, et ce serait quelque chose comme ceci:

#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 piscine alloue la mémoire à l'avance, donc pas d'allocation de mémoire réelle est effectuée pendant push()/pop(). J'ai utilisé un list au lieu d'un deque parce que c'est plus simple. Normalement, un deque is superior to a list, mais avec un allocateur, les choses qui ont donné deque son avantage, comme les performances de cache et le coût d'allocation, n'existent plus.Par conséquent, un list est beaucoup plus simple à utiliser.

Vous pouvez également utiliser un circular buffer, comme par exemple:

#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

Si vous utilisez une des structures pour composer votre file d'attente qui prend en charge la fonction « de réserve » appel, vous devriez être bon. Si cette structure de données ne répond pas à vos besoins, vous pouvez en chercher une autre. Cela étant dit, êtes-vous sûr qu'il y a un problème de performance ici?

Jacob

Answer 3

Vous pouvez essayer d'utiliser un std :: deque à la place ...

Answer 4

Au lieu d'une file d'attente, que diriez-vous utiliser une liste à la place?

Answer 5

voir si cela aide: http://www.cs.sunysb.edu/~skiena/392/programs/queue.c

Answer 6

On dirait que vous avez besoin d'une structure de données avec une méthode de réserve() et efficace « push » et opérations « pop » des extrémités opposées. Que diriez-vous d'un tampon en anneau, enroulé autour d'un vecteur std ::? Vous pouvez réserver() l'espace dont vous avez besoin dans le constructeur, puis maintenir les index "front" et "end" dans votre implémentation pour traduire les opérations "push" et "pop" dans l'interface publique vers les opérations O (1) sur le std sous-jacent ::vecteur.