Data Structure for steady stream of timestamped data

Question

I have a steady stream of timestamped data, of which I want to always keep the last 5 seconds of data in a buffer. Furthermore, I would like to provide support for extracting data of a given subinterval of the 5 seconds, so something like

interval = buffer.extractData(startTime, endTime);

What std data structure would be most appropriate for this?

1) The fact that a new sample pushes an old sample out hints that a Queue would be a good data structure

2) The fact that we have to have random access to any elements, in order to obtain the sub interval maybe suggests that vector is appropriate.

Furthermore, what would be a good way to present the subinterval to the user? My suggestion would be using two iterators?

Answer 1

Unless you are in a fairly performance critical part of the code, a deque would seem reasonable. It can grow and shrink to accommodate changes in your data rate and has reasonable performance for double-ended queue operations and random access.

If the code is performance sensitive (or, even worse, has real-time requirements on top, as is the case with many timestamped buffers), you need to prevent memory allocations as much as possible. You would do this by using a ring buffer with a preallocated array (be it through unique_ptr<T[]> or vector) and either dropping elements when the buffer size is exceeded, or (taking one for the team and) increasing its size.

By never reducing size again, your ring buffer might waste some memory, but remember that in most cases memory is fairly plentiful.

Representing intervals by two iterators or a range object is both common, and although the C++ standard library often prefers iterators, my personal preference is for range objects due to their (in my opinion) slightly better usability.