Dynamic array: Difference between revisions

Revision as of 22:52, 20 December 2006

Revision as of 22:55, 20 December 2006

Line 48:

== Variants ==

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). ThisSee variationthe isarray-based implementedimplementation byof such[[deque]]s standardfor classesmore as C++'s <code>std::deque</code>information.

Optionally, this double-ended variant can wrap elements around 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.