¿Qué contenedor STL debo usar para un FIFO?

¿Qué contenedor STL se adaptaría mejor a mis necesidades? Básicamente tengo un contenedor de 10 elementos de ancho en el que continuamentepush_back nuevos elementos mientras pop_frontingiero el elemento más antiguo (aproximadamente un millón de veces).

Actualmente estoy usando a std::dequepara la tarea, pero me preguntaba si std::listsería más eficiente ya que no necesitaría reasignarme (¿o tal vez estoy confundiendo a std::dequecon a std::vector?). ¿O hay un contenedor aún más eficiente para mis necesidades?

PD: no necesito acceso aleatorio

Dado que hay una gran cantidad de respuestas, es posible que se sienta confundido, pero para resumir:

Utilice un std::queue. La razón de esto es simple: es una estructura FIFO. Si quieres FIFO, usas un std::queue.

Deja en claro su intención para los demás, e incluso para usted mismo. A std::listo std::dequeno. Una lista puede insertar y eliminar en cualquier lugar, que no es lo que se supone que debe hacer una estructura FIFO, y dequepuede agregar y eliminar desde cualquier extremo, que también es algo que una estructura FIFO no puede hacer.

Es por eso que debe usar un queue.

Ahora, preguntaste sobre el rendimiento. En primer lugar, recuerde siempre esta importante regla general: el buen código primero, el rendimiento al final.

La razón de esto es simple: las personas que se esfuerzan por el rendimiento antes de la limpieza y la elegancia casi siempre terminan en último lugar. Su código se convierte en una papilla de mierda, porque han abandonado todo lo que es bueno para realmente no sacar nada de él.

Al escribir primero un código bueno y legible, la mayoría de los problemas de rendimiento se resolverán por sí mismos. Y si más tarde descubre que su rendimiento es deficiente, ahora es fácil agregar un generador de perfiles a su código agradable y limpio y averiguar dónde está el problema.

Dicho todo esto, std::queuees solo un adaptador. Proporciona la interfaz segura, pero utiliza un contenedor diferente en el interior. Puede elegir este contenedor subyacente y esto permite una gran flexibilidad.

Entonces, ¿qué contenedor subyacente debería usar? Lo sabemos std::listystd::deque ambos proporcionan las funciones necesarias ( push_back(), pop_front()yfront() ), por lo que ¿cómo decidir?

Primero, comprenda que asignar (y desasignar) memoria no es algo rápido, generalmente, porque implica ir al sistema operativo y pedirle que haga algo. A listtiene que asignar memoria cada vez que se agrega algo y desasignarlo cuando desaparece.

A deque, por otro lado, asigna en trozos. Se asignará con menos frecuencia que a list. Piense en ello como una lista, pero cada fragmento de memoria puede contener varios nodos. (Por supuesto, le sugiero que realmente aprenda cómo funciona ).

Entonces, con eso solo un deque debería funcionar mejor, porque no se ocupa de la memoria con tanta frecuencia. Combinado con el hecho de que está manejando datos de tamaño constante, probablemente no tendrá que asignar después del primer paso a través de los datos, mientras que una lista se asignará y desasignará constantemente.

Una segunda cosa a comprender es el rendimiento de la caché . Salir a la RAM es lento, por lo que cuando la CPU realmente lo necesita, aprovecha al máximo este tiempo llevándose una parte de la memoria a la caché. Debido a que dequeasigna fragmentos de memoria, es probable que acceder a un elemento en este contenedor haga que la CPU recupere el resto del contenedor también. Ahora cualquier otro acceso a ladeque será más rápido, porque los datos están en la caché.

Esto es diferente a una lista, donde los datos se asignan uno a la vez. Esto significa que los datos podrían estar esparcidos por todas partes en la memoria y el rendimiento de la caché será malo.

Entonces, considerando eso, dequedebería ser una mejor opción. Es por eso que es el contenedor predeterminado cuando se usa un queue. Dicho todo esto, esto sigue siendo solo una suposición (muy) educada: tendrá que perfilar este código, utilizando una dequeprueba en una ylist en la otra para saberlo con certeza.

Pero recuerde: haga que el código funcione con una interfaz limpia, luego preocúpese por el rendimiento.

John plantea la preocupación de que envolver un listo dequeprovocará una disminución del rendimiento. Una vez más, ni él ni yo podemos decirlo con certeza sin perfilarlo nosotros mismos, pero es probable que el compilador incorpore las llamadas que queuerealiza. Es decir, cuando dices queue.push(), realmente solo diráqueue.container.push_back() , omitiendo la llamada a la función por completo.

Una vez más, esto es solo una suposición queuefundamentada , pero el uso de a no degradará el rendimiento, en comparación con el uso del contenedor subyacente sin procesar. Como dije antes, use el queue, porque es limpio, fácil de usar y seguro, y si realmente se convierte en un perfil de problema y prueba.

Revisa std::queue . Envuelve un tipo de contenedor subyacente, y el contenedor predeterminado es std::deque.

Donde el rendimiento realmente importa, consulte la biblioteca de búfer circular de Boost .

Yo continuamente push_backnuevos elementos mientras tomo pop_frontel elemento más antiguo (alrededor de un millón de veces).

Un millón no es realmente un gran número en informática. Como han sugerido otros, utilice a std::queuecomo primera solución. En el improbable caso de que sea demasiado lento, identifique el cuello de botella usando un generador de perfiles (¡no adivine!) Y vuelva a implementarlo usando un contenedor diferente con la misma interfaz.

¿Por qué no std::queue? Todo lo que tiene es push_backy pop_front.

Una cola es probablemente una interfaz más simple que una deque, pero para una lista tan pequeña, la diferencia de rendimiento probablemente sea insignificante.

Lo mismo ocurre con la lista . Depende de la elección de la API que desee.

Utilice a std::queue, pero tenga en cuenta las compensaciones de rendimiento de las dos Containerclases estándar .

De forma predeterminada, std::queuehay un adaptador encima de std::deque. Por lo general, eso dará un buen rendimiento cuando tenga una pequeña cantidad de colas que contengan una gran cantidad de entradas, lo que posiblemente sea el caso común.

Sin embargo, no sea ciego a la implementación de std :: deque . Específicamente:

"... los deques normalmente tienen un gran costo de memoria mínimo; un deque que contiene solo un elemento tiene que asignar su matriz interna completa (por ejemplo, 8 veces el tamaño del objeto en libstdc ++ de 64 bits; 16 veces el tamaño del objeto o 4096 bytes, el que sea mayor , en libc ++ de 64 bits) ".

Para compensar eso, suponiendo que una entrada de cola es algo que le gustaría poner en cola, es decir, de tamaño razonablemente pequeño, entonces si tiene 4 colas, cada una con 30.000 entradas, la std::dequeimplementación será la opción elegida. Por el contrario, si tiene 30.000 colas, cada una con 4 entradas, lo más probable es que la std::listimplementación sea óptima, ya que nunca amortizará los std::dequegastos generales en ese escenario.

Leerás muchas opiniones sobre cómo el caché es el rey, cómo Stroustrup odia las listas enlazadas, etc., y todo eso es cierto, bajo ciertas condiciones. Simplemente no lo acepte a ciegas, porque en nuestro segundo escenario, es bastante poco probable que la std::dequeimplementación predeterminada funcione. Evalúe su uso y mida.

Este caso es lo suficientemente simple como para que puedas escribir el tuyo propio. Aquí hay algo que funciona bien para situaciones de microcontroladores donde el uso de STL ocupa demasiado espacio. Es una buena forma de pasar datos y señales desde el controlador de interrupciones a su bucle principal.

// FIFO with circular buffer
#define fifo_size 4

class Fifo {
  uint8_t buff[fifo_size];
  int writePtr = 0;
  int readPtr = 0;
  
public:  
  void put(uint8_t val) {
    buff[writePtr%fifo_size] = val;
    writePtr++;
  }
  uint8_t get() {
    uint8_t val = NULL;
    if(readPtr < writePtr) {
      val = buff[readPtr%fifo_size];
      readPtr++;
      
      // reset pointers to avoid overflow
      if(readPtr > fifo_size) {
        writePtr = writePtr%fifo_size;
        readPtr = readPtr%fifo_size;
      }
    }
    return val;
  }
  int count() { return (writePtr - readPtr);}
};