array representations

contiguous

• elements occupy a single continuous address interval

• address computation is purely arithmetic

  • address(i) = base + i * stride
• no metadata required beyond base and stride
• relocation requires copying the entire region

discontinuous

• elements are stored in multiple, non-adjacent regions

• address computation requires at least one indirection

• typical realizations

  • pointer arrays
  • block directories
  • stable slot tables

• enables growth and removal without relocating existing elements

• trades locality and simplicity for stability and flexibility

pointer stable

• once an element address is observed, it remains valid until explicit destruction
• prohibits moving live elements in memory
• required when external code caches element pointers
• severely restricts resizing strategies in contiguous layouts

index stable

• once an index is assigned, it permanently identifies the same logical element

• index becomes an identity rather than a position

• requires indirection, tombstones, or fixed slots to prevent shifts

• enables removal without invalidating references by index

static

• capacity fixed at initialization
• no reallocation or structural mutation of storage
• size changes only by modifying a usage counter
• simplest model with strongest predictability

dynamic

• capacity may change during lifetime

• growth strategy defines amortized cost and fragmentation

• shrink strategy determines memory return behavior

• resizing may or may not preserve pointer stability depending on contract

single type

• one interpretation of memory, one stride
• simplest aliasing and correctness model

nested or multidimensional

• arrays represent higher dimensional index spaces

• flat representation

  • one contiguous allocation
  • index mapping function computes linear offset

• hierarchical representation

  • arrays of pointers to subarrays
  • enables ragged shapes at cost of indirection

mixed type

• memory region accessed through multiple type interpretations

• requires explicit control over layout and aliasing

• common mechanisms

  • structs to define composite layout
  • byte-wise access for reinterpretation

• incorrect aliasing leads to undefined behavior

resize

• changes capacity and possibly physical location
• contiguous dynamic arrays may relocate storage
• relocation breaks pointer stability but preserves index ordering

append

• adds element at logical end
• contiguous layouts preserve relative ordering
• amortized cost depends on growth policy

insert

• adds element at arbitrary logical position
• contiguous layouts require shifting or gaps
• shifting breaks pointer and index stability beyond insertion point

removal

• deletes an element and frees its slot

• strategy defines semantic cost

  • shift removal preserves order, breaks stability

  • swap removal preserves density, breaks identity

  • tombstones preserve identity, reduce density

array of structs

• each element stores all fields of a logical record
• one base pointer, one stride
• optimal for per-record access
• less efficient for field-wise bulk processing

struct of arrays

• each field stored in a separate array

• multiple base pointers

• optimal for bulk and vectorized operations

• per-record access requires multiple loads

static contiguous

• fixed buffer plus usage count
• no allocation after initialization

dynamic contiguous

• buffer with explicit capacity and used counters
• growth policy defines relocation behavior

stable slots contiguous

• contiguous slot array

• slot identity is stable

• removal creates empty slots

• reuse via free list

• iteration must test slot occupancy

fixed blocks

• storage divided into equal-sized contiguous blocks
• blocks never moved once allocated
• index mapping computes block index and offset
• preserves pointer stability within blocks

unequal block sizes

• blocks grow geometrically
• reduces allocation frequency
• requires cumulative size metadata for indexing

per-element allocation

• each element allocated independently
• maximal pointer stability
• minimal spatial locality
• high allocator metadata overhead

stable slots

• logical index refers to a slot, not a position

• slot identity is preserved across removals

• empty slots accumulate unless reused

• iteration must skip empty slots

• reuse is mediated by a free list

contract

• indices represent permanent element identities
• pointer stability not guaranteed across growth

design

• contiguous slot array with embedded free list
• growth only increases capacity

insertion

• reuse freed slots before extending used range

removal

• mark slot empty
• link slot into free list

iteration

• scan full used range
• skip empty slots

compaction

• optional operation

• requires emitting index remapping

array of structs

• struct { float x; float y; float z; }
• spatially local per-point access
• inefficient for operations on a single coordinate

struct of arrays

• separate x, y, z arrays
• efficient for coordinate-wise transforms
• higher cost for per-point access
• dimensions can be optional by using a null pointers for arrays