Course: CSE 030: Data Structures & Algorithms Target: Lecture 4 Architecture, Dynamic Heap Management, Rule of Three & Container Testing

Conceptual Architecture & Structural Mechanics

1. The Dynamic Array Model & The Rule of Three

An ArrayList<T> implements a dynamically resizable contiguous container backed by heap memory.


graph LR

    subgraph Stack Frame [Stack Frame: Caller / Instance]

        direction TB

        C["capacity: 4"]

        S["size: 3"]

        D["T* data"]

    end

  

    subgraph Heap Memory [Heap Allocation: Contiguous Virtual Buffer]

        direction LR

        H0["data[0]<br>val_0"]

        H1["data[1]<br>val_1"]

        H2["data[2]<br>val_2"]

        H3["data[3]<br>&lt;free / uninitialized&gt;"]

    end

  

    D --> H0

    H0 --- H1

    H1 --- H2

    H2 --- H3

  

    classDef stack fill:#1e293b,stroke:#475569,stroke-width:1px,color:#f8fafc;

    classDef heap fill:#0f172a,stroke:#2563eb,stroke-width:1.5px,color:#f8fafc;

    class C,S,D stack;

    class H0,H1,H2,H3 heap;

Physical State vs. Logical Abstraction: capacity represents physical heap slots reserved via new T[capacity], whereas size denotes the active caller payload.
The Central Class Invariant: size < capacity is enforced across all quiescent states. data[size] is unconditionally safe to populate prior to triggering geometric reallocation.
The Rule of Three Causal Mandate: If an abstraction directly manages a raw resource handle (T* data), default compiler-synthesized copy routines perform shallow memberwise pointer aliasing. Explicitly implementing the Destructor, Copy Constructor, and Copy Assignment Operator guarantees deep copying and eliminates double-free memory faults.

// Invariant Verification Contract
 
void append(T value) {
 
    data[size] = value; // 1. Direct write (guaranteed safe by invariant)
 
    size++;             // 2. State transition
 
  
 
    if (size == capacity) { // 3. Invariant evaluated post-operation
 
        inflate();          // 4. Invariant restored
 
    }
 
}

2. Operational Cost Model & Shifting Asymmetry

Primitive Operation	Asymptotic Bound	Mechanical Cost Cause	Contiguous Memory Driver
Random Access `operator[]`, `at()`	$O (1)$	Single-step pointer arithmetic: `*(data + i)`	Cache-coherent physical contiguous buffer
Push Back `append()`	$O (1)$ Amortized	Direct assignment into `data[size]`; infrequent reallocation	Geometric expansion ( $2 \times$ ) distributes copying overhead
Push Front `prepend()`	$O (n)$ Linear	Backward element shift from `size` down to `1`	Preserves order; prevents forward memory clobbering
Arbitrary Insertion `insert()`	$O (n)$ Linear	Backward shift from `size` down to `index`	Accommodates new slot; generalizes `prepend` and `append`
Pop Front `removeFirst()`	$O (n)$ Linear	Forward element shift from `0` up to `size - 2`	Closes gap left by deleted root; shifts neighbors left
Pop Back `removeLast()`	$O (1)$ Amortized	Constant-time `size--` adjustment and sparsity verification	Element remains in dead heap space; zero shifts required

3. Architecture Summary & Core Mechanics

Architectural Dimension	Concrete Implementation Rule	Mechanical Failure Mode Prevented
State Fields	Three protected primitives only: `int capacity; int size; T* data;`	Unnecessary memory overhead and field synchronization drift
Class Invariant	`size < capacity` strictly at all times (Always $\geq 1$ free slot reserved)	Buffer overflows during raw `append()` writes prior to resizing
Bounds Enforcement	All access checked against `size`, never against `capacity`	Reading garbage memory; reading/writing uninitialized ADT space
Geometric Growth	`resize(capacity * 2)` on full; Base constructor sets `capacity = 1`	Zero-multiplication trap ( $0 \times 2 = 0$ ) preventing container expansion
Memory Shifting	Right shift (insert): backward loop Left shift (remove): forward loop	Element clobbering and cascading identical-value corruption
Rule of Three	Explicit destructor, copy constructor, and copy assignment operator	Shallow pointer aliasing and fatal runtime double-free crashes
Self-Assignment	`if (this == &other) return this;` Allocate replacement before* `delete[]`	Accidental source data destruction and `std::bad_alloc` corruption
Deflation Buffer	Shrink only when `size < capacity / 4` (Halves buffer; leaves 50% free)	Boundary thrashing: consecutive $O (n)$ reallocations per operation

Pre-Quiz: Assessment & Conceptual Verification

Question 1 (Short Answer)

State the core class invariant governing size and capacity in this repository’s ArrayList. How does this structural invariant alter the typical “bounds-check-first” paradigm during append()?

Question 2 (Short Answer)

In ArrayList.h, the internal resizing factor doubles capacity via capacity * 2. Why must the default constructor initialize capacity to 1 rather than 0 when allocating heap space?

Question 3 (Short Answer)

Distinguish the failure semantics between operator[] and at() when an invalid index ( $i \geq size$ ) is requested. Why does production container code retain operator[] despite lack of bounds enforcement?

Question 4 (Short Answer)

Contrast the internal index checking in insert(int index, T value) versus set(int index, T value). Why is index == size rejected by set() but explicitly allowed by insert()?

Question 5 (Short Answer)

Trace the pointer arithmetic performed by the CPU when executing list[i] on contiguous memory. How does this low-level mechanism guarantee strict $O (1)$ constant time access?

Question 6 (Short Answer)

When resizing via inflate() or deflate(), the copy loop iterates while i < size instead of i < capacity. What critical memory fault or logical error would occur during deflation if capacity were used as the loop bound?

Question 7 (Short Answer)

Explain why the element migration in prepend() must iterate backwards (for (int i = size; i > 0; i--)), whereas removeFirst() must iterate forwards (for (int i = 0; i < size - 1; i++)). What occurs if either directional traversal is reversed?

Question 8 (Short Answer)

The repository dynamically shrinks memory in shrinkIfSparse() only when size < capacity / 4, rather than size < capacity / 2. Explain the “thrashing” hazard this threshold hysteresis actively prevents.

Question 9 (Short Answer)

In removeLast(), the abandoned memory slot is never overwritten or zeroed out (size--). Why is explicit zeroing unnecessary from an encapsulation and safety standpoint?

Question 10 (Short Answer)

State the Rule of Three. Why does a class containing a raw pointer T* data to a heap resource require all three user-defined methods rather than standard compiler-generated defaults?

Question 11 (Short Answer)

If a developer omits a user-defined copy constructor, what operation does the compiler synthesize for ArrayList<T> b = a;? What immediate crash occurs when both objects leave scope?

Question 12 (Short Answer)

Why is implementing operator= fundamentally more complex than implementing the copy constructor regarding pre-existing dynamic memory?

Question 13 (Short Answer)

In operator=, why must self-assignment (this == &other) be evaluated prior to executing heap reallocations? What occurs during a = a; if this guard is omitted?

Question 14 (Short Answer)

Why does ArrayList declare two overloads for the subscript operator: T& operator[](int) and const T& operator[](int) const? What compile error surfaces if the const overload is omitted?

Question 15 (Short Answer)

In inc/ArrayList.h, the class specifies friend struct TestArrayList;. Why do structural unit test harnesses require class friendship, and why shouldn’t these testing methods simply be exposed via public getters?

Question 16 (Code Implementation)

Implement a standalone templated verification function template <class T> bool verifyContainerIntegrity(const ArrayList<T>& list, int expectedCapacity) that verifies the structural invariants of the container: size >= 0, capacity >= 1, and size < capacity. The function must execute in $O (1)$ time without modifying the list.
template <class T>
bool verifyContainerIntegrity(const ArrayList<T>& list, int expectedCapacity) {
    // Write your implementation here
}

Question 17 (Code Implementation)

Implement an external templated function template <class T> void reverseContainer(ArrayList<T>& list) that reverses the elements of an ArrayList<T> strictly in-place using symmetric two-pointer swaps with $O (n)$ time complexity and $O (1)$ auxiliary space.
template <class T>
void reverseContainer(ArrayList<T>& list) {
    // Write your implementation here
}

Question 18 (Code Implementation)

Implement an external member-like utility function template <class T> void removeAllOccurrences(ArrayList<T>& list, const T& target) that strips all entries equal to target from list. To maintain optimal performance, execute the extraction in $O (n)$ total time and $O (1)$ auxiliary space by packing retained elements forward rather than invoking removeFirst() or shifting repeatedly.
template <class T>
void removeAllOccurrences(ArrayList<T>& list, const T& target) {
    // Write your implementation here
}

Question 19 (Debugging Scenario)

A student attempts to populate an empty ArrayList<int> instance using the following initialization loop:
ArrayList<int> list;
for (int i = 0; i < 10; i++) {
    list.set(i, i * 10);
}

The code immediately aborts with std::logic_error: Index is out of bounds on loop pass $i = 0$ . Trace the internal checking condition inside set(), explain why the invariant causes this failure, and state the exact line required to fix it.

Question 20 (Debugging Scenario)

A junior programmer writes the following copy assignment operator to save code lines

template <class T>
ArrayList<T>& ArrayList<T>::operator=(const ArrayList<T>& other) {
    if (this == &other) return *this;
    delete[] data;                     // Step 1: Free old memory
    capacity = other.capacity;
    size = other.size;
    data = new T[capacity];            // Step 2: Allocate new heap buffer
    for (int i = 0; i < size; i++) {
        data[i] = other.data[i];       // Step 3: Copy contents
    }
    return *this;
}

Identify the severe memory safety flaw introduced by releasing data prior to invoking new T[capacity]. If the host operating system is completely exhausted of memory and new throws std::bad_alloc, what catastrophic state is this object left in?

Master Answer Key & AI Grading Rubric

Evaluation Protocol

This answer key is structured with deterministic grading rubrics. Each question is scored out of allocated points, detailing point distributions, key criteria, and common deductions.

Rubric: Short Answer Concept Verification (Questions 1–15)

Check

Grading Criteria:

* States invariant explicitly: size < capacity (or size != capacity, at least one free slot reserved at the end).

* Explains that slot data[size] is guaranteed pre-allocated prior to invocation.

* States append() writes first and performs bounds checks/inflation afterward to restore invariant.

Score Distribution:

* +2 pts: Invariant accurately identified (size < capacity).

* +2 pts: Validates direct, unconditional initial write to data[size] without pre-check.

Check

Grading Criteria:

* Notes that resizing doubles capacity using geometric multiplication (capacity * 2).

* Recognizes that if capacity starts at 0, $0 \times 2 = 0$ , preventing container growth without special branches.

* Notes starting at 1 provides the nonzero mathematical base case.

Score Distribution:

* +2 pts: Mentions multiplication by zero failure (0 * 2 = 0).

* +2 pts: Clarifies that starting at 1 enables exponential expansion.

Check

Grading Criteria:

* Explains at() evaluates if (index < 0 || index >= size) and throws std::logic_error.

* Explains operator[] performs raw pointer indexing without bounds checks, triggering undefined behavior on invalid access.

* Explains operator[] avoids conditional branching overhead for high-performance loops.

Score Distribution:

* +2 pts: Contrasts bounds-checked exception handling with raw unchecked access.

* +2 pts: Justifies operator[] existence via performance and zero-overhead abstractions.

Check

Grading Criteria:

* Explains set() overwrites an existing element; therefore index must reside within active bounds [0, size - 1].

* Explains insert() introduces a new item and can expand the container.

* States insert(size, val) is valid and identical to append(val).

Score Distribution:

* +2 pts: Explains set requires pre-existing element at index (must be < size).

* +2 pts: Identifies insert(size, val) as appending to the end.

Check

Grading Criteria:

* Notes array memory is physically contiguous on the heap.

* Provides address calculation formula: $Address (i) = data + (i \times sizeof (T))$ .

* Explains arithmetic executes in CPU registers in $O (1)$ constant time.

Score Distribution:

* +2 pts: Mentions contiguous virtual memory allocation.

* +2 pts: Cites pointer arithmetic base-offset calculation.

Check

Grading Criteria:

* Notes size elements are active initialized data, while slots from size to capacity - 1 are uninitialized.

* During deflation, newCapacity < capacity; iterating up to capacity causes out-of-bounds heap memory corruption.

* Copying uninitialized memory violates object encapsulation.

Score Distribution:

* +2 pts: Explains memory past size is uninitialized/garbage.

* +2 pts: Identifies heap buffer overflow when copying to a smaller buffer during deflation.

Check

Grading Criteria:

* Explains prepend() shifts right: copying must move backwards from end to prevent overwriting unshifted data (clobbering).

* Explains removeFirst() shifts left: copying must move forwards to pull adjacent right elements leftward.

* Identifies that reversing either causes catastrophic value cascading across all indices.

Score Distribution:

* +2 pts: Backward iteration rationale for rightward shift.

* +2 pts: Forward iteration rationale for leftward shift and clobbering warning.

Check

Grading Criteria:

* Identifies that shrinking at half capacity leaves size == capacity (100% full).

* Explains alternating append() and removeLast() calls trigger repeated $O (n)$ allocations on every operation.

* States shrinking at one-quarter capacity leaves container half-full, creating hysteresis slack.

Score Distribution:

* +2 pts: Traces alternating append/remove pathological thrashing sequence.

* +2 pts: Explains quarter-capacity threshold preserves amortized $O (1)$ complexity.

Check

Grading Criteria:

* Explains container interface enforces bounds against size, making slot data[size] unreachable.

* States subsequent insertions overwrite abandoned slot automatically.

* Identifies zeroing memory as unnecessary CPU instruction overhead.

Score Distribution:

* +2 pts: Logical boundary (size) completely encapsulates data.

* +2 pts: Mentions performance gain of omitting redundant clearing writes.

Check

Grading Criteria:

* States Rule of Three: Destructor, Copy Constructor, Copy Assignment Operator.

* Explains managed heap pointer (T* data) causes compiler-generated bitwise copies to alias raw addresses.

* Identifies aliasing leads to double-free crashes upon object destruction.

Score Distribution:

* +2 pts: Correctly lists all 3 methods.

* +2 pts: Explains shallow copy risks (pointer aliasing, double-free crashes).

Check

Grading Criteria:

* States synthesized constructor performs shallow copy (b.data = a.data).

* Identifies both instances now own the identical dynamic heap array address.

* Traces termination: first destructor frees memory; second destructor frees already deallocated memory (double free crash).

Score Distribution:

* +2 pts: Identifies shallow memberwise pointer copy.

* +2 pts: Explains resulting double-free abort at end-of-scope.

Check

Grading Criteria:

* Explains copy constructor initializes uninitialized memory for a newly instantiated instance.

* Explains operator= executes on an existing instance that already holds allocated heap memory.

* States assignment operator must release old heap memory, allocate fresh memory, and guard against self-assignment.

Score Distribution:

* +2 pts: Identifies pre-existing resource state of target object in assignment.

* +2 pts: Lists cleanup and reassignment requirements for existing heap blocks.

Check

Grading Criteria:

* Explains self-assignment (a = a) without a guard causes redundant allocations or dangling reads.

* In patterns that delete old buffers before allocation, missing the guard destroys the source array before copying.

* Mentions allocating new buffer before deleting old buffer provides exception safety (std::bad_alloc).

Score Distribution:

* +2 pts: Details self-assignment bug (deleting data that must be read).

* +2 pts: Explains allocation-before-deletion sequencing preserves exception safety.

Check

Grading Criteria:

* Explains non-const overload returns T&, allowing elements to be modified (lvalue reference).

* Explains const overload returns const T&, enabling read access on const ArrayList<T>& instances.

* Notes omitting const overload causes compilation errors when passing container by const reference.

Score Distribution:

* +2 pts: Correctly maps T& to mutation/lvalue and const T& to read-only semantics.

* +2 pts: Notes compilation failure for const references when const overload is missing.

Check

Grading Criteria:

* Explains unit tests must inspect private/protected member state (data, capacity, size) to verify invariants directly.

* Explains friendship provides privileged testing access without breaking public API encapsulation.

* States exposing internal pointers via public getters allows callers to corrupt heap state.

Score Distribution:

* +2 pts: Explains need for white-box invariant testing of private state.

* +2 pts: Explains how friendship prevents exposing private pointers to ordinary callers.

Rubric: Algorithmic Implementations (Questions 16–18)

Check

Model Implementation:

```cpp

template

bool verifyContainerIntegrity(const ArrayList& list, int expectedCapacity) {

if (list.getSize() < 0) return false;

if (list.getCapacity() < 1) return false;

if (list.getSize() >= list.getCapacity()) return false;

if (expectedCapacity != -1 && list.getCapacity() != expectedCapacity) return false;

return true;

}

```

Score Distribution:

* +1 pt: Proper template declaration and pass-by-const-reference signature.

* +2 pts: Verifies size >= 0 and non-zero base capacity capacity >= 1.

* +2 pts: Verifies central invariant size < capacity.

* +1 pt: Executes in strict $O (1)$ time with no allocations.

Check

Model Implementation:

```cpp

template

void reverseContainer(ArrayList& list) {

int left = 0;

int right = list.getSize() - 1;

while (left < right) {

T temp = list[left];

list[left] = list[right];

list[right] = temp;

left++;

right—;

}

```

Score Distribution:

* +1 pt: Correct template header and non-const reference parameter ArrayList<T>&.

* +2 pts: Initializes pointers at boundaries (0 and getSize() - 1).

* +2 pts: Swaps elements across symmetric indices correctly.

* +2 pts: Iterates inward and runs in $O (n)$ time with $O (1)$ space.

Check

Model Implementation:

```cpp

template

void removeAllOccurrences(ArrayList& list, const T& target) {

int writeIndex = 0;

int n = list.getSize();

for (int readIndex = 0; readIndex < n; readIndex++) {

if (list[readIndex] != target) {

list[writeIndex] = list[readIndex];

writeIndex++;

}

int removalsNeeded = n - writeIndex;

for (int k = 0; k < removalsNeeded; k++) {

list.removeLast();

}

```

Score Distribution:

* +1 pt: Template setup and pass-by-reference signature.

* +3 pts: Uses two-pointer write/read packing pattern without nested element shifts.

* +2 pts: Truncates trailing garbage via removeLast().

* +1 pt: Completes in $O (n)$ total time without extra container allocations.

Deduction:

* -4 pts: Invokes removeFirst() or shifts elements on each match ( $O (n^{2})$ violation).

Rubric: Architectural Debugging Scenarios (Questions 19–20)

Check

Diagnostics & Analysis:

* Explains that set() checks bounds against size, not capacity: if (index < 0 || index >= size).

* Default constructor sets capacity = 1, size = 0; when $i = 0$ , $0 \geq 0$ is true, throwing std::logic_error.

* set() replaces existing elements and cannot add elements to an empty list.

* Identifies the required fix: replace list.set(i, i * 10); with list.append(i * 10);.

Score Distribution:

* +2 pts: Identifies set() guards bounds against size, which evaluates to 0.

* +1 pt: Explains difference between element replacement (set) and insertion (append).

* +2 pts: Provides correct fix: list.append(...).

Check

Diagnostics & Analysis:

* Calling delete[] data destroys existing heap memory before allocating a replacement buffer.

* If memory is exhausted, new T[capacity] throws std::bad_alloc.

* Because data was deleted and not reassigned, it becomes a dangling pointer; stack unwinding triggers the destructor and causes a crash.

* Explains that assigning to a temporary or allocating before deleting preserves container state upon allocation failures.

Score Distribution:

* +3 pts: Identifies premature deletion causes use-after-free or dangling pointers on failed allocation.

* +2 pts: Explains state corruption if std::bad_alloc is thrown during new.

CSE024x30

Explorer

20260909 Lecture 4

Conceptual Architecture & Structural Mechanics

1. The Dynamic Array Model & The Rule of Three

2. Operational Cost Model & Shifting Asymmetry

3. Architecture Summary & Core Mechanics

Pre-Quiz: Assessment & Conceptual Verification

Master Answer Key & AI Grading Rubric

Rubric: Short Answer Concept Verification (Questions 1–15)

Rubric: Algorithmic Implementations (Questions 16–18)

Rubric: Architectural Debugging Scenarios (Questions 19–20)

Graph View

Table of Contents