Предварительно выделите пространство для очереди STL C++
Еще один...
кэш Perl:
my $processed_input = $records || process_inputs($records_file);
На Открытом исходном коде Elpeleg, Perl CMS http://www.web-app.net/
6 ответов
Скорее всего, это не проблема. 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();
};
Пул распределяет память вверх- front, поэтому фактическое выделение памяти не выполняется во время push () / pop () .
Я использовал список вместо двухсторонней очереди потому что так проще. Как обычно, двухсторонняя очередь превосходит список , но с распределителем вещи, которые давали двухсторонней очереди ее преимущества, такие как производительность кеша и стоимость выделения, больше не существовать. Следовательно, список намного проще использовать.
Вы также можете использовать кольцевой буфер , например:
#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 */
};
Вместо этого вы можете попробовать использовать std :: deque ...
Похоже, вам нужна структура данных с методом reserve () и эффективные операции «push» и «pop» с противоположных сторон. Как насчет кольцевого буфера, обернутого вокруг std :: vector? Вы можете зарезервировать () пространство, которое вам нужно в конструкторе, а затем поддерживать индексы "front" и "end" в своей реализации для преобразования операций "push" и "pop" в общедоступном интерфейсе в операции O (1) на базовом std :: вектор.
Если вы используете одну из структур для создания очереди, которая поддерживает вызов функции «резерв», все должно быть хорошо. Если эта структура данных не соответствует вашим потребностям, вы можете поискать другую.
При этом, вы уверены, что здесь проблема с производительностью?
Джейкоб
посмотрим, поможет ли это: http://www.cs.sunysb.edu/~skiena/392/programs/queue.c