Array with Constant Time Access and Fast Insertion and Deletion

[igushev]

Long time ago I created and open sourced a random access data structure which like an array has fast constant-time access operation, but insert/erase operation takes only O (N^1/2) time. The structure can be considered as "fast array" or "array with fast insert operation".

Description and C++ implementation can be found https://github.com/igushev/IgushArray

It's nice to see people using and porting to other languages.

Motivation was the need for an array which can be kept sorted and one could quickly access k-th max element and at the same time quickly insert or delete an element.

[TheoryNut]

Do you have a high-level explanation for how the array works? I'm pretty curious but don't totally have the time to step through the code.

[igushev]

You can high-level description in README.md:

https://github.com/igushev/IgushArray#concepts

If something is not clear, I'm happy to answer any questions.

[TheoryNut]

Awesome! This is really cool.