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

Pre-allocate space for C++ STL queue(为 C++ STL 队列预分配空间)

问题描述

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

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

推荐答案

这可能不是问题.Deque 无论如何都会以块的形式分配，因此您可能只会重新分配几次.您确定这是一个瓶颈吗?

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.

如果您真的很担心，请使用池分配.这意味着预先分配内存，所以当容器请求内存时，它已经在那里了.我无法真正了解分配器和亲属，这对于 SO 答案来说太过分了，但请查看 Google 上的分配器.

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.

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

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 提供了一个 池分配器，它会是这样的:

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

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

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

我使用 list 而不是 deque 因为它更简单.通常，deque 优于 list，但使用分配器，赋予 deque 优势的东西，如缓存性能和分配成本，不再存在.因此，list 使用起来要简单得多.

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

这篇关于为 C++ STL 队列预分配空间的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持编程学习网！