C++ 寻找流数据的最大值

Question

我有一个数据流，它以随机时间间隔生成数值。现在我不断需要获得流在特定时间间隔内产生的最大值，例如100 毫秒。

我天真的方法是拥有一对双端队列和一个最大值变量。如果传入值大于最大值，我会清除双端队列，否则我循环遍历双端队列，如果现在 - ts 大于我的回顾间隔，我将忽略它，否则检查它是否大于之前的值(除非它是第一个值)。如果是这样，我保存那个迭代器。在循环之后，我删除了双端队列(不包括我的最大迭代器)并设置了新的最大值。

我只是想知道是否有更智能、更优雅的方法通过使用不同的容器来做到这一点。理想情况下，我会坚持使用 c++ 标准库中的一些容器。

编辑:有人建议优先队列(答案被删除)。在这种情况下，我会创建一个成对的堆并告诉堆按值排序(或者如果这不可能，则创建一个包含字段时间戳和值的结构并添加一个 > 运算符)。然后每次我得到最大值时，我都会检查它是否已过期，如果是，弹出它并采用新的最大值...这是比我最初的方法更好的方法吗？

编辑:值不是唯一的

Answer 1

如果数据足够小，可以很容易地放入您的 CPU 缓存中(例如，100 万个 float 值)，那么我们都想多了。

只需存储一个 std::deque< std::pair<float, timestamp> > .

• 当有新值出现时，使用push_back() .
• 当需要查询最大元素时，调用pop_front()直到清除所有过期值。然后调用std::max_element()在整个双端队列上。

如果没有缓存未命中，它将具有与涉及 priority_queue 的更精细解决方案相同(或更好)的性能和 multiset等