prioridad - Asignación previa de espacio para la cola C++ STL

queue c++ example

Question

Estoy escribiendo un algoritmo de ordenamiento de radix utilizando colas y me gustaría tener una cola de STL que asigne espacio antes de comenzar a agregar cosas a la cola para poder evitar operaciones constantes de cambio de tamaño dinámico.

Aunque esto no existe, quiero algo con el efecto de ...

queue<int> qs(N);
for(int i=0;i<N;++i)
  qs.push(rand());

de tal manera que no asignará dinámicamente ninguna memoria durante el ciclo.

El código real en cuestión ...

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

En lugar de una cola, ¿qué tal usar una lista?

Answer 2

Es probable que esto no sea un problema. Deque ''s asigna en pedazos de todos modos, por lo que probablemente solo reasignar un par de veces. ¿Has determinado que esto sea un cuello de botella?

De todos modos, el estándar no proporciona un acceso al contenedor de la "cola", porque eso sería contrario al propósito de la encapsulación.

Si realmente te preocupa, asigna la piscina. Esto significa preasignar la memoria por adelantado, por lo que cuando el contenedor solicita memoria, ya está allí. Realmente no puedo repasar asignadores y familiares, eso sería excesivo para una respuesta SO, pero busca asignadores en Google .

Básicamente, puedes decirle a tu contenedor de dónde obtener su memoria. Normalmente, este es el asignador predeterminado, que usa nuevo y eliminar.

Boost proporciona un asignador de grupo , y sería algo como esto:

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

El conjunto asigna la memoria por adelantado, por lo que no se realiza ninguna asignación real de memoria durante push() / pop() .

Usé una list lugar de una deque porque es más simple. Normalmente, un deque es superior a una list , pero con un asignador, las cosas que le dieron la ventaja, como el rendimiento del caché y el costo de asignación, ya no existen. Por lo tanto, una list es mucho más simple de usar.

También puedes usar un buffer circular , como este:

#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 3

Parece que necesita una estructura de datos con un método reserve () y operaciones eficientes de "push" y "pop" desde extremos opuestos. ¿Qué tal un buffer de anillo, envuelto alrededor de un std :: vector? Puede reservar () el espacio que necesita en el constructor, luego mantener los índices "frontal" y "final" en su implementación para traducir las operaciones "push" y "pop" en la interfaz pública a O (1) operaciones en el estándar subyacente ::vector.

Answer 4

Podría intentar usar un std :: deque en su lugar ...

Answer 5

Si usa una de las estructuras para componer la cola que admite la llamada a la función "reservar", debería estar bien. Si esta estructura de datos no es compatible con sus necesidades, es posible que desee buscar otra.

Dicho esto, ¿estás seguro de que hay un problema de rendimiento aquí?

Jacob

Answer 6

ver si esto ayuda: http://www.cs.sunysb.edu/~skiena/392/programs/queue.c