The XArray data structure

Posted Jan 29, 2018 4:27 UTC (Mon) by willy (subscriber, #9762)
Parent article: The XArray data structure

Thanks for writing up my talk, Jon!

I have a quibble with your article,

> The return value on success is the previous value (if any) that was stored at index.

This is the kind of radix tree thinking that I'm trying to eradicate. Every index has a value stored at it. An "empty array" has a NULL pointer stored at every index; and a freshly-initialised array is empty. Just deleting the parenthetical would make me happy :-)

If you can suggest an improvement to the documentation that would help people get to this mindset, I'd be more than happy to incorporate it. It may just be a matter of time and people getting used to the new way of thinking.

The XArray data structure

Posted Jan 29, 2018 13:50 UTC (Mon) by nix (subscriber, #2304) [Link]

That's exactly what I was thinking. This is not a tree. It's an array that happens to have a tree as its internal storage representation currently. You can't have an array element with no value! (Sure, it's sparse, but all that means is that null elements are cheaper than non-null ones).