Hi Satyam, Thanks for clarifying that. Since we can use any implementation for
this, (which satisfies the requirements and an appropriate interface of course), I suggest using a dynamic array which grows on both sides.
As in you allocate one contiguous block, and start using it from the middle? The problem would be that you lose the property that pointers/iterators/references are not invalidated if the container only grows at the ends, since you may need to perform re-allocation after the beginning or end of the single contiguous block is reached. Also, with a list of blocks approach, wouldn't it be rather difficult
to provide amortized O(1) random access?
The list of blocks could be a vector of pointers, as described in the "Segmented Iterators and Hierarchical Algorithms" article that the ideas page links to. Regards, Eugene Wee