为C++ STL队列预分配空间

Question

我正在使用队列编写基数排序算法,我想在开始向队列添加内容之前让STL队列分配空间,这样我就可以避免持续的动态调整大小操作.

即使这不存在,我想要的东西具有...的效果

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

以这种方式,它不会在循环期间动态分配任何内存.

有问题的实际代码......

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

这可能不是问题.Deque无论如何都要分配,所以你可能只会重新分配几次.你确定这是一个瓶颈吗？

无论如何,标准没有提供`queue'容器的访问器,因为这会破坏封装的目的.

如果你真的很担心,游泳池分配.这意味着预先预先分配内存,所以当容器请求内存时,它已经存在.我不能真的超过分配器和亲属,这对于SO答案来说太过分了,但是在Google上查找分配器.

基本上,你可以告诉你的容器从哪里获取它的内存.通常,这是默认分配器,它使用new和delete.

Boost提供了一个池分配器,它会像这样:

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

池预先分配内存,因此在push()/ 期间不会进行实际的内存分配pop().

我用a list而不是a,deque因为它更简单.通常情况下,a deque优于alist,但是使用分配器,deque使其具有优势的东西(如缓存性能和分配成本)不再存在.因此,a list使用起来要简单得多.

您也可以使用循环缓冲区,如:

#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

这是一个非常古老的问题，但我没有\xe2\x80\x99t看到OPs问题的答案：How can I usespecial std::queue with a pre-alulated buffer。所以这里是：

\n

我\xe2\x80\x99m不知道不需要自定义分配器的解决方案。但是，如果您可以使用自定义分配器，则可以实现您\xe2\x80\x99 正在寻找的内容。

\n

概念证明示例代码可在https://github.com/vincetse/allocator上找到，我将在下面抄袭它：

\n

typedef int data_type;\ntypedef lazy::memory::buffer_allocator<data_type> allocator_type;\ntypedef std::deque<data_type, allocator_type> deque_type;\ntypedef std::queue<data_type, deque_type> queue_type;\n\nconst size_t buffer_size = 32 * 1024;    \ndata_type buffer[buffer_size];\nallocator_type allocator(buffer, sizeof(buffer));\ndeque_type d(allocator);\nqueue_type q(d);\nq.push(1);\nq.pop();\n

\n