什么是最近n秒内存储数据点的最佳数据结构

Question

我需要一个数据结构（用C++）来存储在最近N秒内获取的（整数，双精度）值对。整数是相对毫秒时间戳（保证是单调的），double是实际的数据样本。

约束：

1. 每秒的点数不事先已知，但预计不会一旦应用程序开始变化不大。典型值是每秒10点。

2. 持续时间（即N秒）也不是已知的，可以在执行期间改变。但是当它改变时，我可以清除所有数据并重新开始。典型值是60秒。

3. 在每次迭代中，将新的点添加到集合的末尾，旧点（即比当前时间早N秒）将从集合中移除。我不需要快速的随机访问，但快速插入（尾部）和删除（头部）。

我现在正在使用std :: deque，但我有一种感觉，在尾端添加点并从头端删除会导致频繁的重新分配。

有没有一个标准的方法来做到这一点？或者我应该将自己的“循环列表”包装器放在std :: vector中？

Answer 1

看起来你可以使用提升circular buffer。 在C++ STL中没有等价物。

如果你不想依赖boost，那么在std :: vector上实现一个非缩小循环缓冲区，这并不难。

Answer 2

对于“快速插入（尾部）和缺失（头部）”，std::deque是最佳的，因为它在O（1）两端均被插入和删除。您也可以使用std::queue。标准库不提供任何更符合给定要求的“高效”。