为C ++ STL队列预分配空间 [英] Pre-allocate space for C++ STL queue

问题描述

我正在使用队列编写一个基数排序算法，我希望有一个STL队列在开始向队列中添加内容之前分配空间，以便避免不断的动态调整大小操作。

即使这不存在，我想要一些效果...

  queue< int> qs（N）; 
 for（int i = 0; i  qs.push（rand（））; 
  

，这样在循环期间不会动态分配任何内存。

有问题的实际代码...

  void radix_sort（）
 {
 //最大数字？ 
 int max = -1; 
 for（int i = 0; i  if（a [i]> max）
 max = a [i] 
 
 //多少位数
 int maxdigits = 1; 
 while（max / = 10）maxdigits ++; 
 
 //创建一些存储桶。 
 deque< int> b [10]; 
 for（int i = 0; i <10; ++ i）
 b [i] = deque< int>（N） 
 
 int div = 1; 
 // radix按位数排序
 for（int d = 1; d <= maxdigits; ++ d）
 {
 if（d> 1）
 div * = 10; 
 
 // Queue 
 for（int i = 0; i b [（a [i] / div）％10] .push_front [一世]）; 
 
 // 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 以块为单位分配，因此您可能只会重新分配几次。你确定这是一个瓶颈吗？

无论如何，标准没有给一个访问者'queue'的容器，因为这将失去封装的目的。

如果你真的担心，pool alloc。这意味着预先分配内存，所以当容器请求内存时，它已经存在。我不能真正去分配器和亲，这将是overkill为一个SO的答案，但查找 Google上的分配器。

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

Boost 提供池分配器，它会像这样：

  #include< list> 
 #include< queue> 
 
 // pool 
 #include< boost / pool / pool_alloc.hpp> 
 
 //有帮助typedef's 
 typedef boost :: fast_pool_allocator< int> BoostIntAllocator; 
 typedef boost :: singleton_pool< boost :: fast_pool_allocator_tag，sizeof（int）> BoostIntAllocatorPool; 
 
 int main（void）
 {
 //将列表指定为底层容器，在其内部，
 //指定fast_pool_allocator作为分配器。默认情况下，它预分配
 // 32个元素。 
 std :: queue< int，std :: list< int，BoostIntAllocator> > q; 
 
 / *在此注释下没有内存分配* / 
 
 for（int i = 0; i <31; ++ i）
 {
 q.push（i）; 
} 
 
 / *结束不分配* / 
 
 //通常，单例的内存使用
 //不能释放直到程序完成后，
 //但我们可以手动清除内存，如果需要：
 BoostIntAllocatorPool :: purge_memory（）; 
}; 
  

池预先分配内存，因此在 push（） / pop（）。

c $ c> list 而不是 deque ，因为它更简单。通常， deque 优于列表 ，但使用分配器，给予 deque 它的优点，如缓存性能和分配成本，不再存在。因此，列表更容易使用。

您还可以使用圆形缓冲区，例如：

  #include< queue> 
 
 // ring 
 #include& lt; boost / circular_buffer.hpp> 
 
 int main（void）
 {
 //使用循环缓冲区作为容器。没有发生分配，
 //但一定不要溢出它。这将分配32个元素的空间。 
 std :: queue< int，boost :: circular_buffer< int> > q（boost :: circular_buffer< int>（32））; 
 
 / *在此注释下没有内存分配* / 
 
 for（int i = 0; i <31; ++ i）
 {
 q.push（i）; 
} 
 
 / *结束无分配* / 
}; 
  

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

解决方案

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

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