Какой массив/список следует использовать?

Я ищу тип списка, который реализует следующую функцию (псевдокод):

 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

Добавить новый элемент в список фиксированных размеров и поместить самый старый. Извините, я не знаю названия этой концепции, поэтому я спрашиваю вас, как это имя может быть.;)

Моя реализация в С++ была бы на самом деле:

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

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

Есть ли какие-либо лучшие реализации, чем мои, возможно, фиксированный размер времени?

Ответ 1

Boost circle_buffer - это то, что вы хотите.

Пример использования:

   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

Живой пример

Ответ 2

То, что вы хотите, называется круговым буфером. В STL нет такого контейнера, но У Boost есть реализация.

Если вы не хотите сильно влиять на Boost, вы можете легко реализовать оболочку поверх std::array (если число элементов равно smallish) или над std::vector.

Обертка должна помнить базовый размер контейнера и текущую позицию, например:

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

};

Обратите внимание, что пример упрощен и не реализует такие вещи, как второй аргумент шаблона, если используется std::array, или что делать, если курсор и позиция вставки догоняют друг друга.

Ответ 3

Я думаю, что вы можете написать свою собственную очередь с ограниченным интерфейсом. Как это сделать

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

Это защищенное наследование, поэтому вы не можете изменить его размер.

Ответ 4

Вы можете попробовать увеличить круговой буфер.