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

If you use one of the structures to compose your queue that supports the "reserve" function call you should be good. If this data structure does not support your needs, you might want to look for another one.

That being said, are you sure there is a performance problem here?

Jacob

Answer 2

You could try using a std::deque instead...

Answer 3

instead of a queue, how about use a list instead?

Answer 4

see if this helps: http://www.cs.sunysb.edu/~skiena/392/programs/queue.c

Answer 5

It sounds like you need a data structure with a reserve() method, and efficient "push" and "pop" operations from opposite ends. How about a ring buffer, wrapped around a std::vector ? You could reserve() the space you need in the constructor, then maintain "front" and "end" indices in your implementation to translate "push" and "pop" operations in the public interface to O(1) operations on the underlying std::vector.

Answer 6

Chances are this is not a problem. Deque's allocate in chunks anyway, so you'll probably only reallocate a few times. Have you determined this to be a bottleneck?

Anyway, the standard does not give an accessor to the `queue''s container, because that would defeat the purpose of encapsulation.

If you're really worried, pool allocate. This means preallocate the memory upfront, so when the container asks for memory, it's already there. I can't really go over allocators and kin, that would be overkill for an SO answer, but look up allocators on Google.

Basically, you can tell your container where to get it's memory from. Normally, this is the default allocator, which uses new and delete.

Boost provides a pool allocator, and it would go something like this:

#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();
};

The pool allocates the memory up-front, so no actual memory allocation is done during push()/pop().

I used a list instead of a deque because it is simpler. Normally, a deque is superior to a list, but with an allocator, the things that gave the deque it's advantage, like cache-performance and allocation cost, no longer exist. Therefore, a list is much simpler to use.

You can also use a circular buffer, like such:

#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 */
};