Pre-allocate space for C++ STL queue

Question

I'm writing a radix sort algorithm using queues and I would like to have a STL queue allocate space before I start adding things to the queue so that I can avoid constant dynamic resizing operations.

Even though this doesn't exist, I want something with the effect of...

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

in such a way that it will not dynamically allocate any memory during the loop.

The actual code in 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

This is a very old question, but I didn’t see an answer to OPs question: How can I use specifically std::queue with a pre-allocated buffer. So here goes:

I’m not aware of a solution that doesn’t require a custom allocator. However if you can use a custom allocator, you can achieve what you’re looking for.

Proof of concept example code is available at https://github.com/vincetse/allocator which I will plagiarize below:

typedef int data_type;
typedef lazy::memory::buffer_allocator<data_type> allocator_type;
typedef std::deque<data_type, allocator_type> deque_type;
typedef std::queue<data_type, deque_type> queue_type;

const size_t buffer_size = 32 * 1024;    
data_type buffer[buffer_size];
allocator_type allocator(buffer, sizeof(buffer));
deque_type d(allocator);
queue_type q(d);
q.push(1);
q.pop();