我应该使用哪个数组/列表？

Question

我正在寻找一个实现以下功能的列表类型(伪代码):

 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

将新元素添加到固定大小列表并弹出最旧的元素.对不起,我不知道这个概念的名称,所以我问你,名字是什么.;)

我在C++中的实现实际上是这样的:

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

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

有没有比我更好的实现,也许是所有固定大小？

Answer 1

Boost的circular_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

实例

Answer 2

你想要的是循环缓冲区.STL中没有这样的容器,但Boost确实有一个实现.

如果你不想强烈依赖Boost,你可以很容易地实现一个包装器std::array(如果元素的数量很小)或者结束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,则不会实现第二个模板参数,或者如果光标和插入位置相互匹配,该怎么办.