Я ищу тип списка, который реализует следующую функцию (псевдокод):
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);
}
Есть ли какие-либо лучшие реализации, чем мои, возможно, фиксированный размер времени?
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
То, что вы хотите, называется круговым буфером. В 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, или что делать, если курсор и позиция вставки догоняют друг друга.
Я думаю, что вы можете написать свою собственную очередь с ограниченным интерфейсом. Как это сделать
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);
}
};
Это защищенное наследование, поэтому вы не можете изменить его размер.
Вы можете попробовать увеличить круговой буфер.