Re:Show HN: Array with Constant Time Access and Fast Inserti...
by igushev on Wednesday September 04, 2019 @01:52AM
(#20874375)
Interesting that some people found an article about tiered vectors, I didn't find it back then. I implemented this structure many many years ago and also published in Bauman Moscow State Technical University magazine back in 2012:
http://engjournal.ru/articles/101/101.pdf
(in Russian)
[ Parent
| on HN ]
Re:Show HN: Array with Constant Time Access and Fast Inserti...
by dwohnitmok on Thursday September 05, 2019 @02:08AM
(#20884249)
Tiered vectors have been around for a while. The paper for them came out in 1998. They've just always been rather underappreciated. I only found out about them through this thread too.
I don't think any of us mean to imply that you copied off another implementation; independent discovery happens all the time! It's great you've made this a usable C++ library and have contributed your own thoughts on the structure!
It looks like you're having difficulty with some of the resizing. The two array approach described here https://stackoverflow.com/questions/10478260/looking-for-a-d... makes resizing a lot easier. You just double the size of the main array and increase the size of the offset array by the square root of two, without needing to fiddle around with anything else. You also get unchanged amortized time bounds.