c++ - 在 C++ 中存储最后 n 个元素的正确数据结构

Question

我需要存储最后 n 个时间值，为此我使用了一个向量。我可以做到这一点并且它有效，但我的问题是，从长远来看，向量会填满，我可能会用完内存对吗？我正在使用一个 stl 浮点向量。

更清楚地说：我正在从另一个进程推回时间值，我只需要最后 5 个时间值。

我怎样才能有效地做到这一点，而又不让向量填满并最终耗尽内存？

Answer 1

听起来好像您想要一个覆盖值的循环缓冲区。
以boost为例。

Answer 2

使用队列- 在这种情况下它是完美的。你推入队列直到它的大小为 5，然后当添加一个新值时，你首先从队列中弹出然后推入它。

编辑：如果您需要能够直接访问所有 5 个元素，则deque可能是更好的选择。我也相信默认的队列实现是基于双端队列的。

Answer 3

据我所知，队列（或双端队列）的内存使用不是循环的。相反，它会在需要时增长，并偶尔复制以适应。

我建议制作自己的结构。您所需要的只是一个大小为 5 的数组，以及“最后一个”项目的指针（或索引），它将被下一个新项目覆盖。每次添加新值时，'last' 项被覆盖，'last' 指针向上移动：

last = (last+1)%5;

确保找到一种处理开始的好方法，数组中的项目少于 5 个。如果你只是在开始时用错误/中性值填充数组，你应该没问题。

Answer 4

我认为 STL 队列是你想要的。

Answer 5

不记得容器名称 :) 我会使用 std::queue 容器。因此，您可以从另一端删除，而不必担心序列中的位置。关于线程的事情......我想我不能不知道 afaik 向量和列表不是线程安全的。

Answer 6

我认为每当有新数据出现时，数据都应该转移到下一个位置，
即：
4->5->6->7 //old data
当有新数据出现时，预期的数组必须是
5->6->7->8 //updated
那个

int arr[4]={0};
int count=0;
int head=0;

void insert(int data)
{

    arr[count%4]=data;
    count++;
    if(count > 4)
        head=count%4;
    printf("count=%d head=%d\n",count,head);
}

void display()
{
    int i;
    for(i=0;i<4;i++)
    {
        printf("%d->",arr[(head+i)%4]);
    }
    printf("\n");
}

int item_at(int i)
{
    return arr[(head+i)%4];
}

int main ()
{
    int opt,data;
    while(1)
    {
        printf("0. Exit\n1. Insert\n2. Display\n3. Item at\n");
        scanf("%d",&opt);
        if(opt == 0)
            return 0;
        else if(opt == 1)
        {
            scanf("%d",&data);
            insert(data);
        }
        else if(opt == 2)
        {
            display();
        }
        else if(opt == 3)
        {
            scanf("%d",&data);
            printf("arr[%d]=%d\n",data, item_at(data));
        }
    }
return 0;
}