Dynamic array: Difference between revisions

Revision as of 00:42, 24 November 2005

Revision as of 00:42, 24 November 2005

Line 42:

Dynamic arrays supporting additional operations efficiently can be created. For example, by using cells from the middle of the buffer instead of the beginning of the buffer, one can allow amortized constant time insertion and deletion at both ends, at the expense of keeping track of the starting index of the data (this variation may also require copying during buffer growing more often, since functions like <code>realloc()</code> typically only grow in one direction). This variation is implemented by such standard classes as C++'s <code>std::deque</code>.

Optionally, this double-ended variant can wrap elements around to the from the beginning to the end or vice versa when it runs out of room, creating a growable [[circular buffer]] which only needs to be enlarged when all cells are full. This is more space-efficient but also destroys the useful property that the array's cells occupy contiguous words of memory, allowing normal indexing.

Another variation, notably used by the [[library sort]] algorithm, leaves carefully placed gaps between elements to facilitate rapid insertion in the middle of the list.