Double-ended vector – is it useful?

Re:Double-ended vector – is it useful? by asQuirreL on Monday May 23, 2016 @03:47AM (#11752471)

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.

[ Parent | on HN ]

Re:Double-ended vector – is it useful? by thomasahle on Monday May 23, 2016 @07:25AM (#11753123)

There 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.

[ Parent | on HN ]

Re:Double-ended vector – is it useful? by asQuirreL on Monday May 23, 2016 @08:14AM (#11753325)

Yes, 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.

[ Parent | on HN ]