Study Guide

📖 Core Concepts

C++ Arrays: The Basics C++ arrays are fixed-size collections of same-type elements stored in contiguous memory, offering fast, direct access but lacking flexibility and built-in safety checks.

C++ Vectors: The Basics C++ vectors are dynamic arrays from the Standard Template Library (STL) that automatically resize, providing flexibility and safety features over traditional C++ arrays.

Internals: Memory Management Arrays use static, compile-time memory allocation (stack), while vectors manage memory dynamically on the heap, allowing them to grow and shrink at runtime.

Performance Comparison Arrays offer constant-time access but slow insertions/deletions, while vectors provide amortized constant-time additions and flexible performance trade-offs for dynamic data.

Use Cases & Best Practices Use arrays for fixed-size, performance-critical data where size is known at compile time, and vectors when the collection size is unknown or changes frequently.

Practical Application Applying arrays and vectors effectively involves analyzing trade-offs between an array's raw speed and a vector's safety and flexibility to write robust, maintainable code.

📌 Must Remember

C++ Arrays: The Basics

Fixed Size: The size of an array must be a constant expression known at compile time and cannot be changed.
Contiguous Memory: All elements are stored next to each other in memory, allowing for efficient pointer arithmetic and cache performance.
Zero-Based Indexing: The first element is at index 0, and the last is at index size - 1.
No Bounds Checking: Accessing an index outside the array's bounds (e.g., myArray[10] in a 5-element array) leads to undefined behavior without warning.
Decay to Pointers: In many contexts, an array name decays into a pointer to its first element, which can be a source of confusion.
Initialization Syntax: Can be initialized with an initializer list, e.g., int scores[5] = {100, 95, 88, 76, 92};.

C++ Vectors: The Basics

Dynamic Size: Vectors can grow or shrink at runtime by adding or removing elements.
STL Component: Part of the C++ Standard Template Library; you must #include <vector> to use them.
Member Functions: Use member functions like .push_back(), .pop_back(), .size(), and .clear() to manage elements.
Two Access Methods: Use operator[] for fast, unchecked access (like arrays) or .at() for slower, bounds-checked access that throws an exception if the index is invalid.
Value Semantics: Vectors can be copied, assigned, and passed by value, and they manage their own memory automatically.
Initialization: Can be initialized in various ways, including std::vector<int> v = {1, 2, 3}; (initializer list).

Internals: Memory Management

Array Memory: Local arrays are typically allocated on the stack, which is fast but limited in size.
Vector Memory: Vectors manage their elements in a dynamic array on the heap, providing large storage capacity but with allocation overhead.
Capacity vs. Size: A vector's size is the number of elements it currently holds, while its capacity is the number of elements it can hold before needing to reallocate memory.
Reallocation: When a vector's size exceeds its capacity, it allocates a new, larger block of memory, copies all existing elements, and deallocates the old block.
Growth Strategy: The capacity of a vector typically grows by a factor (often 1.5 or 2) to make append operations efficient on average.
reserve(): You can use .reserve() to pre-allocate capacity and avoid multiple reallocations if you know the approximate number of elements in advance.

Performance Comparison

Access Time: Both arrays and vectors offer constant time, $O(1)$ , for element access by index (e.g., arr[i], vec[i]).
End Insertion/Deletion (Vectors): Adding an element to the end of a vector with .push_back() is amortized constant time, $O(1)$ . It's usually fast, but occasionally slow when a reallocation occurs.
Middle Insertion/Deletion: Inserting or deleting elements in the middle of an array or vector is linear time, $O(n)$ , because subsequent elements must be shifted.
Memory Overhead: Vectors have a small overhead (pointers to manage the heap memory, size, and capacity variables), whereas arrays have zero memory overhead.
Stack vs. Heap: Array (stack) allocation is instantaneous, while vector (heap) allocation involves a system call, which is significantly slower.

Use Cases & Best Practices

Use Arrays For: Performance-critical code, embedded systems, low-level data structures, or when the size of the collection is fixed and known at compile time.
Use Vectors For: General-purpose programming, when the number of elements is unknown, or when you need flexibility like adding/removing elements.
Prefer Vectors by Default: In modern C++, std::vector is the default choice for a sequence of elements due to its safety and flexibility.
Pass by Reference: Pass vectors to functions by reference (const std::vector<T>&) to avoid expensive copies, unless the function needs to modify its own copy.
Use std::array for Fixed-Size: For a fixed-size container with the benefits of STL interfaces (like iterators), prefer std::array over C-style arrays.

Practical Application

Array Example: Storing a fixed set of lookup values, like the number of days in each month, is a perfect use case for an array.
Vector Example: Reading an unknown number of entries from a file or user input is a classic scenario where a vector is necessary.
Performance Trade-off: A game might use a std::vector for a list of active enemies (which changes) but a C-style array for a large, static tilemap to maximize access speed.
Maintainability: Vector-based code is often easier to read and maintain because size is managed automatically, reducing the risk of bugs from manual memory management.
Error Handling: Using .at() with vectors makes code more robust by catching out-of-bounds access errors, a common problem with C-style arrays.

⚠️ Common Mistakes

❌ MISTAKE: Using sizeof(array) to get the number of elements.

Why it happens: sizeof() returns the total size of the array in bytes, not the element count. For example, sizeof(int_array) on a system with 4-byte integers will return count * 4.
✅ Instead: Calculate the count using sizeof(array) / sizeof(array[0]). For STL containers like std::vector or std::array, simply use the .size() member function.
Memory aid: sizeof measures space, not stuff.
Topic: C++ Arrays: The Basics

❌ MISTAKE: Assuming vectors shrink automatically when elements are removed.

Why it happens: Calling .pop_back() or .erase() reduces a vector's size, but its capacity (the allocated memory) remains unchanged to avoid frequent reallocations.
✅ Instead: If you need to reclaim the unused memory, use the "shrink-to-fit" idiom: vec.shrink_to_fit(); (C++11 and later).
Topic: Internals: Memory Management

❌ MISTAKE: Passing a C-style array to a function and expecting to know its size inside.

Why it happens: Arrays "decay" to pointers when passed as function arguments. The function only receives a pointer to the first element, losing all size information.
✅ Instead: Pass the size of the array as a separate argument to the function, e.g., void processArray(int arr[], int size);. Better yet, use std::vector or std::array, which carry their size information with them.
Topic: C++ Arrays: The Basics

❌ MISTAKE: Resizing a vector with resize() and accessing new elements without initializing them.

Why it happens: vec.resize(new_size) will default-construct new elements if the size increases. For primitive types like int, this means their value is indeterminate (garbage).
✅ Instead: Use vec.resize(new_size, initial_value) to provide a specific value for all new elements, or loop through and initialize them after resizing.
Topic: Practical Application

❌ MISTAKE: Creating a loop that modifies a vector's size while iterating over it.

Why it happens: Adding or removing elements can invalidate iterators, pointers, and references to elements in the vector, leading to crashes or undefined behavior.
✅ Instead: Use the iterator returned by .erase() which points to the next valid element. For adding elements, it's often safer to store items to be added in a temporary vector and add them after the loop finishes.
Topic: C++ Vectors: The Basics

❌ MISTAKE: Using operator[] when you are not 100% sure an index is valid.

Why it happens: operator[] provides no bounds checking for performance reasons. Accessing an invalid index is a common bug that can corrupt memory silently.
✅ Instead: Use the .at() member function when an index might be out of bounds. It will throw an std::out_of_range exception, which can be caught and handled gracefully.
Topic: Use Cases & Best Practices

📚 Key Terms

Array: A fixed-size, indexed collection of elements of the same data type, stored in a contiguous block of memory.

Used in context: int fibonacci[10]; declares an array to hold the first 10 Fibonacci numbers.
Don't confuse with: std::array (an STL container wrapper) or std::vector (a dynamic array).
Topic: C++ Arrays: The Basics

Vector: A dynamic array from the C++ Standard Template Library that can automatically manage its own storage and change size at runtime.

Used in context: We used a std::vector<std::string> names; to store a list of names read from a file because we didn't know how many there would be.
Topic: C++ Vectors: The Basics

Contiguous Memory: A memory layout where elements are stored sequentially, one after another, with no gaps.

Used in context: Because array elements are in contiguous memory, you can iterate over them quickly using a pointer.
Topic: Internals: Memory Management

Heap: A region of computer memory used for dynamic memory allocation, where objects can be allocated and deallocated at runtime.

Used in context: A std::vector allocates its element buffer on the heap, allowing it to request more memory from the operating system as it grows.
Topic: Internals: Memory Management

Stack: A region of memory used for static memory allocation, storing local variables and function call information in a last-in, first-out (LIFO) manner.

Used in context: Local arrays like int buffer[256]; are typically allocated on the stack, which is very fast but limited in size.
Topic: Internals: Memory Management

Size: The number of elements currently stored in a container.

Used in context: After my_vector.push_back(42);, its .size() will be 1.
Don't confuse with: Capacity.
Topic: C++ Vectors: The Basics

Capacity: The amount of space allocated by a vector, representing the number of elements it can hold before it must reallocate its internal memory buffer.

Used in context: A vector might have a .size() of 5 but a .capacity() of 8, meaning it can add 3 more elements before needing to reallocate.
Don't confuse with: Size.
Topic: Internals: Memory Management

Reallocation: The process where a vector, having run out of capacity, allocates a new, larger block of memory, copies all existing elements to the new location, and frees the old block.

Used in context: The occasional performance hiccup was caused by vector reallocation when a large number of elements were added.
Topic: Performance Comparison

Time Complexity: A measure of how the runtime of an algorithm scales with the size of its input (n).

Used in context: The time complexity of accessing an array element by index is $O(1)$ , or constant time.
Topic: Performance Comparison

Amortized Time Complexity: The average time taken per operation, when averaged over a sequence of operations.

Used in context: While a single .push_back() can be slow ( $O(n)$ ) if it triggers reallocation, its amortized time complexity is $O(1)$ .
Topic: Performance Comparison

Undefined Behavior (UB): The result of executing code with properties that are not specified by the C++ language standard, which can lead to unpredictable program behavior, including crashes or silent data corruption.

Used in context: Accessing an array out of bounds results in undefined behavior.
Topic: C++ Arrays: The Basics

🔍 Key Comparisons

Array vs. Vector

Feature	C-Style Array	`std::vector`
Size	Fixed, known at compile time	Dynamic, can change at runtime
Memory Location	Stack (for local) or static	Heap (for elements)
Size Management	Manual (must pass size around)	Automatic (use `.size()`)
Bounds Checking	None (leads to Undefined Behavior)	Optional (via `.at()`)
Flexibility	Low	High (add, remove, resize)
Performance	Slightly faster due to no overhead	Minimal overhead, amortized $O(1)$ push_back
When to use	Fixed-size data, performance-critical loops	General purpose, unknown data size

Memory trick: Think of an Array as Anchored (fixed in size and place). Think of a Vector as a Van (can carry a variable number of items and go anywhere).

Topic: Use Cases & Best Practices

🔄 Key Processes

Vector Resizing (Reallocation)

Step 1: Capacity Check

What happens: An element is added (e.g., via push_back()) and the vector checks if size == capacity.
Key indicator: If size < capacity, the new element is added at index size, size is incremented, and the process stops. If they are equal, the process continues to Step 2.

Step 2: Allocate New Memory

What happens: The vector requests a new, larger block of memory from the heap. The new capacity is typically the old capacity multiplied by a growth factor (e.g., 2).
Key indicator: A pointer to a new memory location is obtained.
Common error: This step can fail if the system is out of memory, throwing a std::bad_alloc exception.

Step 3: Copy (or Move) Elements

What happens: All elements from the old memory block are copied (or moved, if possible, for efficiency) to the new memory block.
Key indicator: A loop that transfers elements from the old buffer to the new one.

Step 4: Deallocate Old Memory

What happens: The original, smaller block of memory is released back to the operating system.
Key indicator: The vector's internal pointer is updated to point to the new memory block, and the old pointer is deleted.

Step 5: Add the New Element

What happens: The new element that triggered the reallocation is finally added to the end of the new memory block.
Key indicator: The vector's size is incremented.

Topic: Internals: Memory Management

📝 Worked Examples

Example: Reading Unknown Number of Scores into a Vector

Problem: Write a C++ function that reads integer scores from standard input until a non-integer is entered, then returns the average score.

Solution:

#include <iostream>
#include <vector>
#include <numeric> // For std::accumulate

double calculateAverage() {
    std::vector<int> scores;
    int score;

    std::cout << "Enter scores (enter a non-number to finish):\n";

    // Step 1: Read scores into the vector
    while (std::cin >> score) {
        scores.push_back(score); // Vector grows automatically
    }

    // Step 2: Handle the case of no scores entered
    if (scores.empty()) {
        return 0.0;
    }

    // Step 3: Calculate the sum of the scores
    double sum = std::accumulate(scores.begin(), scores.end(), 0.0);

    // Step 4: Calculate and return the average
    return sum / scores.size();
}

int main() {
    double average = calculateAverage();
    std::cout << "Average score: " << average << std::endl;
    return 0;
}

Reasoning: A std::vector is ideal here because the number of scores is not known beforehand. push_back handles memory management automatically as each new score is entered. std::accumulate is a safe and efficient way to sum elements in a range.

⚠️ Common pitfall: Using a C-style array for this problem would be difficult and unsafe. You would have to pre-allocate a large array and risk either wasting space or overflowing the array if the user enters too many scores.

Topic: Practical Application

Example: Using an Array for a Frequency Counter

Problem: Write a function that counts the frequency of lowercase letters ('a'-'z') in a given std::string.