priority front c++ stl fifo

front - stack c++ stl



¿Qué contenedor de STL debería usar para un FIFO? (6)

¿Qué contenedor de STL se ajustaría mejor a mis necesidades? Básicamente, tengo un contenedor de 10 elementos en el que push_back continuamente hacia push_back elementos nuevos mientras pop_front en 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 una std::list sería más eficiente ya que no necesitaría reasignarme (o tal vez estoy confundiendo una std::deque por una std::vector ?). ¿O hay un contenedor aún más eficiente para mi necesidad?

PD: no necesito acceso aleatorio

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

Un millón realmente no es un gran número en informática. Como otros han sugerido, use una 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.

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

Dado que hay una gran cantidad de respuestas, puede estar confundido, pero para resumir:

Use una std::queue . La razón de esto es simple: es una estructura FIFO. Quieres FIFO, usas una std::queue .

Hace que tu intención sea clara para cualquier otra persona, e incluso para ti mismo. Una 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 una deque puede agregarse y eliminarse desde cualquier extremo, lo cual también es algo que una estructura FIFO no puede hacer.

Es por eso que deberías usar una queue .

Ahora, preguntaste sobre el rendimiento. En primer lugar, recuerde siempre esta importante regla de oro: primero, código bueno, rendimiento último.

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. Una list tiene que asignar memoria cada vez que se agrega algo, y desasignarlo cuando desaparece.

Un deque , por otro lado, asigna en trozos. Se asignará con menos frecuencia que una list . Piense en ello como una lista, pero cada fragmento de memoria puede albergar múltiples nodos. (Por supuesto, sugeriría que realmente aprendas cómo funciona ).

Por lo tanto, solo con eso un deque debería tener un mejor rendimiento, ya que 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 el rendimiento de la memoria caché . 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 una 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 es diferente 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.

Entonces, considerando eso, un deque debería ser una mejor opción. Es por eso que es el contenedor predeterminado cuando se utiliza una queue . Dicho todo esto, esta es solo una conjetura (muy) educada: tendrás que perfilar este código, usando un deque en una prueba y una list 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 una list o deque cause una disminución en 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 la queue . Es decir, cuando dices queue.push() , simplemente dirá queue.container.push_back() omitiendo la llamada a la función por completo.

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

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

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

Lo mismo vale para la list . Solo se trata de elegir qué API quieres.