在C++中存储最后n个元素的适当数据结构

Question

我需要存储最近的n个时间值，我使用一个向量来实现。当前方法可以工作，但是我的问题是，在长期运行中，向量将会填充，并且可能会耗尽内存，对吗？我正在使用一个浮点数的STL向量。

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

如何高效地实现这一点，而不让向量填满并最终耗尽内存？

- mgr

Answer 1

听起来你希望有一个可以覆盖值的循环缓冲区。
可以参考boost提供的示例。

- mkaes

Answer 2

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

我建议你自己创建数据结构。你只需要一个大小为5的数组和一个指向“最后”项的指针（或索引），该指针将被下一个新项目覆盖。每添加一个新值，就会覆盖“最后”项，并将“最后”指针向上移动：

last = (last+1)%5;

确保找到一个好的方法来处理起始位置，如果数组中少于5个元素。如果你只是在开始时填充数组错误/中性值，那么应该没问题。

- Gaminic

---

在我看来，那应该是被选中的答案。在这种情况下，没有任何std::容器比纯C风格的固定大小数组更有优势。除非你想使用像boost这样的外部库，否则就该选择这种方式。 - kuroi neko

Answer 3

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

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

- Ivaylo Strandjev

---

除非 n 很大并且对象复制起来很昂贵，否则 std::vector 的性能优于 std::deque。 - James Kanze

@JamesKanze，你的观点是什么 - 为什么这样认为？我们需要能够将对象添加到向量的一端并从另一端删除对象。deque 就是为这种用法而设计的，我不认为 vector 会表现得更好。 - Ivaylo Strandjev

@izomorphius 但确实如此。std::vector的一个更小的常数因子意味着只有在有很多元素或它们非常昂贵时才会开始表现得比std::deque更好。 - James Kanze

Answer 4

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

- forrestchen

Answer 5

我忘记了容器的名称 :) 我会使用std::queue容器。这样你就可以从序列的另一端删除，而不必担心位置。关于线程的问题...我想我无法帮助，但据我所知，向量和列表不是线程安全的。

- Adrián Pérez

Answer 6

我认为每当有新的数据出现时，数据应该移动到下一个位置，例如：
4->5->6->7 //旧数据
当有新的数据出现时，期望的数组应该是：
5->6->7->8 //更新后
为了实现这个目标。

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;
}

- codenumb