[dwohnitmok]

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.

[igushev]

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.