What are Dynamic Arrays?

Dynamic arrays automatically manage memory and can resize themselves as needed. In C++, the primary dynamic array is the vector:

Basic Vector Operations

Here are the fundamental operations you'll use with vectors:

#include <vector>
#include <iostream>

int main() {
    // Declaration and initialization
    vector<int> v;                    // Empty vector
    vector<int> v2(5);               // 5 elements, all 0
    vector<int> v3(5, 10);           // 5 elements, all 10
    vector<int> v4 = {1, 2, 3, 4, 5}; // Initialize with values
    
    // Adding elements
    v.push_back(10);  // Add to end
    v.push_back(20);
    v.push_back(30);
    
    // Accessing elements
    cout << "First element: " << v[0] << endl;        // Direct access
    cout << "First element: " << v.front() << endl;   // First element
    cout << "Last element: " << v.back() << endl;     // Last element
    cout << "Safe access: " << v.at(1) << endl;       // Bounds checking
    
    // Size and capacity
    cout << "Size: " << v.size() << endl;
    cout << "Capacity: " << v.capacity() << endl;
    cout << "Empty? " << v.empty() << endl;
    
    // Removing elements
    v.pop_back();     // Remove last element
    
    return 0;
}
                    

Iterating Through Vectors

There are several ways to iterate through vector elements:

#include <vector>

int main() {
    vector<int> numbers = {10, 20, 30, 40, 50};
    
    // Method 1: Range-based for loop (C++11+)
    cout << "Range-based loop: ";
    for (int num : numbers) {
        cout << num << " ";
    }
    cout << endl;
    
    // Method 2: Traditional for loop with index
    cout << "Index-based loop: ";
    for (size_t i = 0; i < numbers.size(); i++) {
        cout << numbers[i] << " ";
    }
    cout << endl;
    
    // Method 3: Iterator-based loop
    cout << "Iterator-based loop: ";
    for (auto it = numbers.begin(); it != numbers.end(); ++it) {
        cout << *it << " ";
    }
    cout << endl;
    
    // Method 4: Reverse iteration
    cout << "Reverse loop: ";
    for (auto it = numbers.rbegin(); it != numbers.rend(); ++it) {
        cout << *it << " ";
    }
    cout << endl;
    
    return 0;
}
                    

2D Vectors (Matrices)

Vectors can be nested to create 2D arrays or matrices:

#include <vector>

int main() {
    // Create a 3x4 matrix
    int rows = 3, cols = 4;
    vector<vector<int>> matrix(rows, vector<int>(cols));
    
    // Initialize with values
    vector<vector<int>> matrix2 = {
        {1, 2, 3},
        {4, 5, 6},
        {7, 8, 9}
    };
    
    // Fill with values
    for (int i = 0; i < rows; i++) {
        for (int j = 0; j < cols; j++) {
            matrix[i][j] = i * cols + j + 1;
        }
    }
    
    // Print matrix
    for (const auto& row : matrix) {
        for (int val : row) {
            cout << val << " ";
        }
        cout << endl;
    }
    
    // Jagged arrays (different row sizes)
    vector<vector<int>> jagged = {
        {1, 2},
        {3, 4, 5, 6},
        {7}
    };
    
    return 0;
}
                    

Advanced Vector Operations

Vectors support many advanced operations for manipulation:

#include <vector>
#include <algorithm>

int main() {
    vector<int> v = {5, 2, 8, 1, 9, 3};
    
    // Insert elements
    v.insert(v.begin() + 2, 100);      // Insert 100 at position 2
    v.insert(v.end(), {6, 7});         // Insert multiple at end
    
    // Erase elements
    v.erase(v.begin() + 1);            // Erase element at position 1
    v.erase(v.begin() + 2, v.begin() + 4); // Erase range
    
    // Resize operations
    v.resize(10);          // Resize to 10 elements (fills with 0)
    v.resize(5);           // Shrink to 5 elements
    v.reserve(20);         // Reserve capacity for 20 elements
    
    // Clear and swap
    vector<int> v2 = {10, 20, 30};
    v.swap(v2);            // Swap contents of v and v2
    v.clear();             // Remove all elements
    
    // Using algorithms
    vector<int> nums = {5, 2, 8, 1, 9, 3};
    
    sort(nums.begin(), nums.end());                    // Sort ascending
    reverse(nums.begin(), nums.end());                 // Reverse order
    
    auto it = find(nums.begin(), nums.end(), 8);       // Find element
    if (it != nums.end()) {
        cout << "Found 8 at position: " << it - nums.begin() << endl;
    }
    
    return 0;
}
                    

Memory Management

Understanding how vectors manage memory helps with performance:

#include <vector>

int main() {
    vector<int> v;
    
    cout << "Initial - Size: " << v.size() 
         << ", Capacity: " << v.capacity() << endl;
    
    // Adding elements shows capacity growth
    for (int i = 1; i <= 10; i++) {
        v.push_back(i);
        cout << "After adding " << i 
             << " - Size: " << v.size() 
             << ", Capacity: " << v.capacity() << endl;
    }
    
    // Reserve space to avoid reallocations
    vector<int> v2;
    v2.reserve(1000);  // Reserve space for 1000 elements
    
    // Shrink to fit - reduce capacity to size
    v.shrink_to_fit();
    
    return 0;
}
                    

Common Patterns

Some frequently used patterns in competitive programming:

Reading Input into Vector

// Read n integers into vector
int n;
cin >> n;
vector<int> arr(n);
for (int i = 0; i < n; i++) {
    cin >> arr[i];
}

// Alternative: using istream_iterator
vector<int> arr2(istream_iterator<int>(cin), 
                 istream_iterator<int>());
                    

Prefix Sums

vector<int> computePrefixSums(const vector<int>& arr) {
    vector<int> prefix(arr.size() + 1, 0);
    for (int i = 0; i < arr.size(); i++) {
        prefix[i + 1] = prefix[i] + arr[i];
    }
    return prefix;
}
                    

Sliding Window Maximum

vector<int> slidingWindowMax(vector<int>& nums, int k) {
    vector<int> result;
    deque<int> dq; // Store indices
    
    for (int i = 0; i < nums.size(); i++) {
        // Remove elements outside window
        while (!dq.empty() && dq.front() <= i - k) {
            dq.pop_front();
        }
        
        // Maintain decreasing order
        while (!dq.empty() && nums[dq.back()] <= nums[i]) {
            dq.pop_back();
        }
        
        dq.push_back(i);
        
        if (i >= k - 1) {
            result.push_back(nums[dq.front()]);
        }
    }
    
    return result;
}
                    

Performance Tips