3 ms·
I don't think this is a circular buffer. The strategy here is to shift the data inside the buffer to the middle once either the front or back pointer are at the
by asQuirreL 10y ago
I don't think this is a circular buffer. The strategy here is to shift the data inside the buffer to the middle once either the front or back pointer are at the front/end of the buffer respectively, rather than to wrap around.
My intuition is that a circular buffer would be better though, because it would not have to do any large scale moves of memory until it came time to reallocate.
- thomasahle 10y agoThere are many ways one might implement a circular buffer, that's not really important. The point is that you should use the standard names, so people may easily compare your "Double-ended vector" to the state of the art.
- asQuirreL 10y agoYes, there are, but in my opinion, for it to be a circular buffer, it should wrap the end of the data back round to the front when the end of the queue reaches the end of the buffer. Inserting 4 into: [x, x, x, 1, 2, 3] Produces: [4, x, x, 1, 2, 3] In a circular buffer, and: [x, 1, 2, 3, 4, x] In the proposed "double-ended vector". The technique is different, the amortized complexity is also different. I think therefore, it warrants a different name, to avoid confusion.