O(1) worst case append only array

  big-o, c++, data-structures, memory

I’m looking for a data structure that supports O(1) random access and worst case O(1) append.
In my case however, O(1) amortized time for append is not what I’m looking for.

The data structure also will not have any operations performed on it other than append and access. No deletions, no insertions, just an append-only structure.

In my case, the upper bound would be very large, maybe 8GB.

Also, this question is basically identical to this, however, the problem I have with the answer on that question is that it discounts the cost of memory allocation. Memory allocation is most of the time O(1) in c++, however, there are many times I’ve experienced where malloc takes a long time.

I was wondering if a structure like this even exists. I read this pdf, however I believe the worst case time complexity on that is still O(1) amortized.

If anybody has any ideas for a structure that can support this (not looking for implementation, just an idea), that would be great.

Source: Windows Questions C++

LEAVE A COMMENT