c++ - preguntas - tag del trap




¿Qué matriz/lista debo usar? (3)

Creo que puedes escribir tu propia cola con una interfaz limitada.

template<class T, class Cont = deque<T> >
class MyQueue: protected queue<T,Cont>
{
public:
    MyQueue(size_type size, const T& t=T())
    {
        while(size--)
        {
            c.push_back(t);
        }
    }

    void pop_push(const value_type& x)
    {
        pop();
        __super::push(x);
    }
};

Es herencia protegida, por lo que no puede cambiar su tamaño.

Estoy buscando un tipo de lista que implemente la siguiente función (pseudocódigo):

 list.init(5, 2, 6, 9);
 list.add(1) // 2, 6, 9, 1
 list.add(4) // 6, 9, 1, 4
 list.add(8) // 9, 1, 4, 8

Agregue un nuevo elemento a la lista de tamaño fijo y abra el más antiguo. Lo siento, no sé el nombre de este concepto, así que te pregunto cuál podría ser el nombre. ;)

Mi implementación en C ++ sería en realidad esto:

std::deque<double> values(4);

void add(double value)
{
    values.pop_front();
    values.push_back(value);
}

¿Hay implementaciones mejores que las mías, tal vez de tamaño fijo?


Lo que quieres se llama búfer circular. No hay tal contenedor en el STL, pero Boost tiene una implementación.

Si no desea obtener una gran dependencia de Boost, puede implementar fácilmente una envoltura sobre std::array (si el número de elementos es pequeño) o sobre std::vector .

La envoltura debe recordar el tamaño del contenedor subyacente y su posición actual, como esto:

template <class T>
class circular_buffer {
    std::size_t current_pos, cursor;
    std::vector<T> storage;

    circular_buffer(std::size_t size):current_pos(0), cursor(0){
        storage.resize(size);
    }

    void push_back(T elem){
        storage[current_pos++] = T;
        if (current_pos == storage.size()){
            current_pos = 0;
        }
    }

    T get_element(){
        if (cursor == storage.size()){
            cursor = 0;
        }
        return storage[cursor++];
    }

};

Tenga en cuenta que el ejemplo está simplificado y no implementa elementos como el segundo argumento de la plantilla si usa std::array , o qué hacer si el cursor y la posición de inserción se alcanzan.


Boost's circular_buffer es lo que quieres.

Ejemplo de uso:

   boost::circular_buffer<int> buffer(3);
   buffer.push_back(1);
   buffer.push_back(2);
   buffer.push_back(3);
   // now buffer is 1, 2, 3
   buffer.push_back(4);
   // now buffer is 2, 3, 4

Ejemplo vivo





types