c++ - 为 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 无论如何都会以 block 的形式分配，因此您可能只会重新分配几次。您确定这是一个瓶颈吗？

无论如何，标准并没有为“队列”的容器提供访问器，因为这会破坏封装的目的。

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

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

Boost提供pool allocator ，它会是这样的:

#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() 期间不会进行实际的内存分配。

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

您也可以使用 circular buffer ，比如:

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