Arrays, Dynamic Arrays & Memory Layout

An array is not just a collection with square brackets. Its central contract is physical: elements of a fixed representation occupy consecutive slots, and an integer index selects a slot by arithmetic. That buys predictable random access and fast scans, but makes a hole in the middle expensive. A dynamic array retains this layout while reserving slack at the end, paying an occasional bulk move to make ordinary append cheap over a long run.

The model applies to a native array, std::vector, Rust Vec, Java ArrayList, Go slices, and many column buffers. Their exact growth factors and ownership rules differ; the geometry and failure modes do not.

The address calculation is the contract #

Let an array contain $n$ elements of fixed size $s$ bytes and let $b$ be the address of element zero. Subject to language alignment and bounds rules, element $i$ begins at

$$\mathop{\mathrm{address}}(a[i])=b+i\cdot s,\qquad 0\le i<n.$$

There is no search through previous elements. Computing the address takes constant work, so indexing is $O(1)$. It does not promise constant elapsed time: a cache miss, page fault, bounds check, or expensive element access can dominate the arithmetic.

The same formula explains a rectangular row-major matrix. For $r$ rows, $c$ columns, and zero-based coordinates $(i,j)$,

$$\mathop{\mathrm{offset}}(i,j)=i\cdot c+j.$$

The stride between adjacent columns is one element; the stride between adjacent rows is $c$ elements. Traversing a row-major matrix by rows therefore walks adjacent addresses, while a column-first traversal jumps by $c$ elements each step.

def sum_row_major(a, rows, cols):
    total = 0
    for row in range(rows):
        base = row * cols
        for col in range(cols):
            total += a[base + col]
    return total

The code is not merely stylistic. Sequential accesses let a cache line bring several following elements with it and give hardware prefetchers a simple pattern. Measure on the deployed machine before relying on a particular speedup, but preserve the access pattern when it is semantically free to do so.

Fixed array, view, and dynamic array are different objects #

An array's logical sequence need not own its storage. A slice can expose elements base[start : start + length]; its index zero maps to an offset in its owner. Passing a read-only range this way avoids a copy, but retaining the view may retain a much larger backing allocation than the caller expects. A view also needs an explicit answer to: can another writer change its elements or invalidate it?

Why dynamic append is amortized constant time #

A dynamic array tracks two numbers:

• length: initialized elements the sequence owns;
• capacity: elements that fit before a new allocation is necessary.

Appending when length < capacity constructs one element at the tail. When full, the container allocates a larger contiguous region, moves or copies the old length elements, releases the old region when its ownership rules permit it, then appends. That one operation is linear.

The important promise is amortized, not worst-case. Suppose capacity doubles when full. Starting at capacity 1 and appending until capacity reaches at least $n$ moves at most

$$1+2+4+\cdots+2^{\lceil\log_2 n\rceil-1}<2n$$

existing elements. The $n$ new-element writes plus fewer than $2n$ relocation writes are $O(n)$ total over $n$ appends, hence $O(1)$ amortized cost per append. A single full-capacity append can still take $\Theta(n)$ time and allocate memory.

Shrinking one slot at a time is the symmetric trap. If an implementation halves as soon as length < capacity / 2, alternating just around the threshold can repeatedly grow and shrink. A hysteresis gap such as shrinking only below one quarter avoids immediate reversal; exact policies remain an implementation choice.

The cost table needs movement and invalidation #

Let $n$ be the current length and assume a contiguous dynamic array.

The middle-insert row is why a sorted array offers excellent lookup but poor online updates. It also prevents a common mistake: the $O(\log n)$ search for an insertion point does not make insertion $O(\log n)$, because opening the slot shifts a suffix.

Relocation breaks borrowed addresses #

Pointers, references, iterators, slices, and foreign-language views are all ways to borrow an element's location. A reallocation replaces the backing region, so a borrowed location can become dangling or point to stale memory. The C++ standard specifies that vector::reserve invalidates all element references, pointers, and iterators if it reallocates; Rust's Vec documents the same reallocation boundary through its capacity model.

Treat this as a design constraint rather than a language footnote:

1. Keep a stable index when the collection can move and an index remains meaningful under the update contract.
2. Call reserve/with_capacity when a reliable size estimate exists, then do not exceed it while a borrow must remain valid.
3. Store stable handles in a separate indirection table when object identity must outlive buffer movement.
4. Do not expose raw storage across an API that may append, insert, shrink, or compact unless invalidation is explicitly part of that API.

An index is not automatically safe: deleting or reordering elements can change what an index denotes. State whether it identifies a position, a particular logical record, or a slot carrying a generation counter.

Capacity is not length #

Consider a buffer with length = 5, capacity = 8:

index:      0   1   2   3   4   5   6   7
storage:  [ A | B | C | D | E | · | · | · ]
logical:  [--------------- length = 5 ---------------]
allocated:[---------------- capacity = 8 ----------------]

Slots after length are storage, not elements. Reading them as initialized values, serializing them as data, or exposing them to another subsystem violates the sequence contract. In lower-level code, growth must first allocate raw storage, then construct exactly the new elements; cleanup must destroy exactly the constructed elements even if one constructor throws. Let a standard container own that state machine unless a special representation is necessary and reviewed.

Choosing arrays deliberately #

Choose a contiguous array when all of these are substantially true:

• position-based access or whole-sequence scans dominate;
• elements are reasonably movable or copied through a defined relocation operation;
• end growth is common and middle splicing is not the dominant update;
• data benefits from compact storage, vectorization, serialization, or bulk I/O.

Choose another representation when one decisive requirement conflicts: frequent ordered middle insertion points toward a tree; exact lookup with no ordering requirement may point to a hash table; durable node identity and local splice may justify linked structures; storage-page constraints call for an external-memory structure.

Diagnostic questions #

When an array-backed system is slow or corrupt, ask these in order:

1. Is the index checked against length, not capacity?
2. Does the access pattern follow physical layout, especially for matrices and columns?
3. Did an append/reallocation invalidate an exported pointer, reference, iterator, or view?
4. Is the apparent $O(1)$ append hiding a latency-critical growth step or allocator contention?
5. Is a middle update shifting more data than the workload can tolerate?
6. Are element moves actually cheap and exception-safe, or is a stable indirection layer required?

The answers identify a violated representation contract. They are more useful than prematurely switching containers by name.

Exercises #

1. A doubling dynamic array has capacity 8 and length 8. Append nine elements. Which append triggers relocation, and how many old elements move in total?

2. A row-major 1024 × 1024 matrix of 8-byte values is scanned once. Compare the address stride of the inner loop for row-first versus column-first traversal.