queue front c++

¿Es mejor la lista que vector cuando necesitamos almacenar "los últimos n elementos"?

Question

Hay muchas preguntas que sugieren que siempre se debe usar un vector, pero me parece que una lista sería mejor para el escenario, donde necesitamos almacenar "los últimos n elementos"

Por ejemplo, digamos que necesitamos almacenar los últimos 5 elementos vistos: Iteración 0:

3,24,51,62,37,

Luego, en cada iteración, el elemento en el índice 0 se elimina y el nuevo elemento se agrega al final:

Iteración 1:

24,51,62,37,8

Iteración 2:

51,62,37,8,12

Parece que para este caso de uso, para un vector, la complejidad será O (n), ya que tendríamos que copiar n elementos, pero en una lista, debería ser O (1), ya que siempre estamos simplemente cortando Cabeza, y añadiendo a la cola cada iteración.

¿Mi entendimiento es correcto? ¿Es este el comportamiento real de una lista std ::?

Answer 1

Aquí están los comienzos de una clase de plantilla de salida de cola basada en búfer que escribí hace un tiempo, principalmente para experimentar con el uso de std::allocator (por lo que no es necesario que T sea ​​constructible por defecto). Tenga en cuenta que actualmente no tiene iteradores, o insert / remove , copiar / mover constructores, etc.

#ifndef RING_DEQUEUE_H
#define RING_DEQUEUE_H
#include <memory>
#include <type_traits>
#include <limits>
template <typename T, size_t N>
class ring_dequeue {
private:
static_assert(N <= std::numeric_limits<size_t>::max() / 2 &&
N <= std::numeric_limits<size_t>::max() / sizeof(T),
"size of ring_dequeue is too large");
using alloc_traits = std::allocator_traits<std::allocator<T>>;
public:
using value_type = T;
using reference = T&;
using const_reference = const T&;
using difference_type = ssize_t;
using size_type = size_t;
ring_dequeue() = default;
// Disable copy and move constructors for now - if iterators are
// implemented later, then those could be delegated to the InputIterator
// constructor below (using the std::move_iterator adaptor for the move
// constructor case).
ring_dequeue(const ring_dequeue&) = delete;
ring_dequeue(ring_dequeue&&) = delete;
ring_dequeue& operator=(const ring_dequeue&) = delete;
ring_dequeue& operator=(ring_dequeue&&) = delete;
template <typename InputIterator>
ring_dequeue(InputIterator begin, InputIterator end) {
while (m_tailIndex < N && begin != end) {
alloc_traits::construct(m_alloc, reinterpret_cast<T*>(m_buf) + m_tailIndex,
*begin);
++m_tailIndex;
++begin;
}
if (begin != end)
throw std::logic_error("Input range too long");
}
ring_dequeue(std::initializer_list<T> il) :
ring_dequeue(il.begin(), il.end()) { }
~ring_dequeue() noexcept(std::is_nothrow_destructible<T>::value) {
while (m_headIndex < m_tailIndex) {
alloc_traits::destroy(m_alloc, elemPtr(m_headIndex));
m_headIndex++;
}
}
size_t size() const {
return m_tailIndex - m_headIndex;
}
size_t max_size() const {
return N;
}
bool empty() const {
return m_headIndex == m_tailIndex;
}
bool full() const {
return m_headIndex + N == m_tailIndex;
}
template <typename... Args>
void emplace_front(Args&&... args) {
if (full())
throw std::logic_error("ring_dequeue full");
bool wasAtZero = (m_headIndex == 0);
auto newHeadIndex = wasAtZero ? (N - 1) : (m_headIndex - 1);
alloc_traits::construct(m_alloc, elemPtr(newHeadIndex),
std::forward<Args>(args)...);
m_headIndex = newHeadIndex;
if (wasAtZero)
m_tailIndex += N;
}
void push_front(const T& x) {
emplace_front(x);
}
void push_front(T&& x) {
emplace_front(std::move(x));
}
template <typename... Args>
void emplace_back(Args&&... args) {
if (full())
throw std::logic_error("ring_dequeue full");
alloc_traits::construct(m_alloc, elemPtr(m_tailIndex),
std::forward<Args>(args)...);
++m_tailIndex;
}
void push_back(const T& x) {
emplace_back(x);
}
void push_back(T&& x) {
emplace_back(std::move(x));
}
T& front() {
if (empty())
throw std::logic_error("ring_dequeue empty");
return *elemPtr(m_headIndex);
}
const T& front() const {
if (empty())
throw std::logic_error("ring_dequeue empty");
return *elemPtr(m_headIndex);
}
void remove_front() {
if (empty())
throw std::logic_error("ring_dequeue empty");
alloc_traits::destroy(m_alloc, elemPtr(m_headIndex));
++m_headIndex;
if (m_headIndex == N) {
m_headIndex = 0;
m_tailIndex -= N;
}
}
T pop_front() {
T result = std::move(front());
remove_front();
return result;
}
T& back() {
if (empty())
throw std::logic_error("ring_dequeue empty");
return *elemPtr(m_tailIndex - 1);
}
const T& back() const {
if (empty())
throw std::logic_error("ring_dequeue empty");
return *elemPtr(m_tailIndex - 1);
}
void remove_back() {
if (empty())
throw std::logic_error("ring_dequeue empty");
alloc_traits::destroy(m_alloc, elemPtr(m_tailIndex - 1));
--m_tailIndex;
}
T pop_back() {
T result = std::move(back());
remove_back();
return result;
}
private:
alignas(T) char m_buf[N * sizeof(T)];
size_t m_headIndex = 0;
size_t m_tailIndex = 0;
std::allocator<T> m_alloc;
const T* elemPtr(size_t index) const {
if (index >= N)
index -= N;
return reinterpret_cast<const T*>(m_buf) + index;
}
T* elemPtr(size_t index) {
if (index >= N)
index -= N;
return reinterpret_cast<T*>(m_buf) + index;
}
};
#endif

Answer 2

Aquí hay un mínimo buffer circular. Principalmente, estoy publicando eso aquí para obtener una tonelada métrica de comentarios e ideas de mejora.

Implementacion Minima

#include <iterator>
template<typename Container>
class CircularBuffer
{
public:
using iterator = typename Container::iterator;
using value_type = typename Container::value_type;
private:
Container _container;
iterator _pos;
public:
CircularBuffer() : _pos(std::begin(_container)) {}
public:
value_type& operator*() const { return *_pos; }
CircularBuffer& operator++() { ++_pos ; if (_pos == std::end(_container)) _pos = std::begin(_container); return *this; }
CircularBuffer& operator--() { if (_pos == std::begin(_container)) _pos = std::end(_container); --_pos; return *this; }
};

Uso

#include <iostream>
#include <array>
int main()
{
CircularBuffer<std::array<int,5>> buf;
*buf = 1; ++buf;
*buf = 2; ++buf;
*buf = 3; ++buf;
*buf = 4; ++buf;
*buf = 5; ++buf;
std::cout << *buf << " "; ++buf;
std::cout << *buf << " "; ++buf;
std::cout << *buf << " "; ++buf;
std::cout << *buf << " "; ++buf;
std::cout << *buf << " "; ++buf;
std::cout << *buf << " "; ++buf;
std::cout << *buf << " "; ++buf;
std::cout << *buf << " "; --buf;
std::cout << *buf << " "; --buf;
std::cout << *buf << " "; --buf;
std::cout << *buf << " "; --buf;
std::cout << *buf << " "; --buf;
std::cout << *buf << " "; --buf;
std::cout << std::endl;
}

Compilar con

g++ -std=c++17 -O2 -Wall -Wextra -pedantic -Werror

Manifestación

En Coliru: pruébalo en línea

Answer 3

Creo que incluso usar std :: deque también tiene una sobrecarga de elementos de copia en ciertas condiciones porque std :: deque es esencialmente un mapa de matrices, por lo que std :: list es una buena idea para eliminar la sobrecarga de copia.

Para aumentar el rendimiento de transversal para std :: list, puede implementar una agrupación de memoria para que std :: list asigne memoria desde un troncal y su localidad espacial para el almacenamiento en caché.

Answer 4

Diga brevemente que std::vector es mejor para un tamaño de memoria no modificable. En su caso, si mueve todos los datos hacia adelante o agrega datos nuevos en un vector, debe ser un desperdicio. Como @David dijo que std::deque es una buena opción, ya que, por pop_head , pop_head y push_back . lista de dos vías

de la referencia cplus cplus sobre la lista

En comparación con otros contenedores de secuencia estándar de base (matriz, vector y deque), las listas generalmente funcionan mejor en la inserción, extracción y movimiento de elementos en cualquier posición dentro del contenedor para el cual ya se ha obtenido un iterador, y por lo tanto también en algoritmos que hacen uso intensivo De estos, como algoritmos de clasificación.

El principal inconveniente de las listas y las listas de avance en comparación con estos otros contenedores de secuencias es que carecen de acceso directo a los elementos por su posición; Por ejemplo, para acceder al sexto elemento en una lista, uno tiene que iterar desde una posición conocida (como el principio o el final) hasta esa posición, lo que requiere un tiempo lineal en la distancia entre estos. También consumen algo de memoria adicional para mantener la información de enlace asociada a cada elemento (lo que puede ser un factor importante para listas grandes de elementos pequeños).

sobre deque

Para las operaciones que involucran la inserción frecuente o la eliminación de elementos en posiciones distintas al principio o al final, los deques tienen peor desempeño y tienen iteradores y referencias menos consistentes que las listas y las listas de reenvíos.

vetor

Por lo tanto, en comparación con las matrices, los vectores consumen más memoria a cambio de la capacidad de administrar el almacenamiento y crecer dinámicamente de manera eficiente.

En comparación con los otros contenedores de secuencia dinámica (deques, listas y forward_lists), los vectores son muy eficientes para acceder a sus elementos (como las matrices) y agregar o eliminar elementos relativamente eficientes de su extremo. Para las operaciones que involucran la inserción o eliminación de elementos en posiciones distintas al final, se desempeñan peor que las otras, y tienen iteradores y referencias menos consistentes que las listas y las listas de avance.

Answer 5

El problema es que O (n) solo habla sobre el comportamiento asintótico ya que n tiende a infinito. Si n es pequeño, entonces los factores constantes involucrados se vuelven significativos. El resultado es que, para "los últimos 5 elementos enteros", quedaría aturdido si el vector no superara la lista. Incluso esperaría que std::vector venciera a std::deque .

Para los "últimos 500 elementos enteros", todavía esperaría que std::vector sea ​​más rápido que std::list , pero std::deque ahora probablemente gane. Para "los últimos 5 millones de elementos de copia lenta", std:vector sería el más lento de todos.

Sin embargo, un búfer de anillo basado en std::array o std::vector probablemente sería aún más rápido.

Como (casi) siempre con problemas de rendimiento:

• encapsular con una interfaz fija
• Escribe el código más simple que puede implementar esa interfaz.
• Si el perfil muestra que tiene un problema, optimice (lo que hará que el código sea más complicado).

En la práctica, solo usar un std::deque , o un buffer de anillo pre-construido si tiene uno, será lo suficientemente bueno. (Pero no vale la pena tomarse la molestia de escribir un búfer de anillo a menos que el perfil lo indique).

Answer 6

Ninguno. Su colección tiene un tamaño fijo y std::array es suficiente.

La estructura de datos que implementas se llama un búfer de anillo. Para implementarlo, crea una matriz y realiza un seguimiento del desplazamiento del primer elemento actual.

Cuando agrega un elemento que empujaría un elemento fuera del búfer, es decir, cuando elimina el primer elemento, incrementa el desplazamiento.

Para obtener elementos en el búfer, agregue el índice y el desplazamiento y tome el módulo de este y la longitud del búfer.

Answer 7

Sí. La complejidad temporal del vector std :: para eliminar elementos del final es lineal. std :: deque puede ser una buena opción para lo que está haciendo, ya que ofrece inserción y eliminación de tiempo constante al principio y al final de la lista y también un mejor rendimiento que std :: list

Fuente:

http://www.sgi.com/tech/stl/Vector.html

http://www.sgi.com/tech/stl/Deque.html

Answer 8

Si necesita almacenar los últimos elementos N , lógicamente está haciendo algún tipo de cola o un búfer circular, std::stack y std::deque son implementaciones de las colas LIFO y FIFO .

Puede utilizar boost::circular_buffer o implementar manualmente un búfer circular simple:

template<int Capcity>
class cbuffer
{
public:
cbuffer() : sz(0), p(0){}
void push_back(int n)
{
buf[p++] = n;
if (sz < Capcity)
sz++;
if (p >= Capcity)
p = 0;
}
int size() const
{
return sz;
}
int operator[](int n) const
{
assert(n < sz);
n = p - sz + n;
if (n < 0)
n += Capcity;
return buf[n];
}
int buf[Capcity];
int sz, p;
};

Ejemplo de uso para búfer circular de 5 elementos int:

int main()
{
cbuffer<5> buf;
// insert random 100 numbers
for (int i = 0; i < 100; ++i)
buf.push_back(rand());
// output to cout contents of the circular buffer
for (int i = 0; i < buf.size(); ++i)
cout << buf[i] << '' '';
}

Como nota, tenga en cuenta que cuando tiene solo 5 elementos, la mejor solución es la que se implementa rápidamente y funciona correctamente.

Answer 9

Si puedes usar Boost, prueba boost::circular_buffer :

Es un tipo de secuencia similar a std::list o std::deque . Es compatible con iteradores de acceso aleatorio, operaciones de inserción y borrado de tiempo constante al principio o al final del búfer e interoperabilidad con algoritmos estándar.

Proporciona almacenamiento de capacidad fija: cuando se llena el búfer, los datos nuevos se escriben comenzando al principio del búfer y sobrescribiendo el antiguo

// Create a circular buffer with a capacity for 5 integers.
boost::circular_buffer<int> cb(5);
// Insert elements into the buffer.
cb.push_back(3);
cb.push_back(24);
cb.push_back(51);
cb.push_back(62);
cb.push_back(37);
int a = cb[0]; // a == 3
int b = cb[1]; // b == 24
int c = cb[2]; // c == 51
// The buffer is full now, so pushing subsequent
// elements will overwrite the front-most elements.
cb.push_back(8); // overwrite 3 with 8
cb.push_back(12); // overwrite 24 with 12
// The buffer now contains 51, 62, 37, 8, 12.
// Elements can be popped from either the front or the back.
cb.pop_back(); // 12 is removed
cb.pop_front(); // 51 is removed

El circular_buffer almacena sus elementos en una región contigua de la memoria, que luego permite la inserción rápida, la eliminación y el acceso aleatorio de los elementos.

PS ... o implementar el búfer circular directamente como lo sugiere Taemyr .

Overload Journal # 50 - Aug 2002 tiene una buena introducción (de Pete Goodliffe) a la escritura de un sólido búfer circular tipo STL.

Answer 10

std::deque es una opción mucho mejor. O bien, si ha evaluado std :: deque y encontró que su rendimiento es inadecuado para su uso específico, podría implementar un búfer circular en una matriz de tamaño fijo, almacenando el índice del inicio del búfer. Al reemplazar un elemento en el búfer, sobrescribiría el elemento en el índice de inicio y luego establecería el índice de inicio en su valor anterior más un módulo del tamaño del búfer.

El recorrido de la lista es muy lento, ya que los elementos de la lista se pueden dispersar en toda la memoria, y el desplazamiento vectorial es sorprendentemente rápido, ya que los movimientos de la memoria en un solo bloque de memoria son bastante rápidos, incluso si se trata de un bloque grande.

La charla Cómo domar a la bestia de rendimiento de la conferencia Reunión C ++ 2015 podría ser de su interés.