Suggestion for a Data Structure!

Question

I have the following requirements for a data structure:

1. Direct access to an element with the help of a key (Key will be an integer, range is also same as integer range)
2. Avoid memory allocation in chunks (Allocate contigous memory for the data structure including the data)
3. Should be able to grow the data structure size dynamically

Which data structure would you suggest?

Any pointers in the direction will also be of help.

Answer 1

sounds like a hash table (aka dictionary) to me

Answer 2

1) sparse array
2,3) heap

You will basically have to implement a heap and a sparse array that share single large buffer. Normally, the value stored in a sparse array is a pointer. In your case the pointer would be relative to the base of your heap, otherwise known as an offset. The heap should be before the sparse array in the large buffer so that resizing the heap does not change offsets.

Normally something like this is done as a flatten step. In other words, a normal hash table or sparse array is used with system managed pointers up until the point it is all needed as one contiguous block. At that point, everything is packed into some other format and expanded again later.