C ++ N个最后添加的项目容器

Question

我尝试为下一个简单任务找到最佳的数据结构：该类将N个最后添加的项目值保留在内置容器中。如果对象获得N + 1个项目，则应将其添加到容器的末尾，并从其中删除第一个项目。它就像一个简单的队列，但是类应该具有方法GetAverage，以及必须访问每个项目的其他方法。不幸的是，为此，std :: queue没有方法begin和end。

这是简单类接口的一部分：

class StatItem final
{
    static int ITEMS_LIMIT;

public:
    StatItem() = default;
    ~StatItem() = default;

    void Reset();
    void Insert(int val);

    int  GetAverage() const;

private:
    std::queue<int> _items;
};

以及所需实现的一部分：

void StatItem::Reset()
{
    std::queue<int> empty;
    std::swap(_items, empty);
}

void StatItem::Insert(int val)
{
    _items.push(val);
    if (_items.size() == ITEMS_LIMIT)
    {
        _items.pop();
    }
}

int StatItem::GetAverage() const
{
    const size_t itemCount{ _items.size() };
    if (itemCount == 0) {
        return 0;
    }

    const int sum = std::accumulate(_items.begin(), _items.end(), 0); // Error. std::queue doesn't have this methods
    return sum / itemCount;
}

有什么想法吗？

我不确定std :: deque。它有效吗？我应该将其用于此任务还是其他一些方法？

P.S.：ITEMS_LIMIT在我的情况下约为100-500个项目

Answer 1

您要查找的数据结构是循环缓冲区。 Boost库中有一个实现，但是在这种情况下，因为似乎不需要删除项目，因此可以使用std::vector或std::array轻松实现。

[您将需要到目前为止跟踪向量中元素的数量，以便可以正确求平均，直到达到元素限制为止，并且还需要达到该限制时，当前插入索引应该自动换行。

使用数组或向量将使您受益于固定的元素限制，因为元素将存储在单个内存块中，并且通过这两种数据结构，您可以预先分配所有元素。

如果选择使用std::vector，请确保使用“填充”构造函数（http://www.cplusplus.com/reference/vector/vector/vector/），这将使您能够从头开始创建正确数量的元素，并避免任何额外的分配。