c++ - 数据结构来维护值的时间窗口？

Question

我正在解决一个问题，我需要维护一个十秒时间窗口的点。随着新点的到来，它们会添加到队列的末尾，随着时间的推移，超过十秒的点就会离开队列。队列可以变得很大，比如 1000 个或更多元素。

有趣的是我还需要快速访问中间的元素，比如第一个早于 3 秒的元素。快速做到这一点是困难的部分。

请注意，队列始终是有序的。

我考虑过排序数组，但是从前面删除元素的速度很慢。列表搜索速度慢。

我是用 C++ 做的，但欢迎使用任何语言。

Answer 1

I'm working on a problem where I need to maintain a ten second time window of points. As new points come in they add to end of queue and as time goes on points that are older than ten seconds so leave front of queue. Queue can get pretty big , say 1000 or more elements.

1000 个元素看起来并不大，所以我看不出有什么问题。实际的时序要求会更有用。

Note that queue is always sorted.

按什么排序？时间？由于时间似乎是索引本身并且它是一个 FIFO，因此根据定义似乎就是这种情况。

I thought about sorted array but that is slow to remove elements from front.

为什么需要额外排序？它有多慢，需要多快？你使用什么实现？如果您知道点数的上限，为什么不使用循环缓冲区呢？

List is slow to search.

您使用什么搜索方法？它的实现是什么样的？有多慢？它需要多快？关于搜索的性质，是否有任何可以帮助加快搜索速度的事前已知信息？二分查找不够快吗？