为 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 */
};
相关文章