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><free / uninitialized>"]
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 Contractvoid 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
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 beforedelete[]
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≥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.
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.
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.
*
Grading Criteria:
* Notes that resizing doubles capacity using geometric multiplication (capacity * 2).
* Recognizes that if capacity starts at 0, 0×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×sizeof(T)).
* Explains arithmetic executes in CPU registers in O(1) constant time.
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.
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.
template <class T> bool verifyContainerIntegrity(const ArrayList<T>& 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:
template <class T> void reverseContainer(ArrayList<T>& 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:
template <class T> void removeAllOccurrences(ArrayList<T>& 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(n2) violation).
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≥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.