A Survey of Dynamic Array Structures
a day ago
- #data-structures
- #dynamic-arrays
- #memory-management
- Dynamic arrays are essential for runtime-determined element counts, with various implementation strategies.
- Static and runtime fixed-size arrays offer simplicity but can be inefficient or inflexible.
- Realloc-style arrays dynamically resize by copying to larger buffers, balancing generality with performance spikes.
- Arena-backed arrays use virtual memory for contiguous space but limit the number of arenas.
- Chunk/bucket arrays provide stable pointers and avoid data copying but introduce metadata complexity.
- Linked chunks simplify bookkeeping but suffer from O(N) random access.
- Trees offer balanced operations (O(log N)) but with significant indirection and complexity.
- Exponential Arrays (Xar) minimize bookkeeping with fixed metadata but have large struct sizes and discontiguous data issues.
- Each array type has trade-offs in stability, contiguity, allocation complexity, and access patterns.