Which array/list should I use?

Question

I am looking for a list type which implement the following feature (pseudocode):

 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

Add new element to fixed size list and pop the oldest one. I am sorry, I don´t know the name of this concept so I asking you, what the name could be. ;)

My implementation in C++ would be actually this:

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

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

Are there any better implementations than mine, maybe alltime fixed size?

Answer 1

Boost's circular_buffer is what you want.

Example of usage:

   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

Live example

Answer 2

What you want is called circular buffer. There is no such container in the STL, but Boost does have an implementation.

If you don't want to pull in huge dependency on Boost, you can quite easily implement a wrapper over either std::array (if the number of element is smallish) or over std::vector.

The wrapper needs to remember the underlying container size and it's current position, like this:

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++];
    }

};

Note that the example is simplified and doesn't implement things like second template argument if using std::array, or what to do if your cursor and insertion position catch up to each other.

Answer 3

I think you can write you own queue with limited interface.like this

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);
    }
};

It's protected inheritance,so you can't change its size.