1. Introduction & Motivation What is a Dynamic Vector? A dynamic vector (or dynamic array) is a resizable array-based data structure that can grow and shrink during program execution. Unlike static arrays with fixed size, vectors adapt to your needs. Common names across languages: Rust: Vec C++: std::vector Java: ArrayList Python: list JavaScript: Array Why Do We Need Them? Static Array Problem: rustlet numbers: [i32; 5] = [1, 2, 3, 4, 5]; // What if I need to add a 6th element? // 💥 Can't! Size is fixed at compile time. ``` **Real-world scenarios:** - User uploading unknown number of photos - Reading a file with unknown number of lines - Building a to-do list that grows over time - Processing streaming data **We need:** A data structure that combines array performance with dynamic sizing. --- ## **2. The Problem with Static Arrays** ### **Static Array Characteristics:** ``` Memory layout (static array of 5 integers): ┌────┬────┬────┬────┬────┐ │ 10 │ 20 │ 30 │ 40 │ 50 │ └────┴────┴────┴────┴────┘ idx0 idx1 idx2 idx3 idx4 Size: Fixed at compile time Location: Usually stack Access: O(1) - direct indexing Resize: Impossible! ``` **Strengths:** - ✅ **O(1) random access** - `array[3]` is instant - ✅ **Cache-friendly** - contiguous memory - ✅ **No overhead** - just the data, no metadata **Weaknesses:** - ❌ **Fixed size** - must know size at compile time - ❌ **Wasted space** - over-allocate or run out - ❌ **Can't grow** - need a completely new array --- ## **3. Dynamic Vector Design** ### **The Big Idea: Separation of Size and Capacity** The key insight is to maintain **two separate values**: ``` ┌─────────────────────────────────┐ │ DYNAMIC VECTOR │ ├─────────────────────────────────┤ │ ptr: *mut T │ ← Pointer to heap memory │ len: usize │ ← Number of elements stored │ capacity: usize │ ← Total allocated space └─────────────────────────────────┘ ``` **Visual representation:** ``` Capacity: 8 slots allocated Len: 4 elements stored ┌────┬────┬────┬────┬────┬────┬────┬────┐ │ 10 │ 20 │ 30 │ 40 │ ?? │ ?? │ ?? │ ?? │ └────┴────┴────┴────┴────┴────┴────┴────┘ ↑___________________↑ ↑___________________↑ len = 4 unused capacity ptr points here → Core Operations: Create - Initialize empty vector Push - Add element to end Pop - Remove element from end Get - Access element by index Grow - Reallocate when full 4. Implementation Strategy Step 1: The Data Structure rustpub struct MyVec { ptr: *mut T, // Heap pointer len: usize, // Current count capacity: usize, // Total slots } Why these fields? ptr: Where the data lives (heap address) len: How many elements we have capacity: How much room before we need to grow Step 2: Construction rustpub fn new() -> Self { MyVec { ptr: ptr::null_mut(), // No allocation yet len: 0, capacity: 0, } } ``` **Initial state:** ``` MyVec { ptr: NULL len: 0 capacity: 0 } Heap: (nothing allocated) Why start empty? Don't waste memory if the vector is never used! Step 3: The Growth Strategy This is the heart of a dynamic vector! Option 1: Grow by 1 each time (BAD) rust// Every push allocates new memory vec.push(1); // Allocate 1 vec.push(2); // Allocate 2, copy 1 vec.push(3); // Allocate 3, copy 1, 2 vec.push(4); // Allocate 4, copy 1, 2, 3 // Total copies: 0 + 1 + 2 + 3 = 6 copies for 4 elements! Time complexity: O(n²) for n pushes! 😱 Option 2: Double capacity (GOOD) rust// Double when full Capacity progression: 0 → 1 → 2 → 4 → 8 → 16 → 32 ... vec.push(1); // Allocate 1 vec.push(2); // Allocate 2, copy 1 vec.push(3); // Allocate 4, copy 1, 2 vec.push(4); // Use existing (no allocation!) vec.push(5); // Allocate 8, copy 1, 2, 3, 4 // Total copies: 0 + 1 + 2 + 0 + 4 = 7 copies for 5 elements Time complexity: O(n) for n pushes → amortized O(1) per push! 🎉 Step 4: Push Implementation (The Complex Part) Let's break this into phases: Phase A: Check if growth needed rustpub fn push(&mut self, value: T) { if self.len == self.capacity { // Vector is full, need to grow! self.grow(); } // Now we have space, add the element self.insert_at_end(value); } Phase B: Growth algorithm rustfn grow(&mut self) { // 1. Calculate new capacity let new_capacity = if self.capacity == 0 { 1 // Bootstrap: start with 1 } else { self.capacity * 2 // Double }; // 2. Allocate new memory let layout = Layout::array::(new_capacity).unwrap(); let new_ptr = unsafe { alloc(layout) as *mut T }; // 3. Copy old data to new location if !self.ptr.is_null() { unsafe { ptr::copy_nonoverlapping( self.ptr, // source new_ptr, // destination self.len // count ); // 4. Free old memory let old_layout = Layout::array::(self.capacity).unwrap(); dealloc(self.ptr as *mut u8, old_layout); } } // 5. Update metadata self.ptr = new_ptr; self.capacity = new_capacity; } ``` **Visual walkthrough:** ``` Before growth (len=2, capacity=2): Old: [10, 20] ↑ ptr Step 1: Allocate new (capacity=4) Old: [10, 20] New: [??, ??, ??, ??] ↑ new_ptr Step 2: Copy data Old: [10, 20] New: [10, 20, ??, ??] Step 3: Free old Old: [FREED] New: [10, 20, ??, ??] ↑ ptr (updated) Result: capacity=4, len=2, space for 2 more! Phase C: Insert element rustfn insert_at_end(&mut self, value: T) { unsafe { // Calculate address: ptr + len let target = self.ptr.add(self.len); // Write value without dropping old value ptr::write(target, value); } // Increment length self.len += 1; } Why ptr::write and not assignment? rust// WRONG (would try to drop uninitialized memory): *self.ptr.add(self.len) = value; // 💥 Tries to drop garbage! // CORRECT (just writes the value): ptr::write(self.ptr.add(self.len), value); // ✅ Safe Step 5: Access (Get) rustpub fn get(&self, index: usize) -> Option<&T> { if index < self.len { unsafe { // ptr.add(index) moves pointer forward // * dereferences it // & borrows it Some(&*self.ptr.add(index)) } } else { None // Out of bounds } } ``` **Pointer arithmetic:** ``` Array: [10, 20, 30, 40] ↑ ↑ ↑ ↑ ptr+0 +1 +2 +3 get(2): self.ptr.add(2) → points to 30 * → dereferences to value 30 & → creates reference &30 Step 6: Cleanup (Drop) The problem: When vector goes out of scope, memory is leaked! rust{ let mut v = MyVec::new(); v.push(10); v.push(20); } // v dropped, but heap memory still allocated! ❌ The solution: Implement Drop trait rustimpl Drop for MyVec { fn drop(&mut self) { if !self.ptr.is_null() && self.capacity > 0 { unsafe { // Step 1: Drop all elements for i in 0..self.len { ptr::drop_in_place(self.ptr.add(i)); } // Step 2: Free the memory let layout = Layout::array::(self.capacity).unwrap(); dealloc(self.ptr as *mut u8, layout); } } } } Why two steps? rust// Example: Vec let mut v = MyVec::new(); v.push(String::from("hello")); v.push(String::from("world")); // When dropped: // 1. drop_in_place("hello") - frees String's heap data // 2. drop_in_place("world") - frees String's heap data // 3. dealloc(ptr) - frees the vector's array memory // Without step 1, we'd leak "hello" and "world"! ``` --- ## **5. Time Complexity Analysis** ### **Individual Operations** | Operation | Best Case | Worst Case | Amortized | |-----------|-----------|------------|-----------| | `push()` | O(1) | O(n) | **O(1)** | | `pop()` | O(1) | O(1) | O(1) | | `get(i)` | O(1) | O(1) | O(1) | | `insert(i)` | O(1) at end | O(n) | O(n) | | `remove(i)` | O(1) at end | O(n) | O(n) | ### **Push Analysis (The Important One)** **Worst case:** When vector is full, we must: 1. Allocate new array: O(1) 2. Copy all elements: O(n) 3. Free old array: O(1) **Total: O(n)** **But this is rare!** Let's count for n=8 pushes: ``` push(1): capacity 0→1, copy 0 elements push(2): capacity 1→2, copy 1 element push(3): capacity 2→4, copy 2 elements push(4): no realloc push(5): capacity 4→8, copy 4 elements push(6): no realloc push(7): no realloc push(8): no realloc Total copies: 0+1+2+4 = 7 copies for 8 pushes Average: 7/8 ≈ 0.875 copies per push As n → ∞, average → 1 copy per push = O(1)! ``` **Mathematical proof:** ``` Sequence of reallocations at sizes: 1, 2, 4, 8, 16, ..., n Copies performed: 0, 1, 2, 4, 8, ..., n/2 Sum = 1 + 2 + 4 + ... + n/2 = 2^0 + 2^1 + 2^2 + ... + 2^(log n - 1) = 2^(log n) - 1 = n - 1 Average per push = (n-1) / n ≈ 1 = O(1) ``` --- ## **6. Memory Management** ### **Heap vs Stack** ``` STACK (fast, limited): ┌─────────────┐ │ MyVec { │ ← The struct itself (24 bytes) │ ptr │ │ len │ │ capacity │ │ } │ └──────┬──────┘ │ │ points to... ▼ HEAP (slower, large): ┌────┬────┬────┬────┬────┬────┐ │ 10 │ 20 │ 30 │ 40 │ ?? │ ?? │ ← The actual data └────┴────┴────┴────┴────┴────┘ Why heap? Size unknown at compile time Need to resize Can be very large (millions of elements) Memory Allocation (Layout) rustlet layout = Layout::array::(capacity).unwrap(); ``` **What's happening:** ``` For T = i32 (4 bytes), capacity = 8: Layout { size: 4 × 8 = 32 bytes align: 4 bytes (i32 alignment) } Memory allocated: ┌────┬────┬────┬────┬────┬────┬────┬────┐ │ 4B │ 4B │ 4B │ 4B │ 4B │ 4B │ 4B │ 4B │ └────┴────┴────┴────┴────┴────┴────┴────┘ 32 bytes total, aligned on 4-byte boundaries ``` ### **Memory Safety Rules** 1. **No use-after-free**: Can't access freed memory 2. **No double-free**: Can't deallocate twice 3. **No leaks**: Must free everything we allocate 4. **Proper alignment**: Memory addresses must align with type requirements **Rust's `unsafe` enforces:** "If you violate these, it's YOUR bug!" --- ## **7. Practical Considerations** ### **Growth Factor Trade-offs** | Strategy | Pros | Cons | |----------|------|------| | **Double (×2)** | Fast amortized time | More wasted space | | **×1.5** | Less wasted space | Slower growth | | **+Fixed amount** | Predictable | O(n²) time! | **Real implementations:** - Rust `Vec`: doubles (×2) - C++ `std::vector`: Usually ×1.5 or ×2 (implementation-defined) - Java `ArrayList`: ×1.5 - Python `list`: ×1.125 (with more complex formula) ### **Space Overhead** ``` Best case (just filled to capacity): Overhead = 0% Worst case (just grew, half empty): Overhead = 50% Example: capacity=100, len=51 (just triggered growth from 50) Wasted slots: 49 Overhead: 49/100 = 49% ``` ### **When to Use Dynamic Vectors** **✅ Good for:** - Unknown size at compile time - Frequent appends to end - Random access by index - Cache-friendly iteration **❌ Bad for:** - Frequent insertions in middle (use LinkedList) - Need to preserve pointers to elements (use Box/Rc) - Lots of insertions/deletions (use HashMap, BTreeMap) --- ## **Summary & Key Takeaways** ### **The Big Ideas:** 1. **Separation of concerns**: `len` vs `capacity` 2. **Amortization**: Rare expensive operations averaged out 3. **Doubling strategy**: Key to O(1) amortized push 4. **Manual memory**: Explicit allocation, copying, freeing 5. **Unsafe blocks**: Necessary for performance, require care ### **Complexity Cheat Sheet:** ``` Access: O(1) [Direct indexing] Search: O(n) [Linear scan] Push: O(1)* [Amortized, worst O(n)] Pop: O(1) [Just decrement len] Insert: O(n) [Shift elements] Delete: O(n) [Shift elements] Space: O(n) [+ up to 50% overhead] Why This Matters: Understanding dynamic vectors teaches you: Memory management fundamentals Time/space trade-offs Amortized analysis Real-world data structure design Most importantly: You now understand what happens when you do vec.push() in any language! Further Study Next topics to explore: Implement pop(), insert(), remove() Add iterators Compare with other structures (LinkedList, Deque) Study other growth strategies Thread-safe vectors (Arc, Mutex) Questions to ponder: What if we shrink when len < capacity/4? How to handle zero-sized types? Can we avoid copying on growth? (No, but tricks exist!) End of Lecture 🎓

Finding Dynamic Vector Solution

Loading your video...

Feedback