存储最后 n 秒内获取的数据点的最佳数据结构是什么
What is the optimal data structure for storing data points acquired during last n seconds
我需要一个数据结构（在 C++ 中）来存储在过去 N 秒内获取的（整数，双精度）对值。 integer是相对毫秒时间戳（保证单调），double是实际的数据样本。
约束条件：
每秒的点数未知，但应用程序启动后预计不会有太大变化。典型值为每秒 10 个点。
持续时间（即 N 秒）也不是先验的，可以在执行期间更改。但是当它改变时，我可以刷新所有数据并重新开始。典型值为 60 秒。
在每次迭代中，一个新点被添加到集合的末尾，旧点（即从当前时间开始超过 N 秒）将从集合中删除。
我不需要快速的随机存取，而是快速的插入（tail）和删除（head）。
我目前正在使用std::deque，但感觉在尾端加点，从头端删除会导致频繁重新分配。
有没有标准的方法来做到这一点？或者我应该围绕 std::vector 滚动我自己的 'circular list' 包装器？
对于 "fast insertions (tail) and deletions (head)" std::deque 是最优的，因为它在两端的插入和删除都被摊销了 O(1)。您也可以使用 std::queue。标准库不提供更多 "efficient" 满足给定要求的内容。
看来你可以使用 boost 中的 circular buffer。
C++ STL 中没有等效项。
如果你不想依赖 boost，在 std::vector 上自己实现一个非收缩循环缓冲区，这并不难。
我需要一个数据结构（在 C++ 中）来存储在过去 N 秒内获取的（整数，双精度）对值。 integer是相对毫秒时间戳（保证单调），double是实际的数据样本。
约束条件：
每秒的点数未知，但应用程序启动后预计不会有太大变化。典型值为每秒 10 个点。
持续时间（即 N 秒）也不是先验的，可以在执行期间更改。但是当它改变时，我可以刷新所有数据并重新开始。典型值为 60 秒。
在每次迭代中，一个新点被添加到集合的末尾，旧点（即从当前时间开始超过 N 秒）将从集合中删除。
我不需要快速的随机存取，而是快速的插入（tail）和删除（head）。
我目前正在使用std::deque，但感觉在尾端加点，从头端删除会导致频繁重新分配。
有没有标准的方法来做到这一点？或者我应该围绕 std::vector 滚动我自己的 'circular list' 包装器？
对于 "fast insertions (tail) and deletions (head)" std::deque 是最优的，因为它在两端的插入和删除都被摊销了 O(1)。您也可以使用 std::queue。标准库不提供更多 "efficient" 满足给定要求的内容。
看来你可以使用 boost 中的 circular buffer。 C++ STL 中没有等效项。
如果你不想依赖 boost，在 std::vector 上自己实现一个非收缩循环缓冲区，这并不难。