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

Solution 1

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

Solution 2

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

Solution 3

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.

Solution 4

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

Solution 5

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

View more solutions

Comments

[GManNickG]

A list is worse than a deque for a queue, in general.

[Brandon Pelfrey]

Yeah the problem is that deque also doesn't let you explicitly reserve space without actually editing the contents. The performance issue is that I'll be pushing to the front and popping the back of the queue, but I want to reserve space for the queue since all of these pushes will cause a dynamic resize and kill my sort performance.

[Brandon Pelfrey]

Sounds promising. Will try it soon. Thanks!

[Ilia Hadzhiev]

I agree, I was going to suggest a simple object containing head/tail ptrs and a pool of free'd objects. You would then build and maintain a doubly linked list. Your method is simpler.

[moogs]

errr, a deque doesn't answer the question. a list does (and in fact is almost the same at the marked answer (ring buffer, wrapped around a std::vector).

[doug65536]

Define "chunks". I looked at the GCC implementation and deque allocates in 512 byte chunks. If you think that's bad, MSVC allocates in 16 byte chunks. deque implementations are horrible. If you could point out one that isn't, I would be grateful.