C++: ¿Cola con eficiente obtención/colocación de múltiples elementos?

Question

Por lo tanto, creo que debería haber una buena solución incorporada para esto en C++, pero no estoy seguro de qué se trata.

Necesito una cola (idealmente segura para subprocesos, pero puedo envolverla en sincronización si es necesario) que maneja grupos de bytes de manera eficiente, permitiendo lecturas/escrituras de diferentes tamaños.

por lo que la interfaz se ve como p.

//removes the first bytesToRead elements from the front of the queue and places them in array; returns the actual number of bytes dequeued 
int dequeue(unsigned char *array, int bytesToRead) 
//Adds bytesToWrite elements from array to the end of the queue; does nothing and returns 0 if this would exceed the queue's max size 
int enqueue(unsigned char *array, int bytesToWrite) 

Puedo escribir uno yo mismo sin demasiada dificultad, pero parece que esto debería ser algo que se hace fácilmente fuera de la plataforma.

Lo mejor en el STL parece que podría ser un stringbuf - Tendría que emparejar llamadas a sgetc/pubseekoff a mano, pero parece que funcionaría.

Estoy buscando hacer esto como un reemplazo inmediato para una implementación de cola actual que es un problema de rendimiento; la lectura en esta implementación es O (N) en la cantidad de datos en la cola. (Es una implementación muy ingenua: cada dequeue da como resultado una copia de matriz de los datos restantes en la cola.)

Requisitos adicionales (puedo implementarlos en un contenedor si es necesario): -Necesito poder especificar un tamaño máximo de la memoria intermedia operaciones -Leer debe recuperar todos los datos disponibles si es menor se dispone de datos que se solicitó operaciones -Escribir debe hacer nada si la escritura solicitada excede el tamaño máximo y devolver un indicador de fallo

Así , mis preguntas: 1) es stringbuf suficiente? ¿Son las operaciones de lectura/escritura O (1) relativas a la cantidad de datos en el búfer, suponiendo que no es necesario cambiar el tamaño? (Obviamente, potencialmente serían O (n) en el número de elementos solicitados).

2) ¿Hay alguna otra clase que no veo que sea suficiente?

¡Gracias de antemano!

Answer 1

¿Podría usar std::stringstream donde ingresa en la cola con write y salga de la cola con read?

Answer 2

Hmmm ... ¿Ha intentado lo obvio:

class queue { 
     std::deque<unsigned char> data; 
public: 
    int enqueue(unsigned char *array, int bytesToWrite) { 
     data.insert(data.end(), array, array+bytesToWrite); 
    } 

    int dequeue(unsigned char *array, int bytesToRead) { 
     std::copy(data.begin(), data.begin()+bytesToRead, array); 
     // or, for C++11: std::copy_n(data.begin(), bytesToRead, array); 

     data.erase(data.begin(), data.begin()+bytesToRead); 
    } 
}; 

Lo sentimos, no me siento bastante ambicioso suficiente en el momento de añadir el bloqueo y los valores de retorno que solicitó, pero tampoco debería ser terriblemente difícil. Sin embargo, en lugar de jugar con sus valores de retorno, cambiaría la interfaz para usar iteradores (o, si realmente insiste, una referencia a un vector).

Esto se garantiza que es lineal en la cantidad de elementos insertados/eliminados.

Answer 3

Según lo sugerido, std::stringstream es probablemente la solución más fácil y mejor.

Otra alternativa es std::deque, le dará la eficiencia que desee (amortización constante para todas las lecturas/escrituras desde cualquier extremo de la cola, y generalmente mucho menos que O (N) de reasignación si la capacidad se agota).El único inconveniente es que std::deque no es compatible con la aritmética del puntero (porque todos los elementos no son necesariamente contiguos (en fragmentos)), por lo que no podrá realizar una operación de lectura/escritura en bloque, deberá iterar de la siguiente manera:

std::deque<unsigned char> buf; 

int dequeue(unsigned char *array, int bytesToRead) { 
    int result = std::min(bytesToRead, buf.size()); 
    std::copy(buf.begin(), buf.begin() + result, array); 
    buf.erase(buf.begin(), buf.begin() + result); 
    return result; 
}; 

int enqueue(unsigned char *array, int bytesToWrite) { 
    buf.insert(buf.end(), array, array + bytesToWrite); 
    return bytesToWrite; 
}; 

Probablemente debería hacer la última comprobación de implementación si se alcanza la capacidad máxima y ajustar el valor resultante en consecuencia.

Answer 4

Si desea una implementación eficiente realmente rápida, me gustaría ir con una simple implementación circular de búfer, lo que significa que puede hacer sus lecturas en una o dos copias (dependiendo de si está terminando o terminando su búfer) Esto le permite usar memcpy que en mi experiencia casi siempre supera el bucle a través de muchos elementos para hacer su copia.

Si el rendimiento es menos crítico, iré con la respuesta de Jerry.