6 ms·

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 publis

• mises 7y ago
  Thank you very much for making this MIT licensed and not GPL. I'm glad it's actually usable by people. Looks like a great project!
• dwohnitmok 7y ago
  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-data-container-with-o1-indexing-and-ologn-insertion-and-dele/10519240#10519240 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.
  • igushev 7y ago
    I also found out about tiered vectors only in this thread. At the time of implementation I tried to Google for something like this but didn't find.