为 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 都是以块的形式分配的，因此您可能只会重新分配几次。您确定这是瓶颈吗？

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

如果您真的担心，请进行池分配。这意味着预先分配内存，因此当容器请求内存时，它已经在那里了。我无法真正回顾分配器和亲属，这对于 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()。

我使用 list 而不是 deque 因为它更简单。通常，双端队列 优于 list，但有了分配器，赋予 deque 优势的东西（例如缓存性能和分配成本）不再存在。因此，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

您可以尝试使用 std::deque 代替......

Answer 3

如果您使用其中一种结构来组成支持“reserve”函数调用的队列，那么您应该会很好。如果此数据结构不能满足您的需求，您可能需要寻找另一种。

话虽如此，您确定这里存在性能问题吗？

雅各布

Answer 4

听起来您需要一个带有 Reserve() 方法的数据结构，以及来自两端的高效“推送”和“弹出”操作。包裹在 std::vector 周围的环形缓冲区怎么样？您可以在构造函数中保留（）所需的空间，然后在实现中维护“front”和“end”索引，以将公共接口中的“push”和“pop”操作转换为底层 std 上的 O(1) 操作：：向量。

Answer 5

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

我不知道不需要自定义分配器的解决方案。但是，如果您可以使用自定义分配器，则可以实现您想要的目标。

概念证明示例代码可在 https://github.com/vincetse/allocator 获取，我将抄袭如下：

typedef int data_type;
typedef lazy::memory::buffer_allocator<data_type> allocator_type;
typedef std::deque<data_type, allocator_type> deque_type;
typedef std::queue<data_type, deque_type> queue_type;

const size_t buffer_size = 32 * 1024;    
data_type buffer[buffer_size];
allocator_type allocator(buffer, sizeof(buffer));
deque_type d(allocator);
queue_type q(d);
q.push(1);
q.pop();

Answer 6

看看这是否有帮助：http://www.cs.sunysb。 edu/~skiena/392/programs/queue.c

Answer 7

不用队列，用列表代替怎么样？