Show HN: Array with Constant Time Access and Fast Insertion and Deletion

Re:Show HN: Array with Constant Time Access and Fast Inserti... by superphil0 on Wednesday September 04, 2019 @02:07AM (#20874449)

If deq had to be fixed length beforehand with length k but with many insertions k can be much smaller than n^0.5 I think you might end up with a much worse worst case for insertion? Something in the order of O(n) than O(n^0.5)

Or there has to be a readjustment of k.

Cab somebody point out my thinking error?

[ Parent | on HN ]

Re:Show HN: Array with Constant Time Access and Fast Inserti... by igushev on Wednesday September 04, 2019 @01:08PM (#20879200)

Yes, the structure is sensitive for that and benefits a lot from using reserve(). I need to add automatic restructuring to maintain perfect k.

[ Parent | on HN ]