Подтвердить что ты не робот

Предварительное выделение пространства для очереди STL STL

Я пишу алгоритм сортировки radix, используя очереди, и я хотел бы, чтобы очередь 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();
        }
}
}
4b9b3361

ОТВЕТЫ

Ответ 1

Скорее всего, это не проблема. Deque в любом случае выделять куски, поэтому вы, вероятно, перераспределите несколько раз. Вы определили это как узкое место?

Во всяком случае, стандарт не предоставляет аксессуар в контейнер "queue", потому что это победит цель инкапсуляции.

Если вы действительно волнуетесь, пул распределяет. Это означает предварительную выделение памяти, поэтому, когда контейнер запрашивает память, он уже существует. Я не могу по-настоящему разобраться с дистрибуторами и родственниками, это было бы излишним для ответа SO, но посмотрите распределители в Google.

В принципе, вы можете сообщить своему контейнеру, откуда его получить. Обычно это распределитель по умолчанию, который использует новые и удаляет.

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, потому что он проще. Обычно Deque превосходит list, но с распределителем вещи, которые дали преимущество Deque, такие как производительность кэша и распределение стоимость больше не существует. Поэтому a 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 */
};

Ответ 2

Вместо этого вы можете попробовать использовать std:: deque...

Ответ 3

Если вы используете одну из структур для составления своей очереди, которая поддерживает вызов функции "резерв", вы должны быть хорошими. Если эта структура данных не поддерживает ваши потребности, вы можете захотеть найти другую.

Как вы сказали, вы уверены, что здесь есть проблема с производительностью?

Jacob

Ответ 4

Похоже, вам нужна структура данных с помощью метода reserve(), а также эффективные операции "push" и "pop" с противоположных концов. Как насчет кольцевого буфера, обернутого вокруг std::vector? Вы можете зарезервировать() пространство, в котором вы нуждаетесь в конструкторе, а затем сохранить индексы "впереди" и "конец" в своей реализации, чтобы перевести операции "push" и "pop" в публичный интерфейс на операции O (1) в базовом std::vector.

Ответ 5

Вместо очереди, как насчет использования списка?