CODEWITHSUNDEEP
c++vectordata-structuresdeque
Syam
Syam

Reputation: 193

What is the optimal data structure for storing data points acquired during last n seconds

I need a data structure (in C++), to store (integer,double) pair values acquired over last N seconds. The integer is a relative milliseconds time stamp (guaranteed to be monotonic) and the double is the actual data sample.

Constraints:

  1. The number of points per second is not known apriori, but is not expected to vary much once the application is started. Typical value is 10 points per second.

  2. The duration (i.e. N seconds) is also not known apriori and can change during execution. But when it is changed, I'm OK with flushing all data and starting fresh. Typical value is 60 seconds.

  3. In every iteration, a new point is added to the end of the set and old points (i.e. older than N seconds from current time) are to be removed from the set.

  4. I don't need fast random access, but fast insertions (tail) and deletions (head).

I am using std::deque at the moment, but I have a feeling that adding points at the tail end and deleting from the head end will cause frequent re-allocations.

Is there a standard way to do this? Or should I roll my own 'circular list' wrapper around std::vector?

Upvotes: 0

Views: 265

Answers (2)

stgatilov
stgatilov

Reputation: 5533

It seems that you can use circular buffer from boost. There is no equivalent in C++ STL.

If you don't want to depend on boost, implement a non-shrinking circular buffer yourself over std::vector, that's not hard.

Upvotes: 0

Shoe
Shoe

Reputation: 76240

For "fast insertions (tail) and deletions (head)" std::deque is optimal, given that it's amortized O(1) both insertion and deletion at both ends. You could also use std::queue. The standard library doesn't provide anything more "efficient" with the given requirements.

Upvotes: 2

Related Questions