A Fast, Growable Array with Stable Pointers in C

Re:A Fast, Growable Array with Stable Pointers in C by sigbottle on Wednesday August 06, 2025 @03:35PM (#44816633)

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.

[ Parent | on HN ]

Re:A Fast, Growable Array with Stable Pointers in C by o11c on Wednesday August 06, 2025 @04:14PM (#44817155)

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.

[ Parent | on HN ]

Re:A Fast, Growable Array with Stable Pointers in C by dwattttt on Wednesday August 06, 2025 @05:52PM (#44818296)

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.

[ Parent | on HN ]