In principle it's not that different that deque, though:

(1) deque uses fixed-sized blocks, not increasing-size blocks. (2) dequeue supports prepending, which adds another level of indirection internally.

▲

sigbottle 4 days ago | parent [-]

You can support prepending by mirroring the allocations, probably? eg for the "negative index" case do an exponential thing in the other direction.

Your indexing has some legitimate math to be done now which can be annoying (efficiency perspective) I think you can still get o(1) with careful allocation of powers of 2.

▲

o11c 4 days ago | parent [-]

That's fine if you only ever add, but is likely to fail if you pop FIFO-style. This too is ultimately fixable but means we can no longer assume "every bucket size doubles".

That said, IMO "stable pointers" is overrated; "minimize copying" is all that's useful.

	▲	dwattttt 4 days ago \| parent [-]
		Stable pointers is a limitation for simplicity's sake. If C were better at tracking pointer invalidation, we'd be better at propagating updated pointers.