什麼是最近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。標準庫不提供任何更符合給定要求的「高效」。