用于存储最新值的 C++ 固定大小容器

Question

我想知道C++中下列问题最适合的数据结构是什么

我想存储 100 个按新近度排序的花车。因此，当我添加（推送）一个新项目时，其他元素会向上移动一个位置。每次触发事件时，我都会收到一个值，然后将其添加到我的数据结构中。

当元素数量达到100时，我想删除（pop）最后（最旧）的项目。

我希望能够遍历所有元素并对它们执行一些数学运算。

我查看了所有标准 C++ 容器，但其中 none 满足了我的所有需求。使用标准 C++ 代码实现此目的的最简单方法是什么？

Answer 1

刚看到您需要迭代它们。使用 list.

你的基本函数看起来像这样

void addToList(int value){
    list100.push_back(value);
    if(list100.size() > 100){
        list100.pop_front();
    }
}

遍历它们也很容易：

for(int val : list100){
    sum += val;
}
// Average, or whatever you need to do

显然，如果您使用 int 以外的内容，则需要对其进行更改。虽然这增加了比您需要的多一点的功能，但它非常有效，因为它是一个双向链表。

http://www.cplusplus.com/reference/list/list/

Answer 2

您可以使用 std::array、std::dequeue、std::list 或 std::priority_queue

Answer 3

你想要一个循环缓冲区。您可以使用 Boost's implementation 或通过分配一个数组来创建自己的数组，并跟踪所用范围的开始和结束。这归结为做索引模 100。

Answer 4

无需创建自己的库或使用库，std::vector 是最有效的标准数据结构。一旦达到其最大大小，将不再有动态内存分配。与动态内存分配的成本相比，向上移动 100 个浮点数的成本是微不足道的。（这就是为什么 std::list 是一个慢数据结构的原因）。 vector 没有 push_front 函数。相反，您必须使用 v.insert(v.begin(), f)

当然，这是假设您正在做的事情对性能至关重要，而事实可能并非如此。在那种情况下，我会使用 std::deque 来更方便地使用。

Answer 5

一个MAP (std::map)应该可以解决你的需求。使用 Key 作为对象，使用 value 作为当前推送数 nPusheCount，每当您将元素添加到映射时，nPusheCount 都会递增。向地图添加新元素时，如果元素少于 100 个，只需将数字作为键添加到 MAP，将 nPushCount 作为值添加。如果您已经有 100 个元素，请检查该数字是否已存在于地图中并执行以下操作：

如果map中已经存在number，则添加number作为key，nPushCount作为value；
如果不是，删除具有最低 nPushCount 作为值的号码，然后添加具有更新的 nPushCount 的所需号码。

用于存储最新值的 C++ 固定大小容器

C++ Fixed Size Container to Store Most Recent Values

c++

stack

queue

containers