From fixed memory blocks to flexible data structures
Before arrays, we dealt with single values:
int x = 5;
But real programs rarely work with _one_ value.
They work with collections of data: scores, pixels, samples, prices, packets.
That’s where arrays enter the story.
What Is an Array?
An array is a fixed-size collection of elements stored contiguously in memory.
All elements:
- Have the same type
- Live next to each other
- Are accessed by an index
Conceptual view
Array A (size = 5)
Index: 0 1 2 3 4
┌───┬───┬───┬───┬───┐
Value: │10 │20 │30 │40 │50 │
└───┴───┴───┴───┴───┘
This layout is not logical — it is physical memory.
Why Arrays Are Fast
Because arrays are stored contiguously, the CPU can compute any element’s address instantly.
Address calculation
address(A[i]) = base_address + (i × sizeof(type))
No loops.
No searching.
Just math.
This is why array access is O(1) — constant time.
Arrays in Memory (Stack Example)
int arr[4] = {1, 2, 3, 4};
Stack memory layout
High Address
┌──────────┐
│ arr[3] │ ← 4
├──────────┤
│ arr[2] │ ← 3
├──────────┤
│ arr[1] │ ← 2
├──────────┤
│ arr[0] │ ← 1
└──────────┘
Low Address
Key observations:
- Size is known at compile time
- Memory is automatic
- Lifetime is tied to scope
The First Big Limitation of Arrays
Arrays are fixed-size.
Once created:
int arr[10];
You cannot:
- Grow it
- Shrink it
- Resize it
If you need more space later → you’re stuck
This limitation leads directly to dynamic arrays.
Dynamic Arrays: The Motivation
Real problems don’t know sizes upfront:
- User input
- Network packets
- Sensor data
- Growing datasets
We need memory that can be:
- Allocated at runtime
- Sized dynamically
- Managed explicitly
That means → heap memory
Dynamic Arrays (Heap Allocation)
Basic idea
Instead of:
int arr[10]; // stack, fixed
We do:
int* arr = new int[10]; // heap, dynamic
Memory view
Stack Heap
┌──────────┐ ┌──────────┐
│ arr ────┼────────────▶│ [ ][ ][ ]│
└──────────┘ └──────────┘
- Stack holds a pointer
- Heap holds the actual data
Dynamic Array Access Is Still Fast
Even though memory is dynamic, the layout is still contiguous.
Heap block:
Base → [0][1][2][3][4][5][6][7][8][9]
So access is still O(1):
arr[5] = 42;
Same math. Same speed.
Manual Memory Management (The Danger Zone)
Dynamic arrays introduce responsibility.
Allocation
int* arr = new int[10];
Deallocation
delete[] arr;
If you forget to free:
- ❌ Memory leak
If you free twice:
- ❌ Undefined behavior
If you access after free:
- ❌ Use-after-free bug (security critical)
This is why raw dynamic arrays are dangerous.
The Resize Problem (Why Dynamic Arrays Aren’t Truly Dynamic)
Let’s say we allocated 5 elements…
[10][20][30][40][50]
Now we need 6.
You cannot extend in place.
Instead, the system must:
- Allocate a bigger block
- Copy old elements
- Free old memory
Resize process
Old Block New Block
┌─────────┐ ┌───────────────┐
│10 20 30 │ ───▶ │10 20 30 40 50 │
└─────────┘ └───────────────┘
This operation is O(n).
This Leads to a Higher-Level Abstraction
Manual dynamic arrays are:
- Error-prone
- Verbose
- Unsafe
So higher-level languages and modern C++ introduce dynamic array containers that:
- Manage memory automatically
- Resize intelligently
- Preserve contiguous layout
This is where std::vector comes from.
Static Array vs Dynamic Array (Mental Model)
Static Array Dynamic Array
──────────── ─────────────
Size known at compile Size known at runtime
Stored on stack Stored on heap
Fast, safe Flexible, risky
No resizing Manual resizing
When to Use Which
Use static arrays when:
- Size is small and fixed
- Lifetime is local
- Performance predictability matters (embedded, RTOS)
Use dynamic arrays when:
- Size depends on runtime data
- Data must outlive scope
- You need flexibility
**Summary**
Arrays are the first true data structure that introduce collections of values stored contiguously in memory, enabling extremely fast O(1) indexed access through simple address arithmetic. Their simplicity and predictability make them ideal when size is known in advance and performance determinism matters.
However, static arrays are inherently fixed in size and tied to scope-based lifetime, which limits their usefulness in real-world problems where data sizes are only known at runtime. This limitation leads to dynamic arrays, which allocate contiguous memory on the heap and provide runtime flexibility at the cost of manual memory management.
Dynamic arrays preserve the performance benefits of arrays but introduce new challenges such as explicit allocation and deallocation, memory leaks, use-after-free bugs, and expensive O(n) resizing operations. These challenges motivate the need for safer, higher-level abstractions, setting the stage for containers like std::vector that automate memory handling while retaining array-like performance.