¿Qué contenedor STL debo usar para un FIFO?

Question

¿Qué contenedor STL satisfaría mejor mis necesidades? Básicamente, tengo un contenedor de 10 elementos en el que continuamente push_back elementos nuevos, mientras que pop_front es el elemento más antiguo (alrededor de un millón de veces).

actualmente estoy usando un std::deque para la tarea, pero me preguntaba si un std::list sería más eficiente, ya que no tendría que reasignar sí (o tal vez estoy confundir una std::deque para un std::vector?). ¿O hay un contenedor aún más eficiente para mi necesidad?

P.S. No necesito acceso aleatorio

Answer 1

Puesto que hay una gran variedad de respuestas, puede ser confundido, pero para resumir:

Utilice un std::queue. La razón de esto es simple: es una estructura FIFO. Desea FIFO, usa un std::queue.

Hace que tu intención sea clara para cualquier otra persona, e incluso para ti mismo. Un std::list o std::deque no lo hace. Una lista puede insertarse y eliminarse en cualquier lugar, que no es lo que se supone que debe hacer una estructura FIFO, y un deque puede agregar y eliminar de cualquier extremo, que también es algo que una estructura FIFO no puede hacer.

Es por esto que deberías usar un queue.

Ahora, ha preguntado acerca del rendimiento. En primer lugar, siempre recuerde esta importante regla de oro: Primero, código bueno, último rendimiento.

La razón de esto es simple: las personas que luchan por el rendimiento antes de la limpieza y la elegancia casi siempre terminan en último lugar. Su código se convierte en un desastre, 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 sus problemas de rendimiento se resolverán solos. Y si más tarde descubre que su rendimiento es deficiente, ahora es fácil agregar un generador de perfiles a su código limpio y agradable, y descubrir dónde está el problema.

Dicho todo esto, std::queue es 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? Sabemos que std::list y std::deque proporcionan las funciones necesarias (push_back(), pop_front() y front()), entonces, ¿cómo decidimos?

Primero, comprenda que asignar (y desasignar) la memoria no es una tarea rápida, generalmente, porque implica salir al sistema operativo y pedirle que haga algo. Un list tiene que asignar memoria cada vez que se agrega algo y desasignarlo cuando se va.

A deque, por otro lado, asigna en trozos. Se asignará con una frecuencia inferior a list. Piense en ello como una lista, pero cada fragmento de memoria puede albergar múltiples nodos. (Por supuesto, sugeriría que really learn how it works.)

Por lo tanto, con eso solo un deque debería funcionar mejor, porque no se ocupa de la memoria con tanta frecuencia. Mezclado con el hecho de que está manejando datos de tamaño constante, probablemente no tendrá que asignarlos después de la primera pasada a través de los datos, mientras que una lista será asignada y desasignada constantemente.

Una segunda cosa para entender es cache performance. Salir a la memoria RAM es lento, por lo que cuando la CPU realmente lo necesita, saca lo mejor de esta vez al llevar una porción de memoria a la caché. Debido a que deque asigna trozos de memoria, es probable que al acceder a un elemento en este contenedor la CPU vuelva a traer el resto del contenedor. Ahora cualquier acceso adicional al deque será rápido, porque los datos están en caché.

Esto no se parece a una lista, donde los datos se asignan de uno en uno. Esto significa que los datos se pueden distribuir por todas partes en la memoria, y el rendimiento de la memoria caché será malo.

Por lo tanto, teniendo en cuenta que, un deque debería ser una mejor opción. Es por eso que es el contenedor predeterminado cuando se usa un queue. Dicho todo esto, esta sigue siendo solo una conjetura (muy) educada: tendrá que crear un perfil de este código, utilizando un deque en una prueba y list en la otra para saberlo con certeza.

Pero recuerde: obtenga el código trabajando con una interfaz limpia, luego preocúpese por el rendimiento.

John plantea la preocupación de que al ajustar list o deque se reduzca el rendimiento. Una vez más, ni él ni yo podemos decirlo con certeza sin elaborar un perfil nosotros mismos, pero lo más probable es que el compilador alinee las llamadas que hace el queue. Es decir, cuando diga queue.push(), realmente solo dirá queue.container.push_back() omitiendo la llamada de función por completo.

Una vez más, esto es solo una suposición educada, pero usar un queue no degradará el rendimiento, en comparación con el uso del contenedor subyacente en bruto. Como he dicho antes, use queue, ya que es limpio, fácil de usar y seguro, y si realmente se convierte en un perfil problemático y en una prueba.

Answer 2

A queue es probablemente una interfaz más simple que deque pero para una lista tan pequeña, la diferencia en el rendimiento es probablemente despreciable.

Lo mismo ocurre con list. Solo se trata de elegir qué API quieres.

Answer 3

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

Answer 4

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

Answer 5

I push_back continuamente nuevos elementos mientras pop_front ing el elemento más antiguo (alrededor de un millón de tiempo).

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

Answer 6

Donde el rendimiento realmente importa, consulte el Boost circular buffer library.