16.10 — std::vector resizing and capacity

In this lesson, you'll learn about std::vector's dynamic memory management, including the difference between size and capacity, how to resize vectors efficiently, and how to optimize performance by managing memory allocation strategically.

Size vs capacity

std::vector maintains two important properties that are often confused:

• Size: The number of elements currently stored in the vector
• Capacity: The number of elements the vector can hold without allocating new memory

Understanding this distinction is crucial for writing efficient code.

Visualizing size and capacity

#include <vector>
#include <iostream>

int main()
{
    std::vector<int> numbers;
    
    std::cout << "Initial state:" << std::endl;
    std::cout << "Size: " << numbers.size() << ", Capacity: " << numbers.capacity() << std::endl;
    
    // Add elements one by one
    for (int i = 1; i <= 10; ++i)
    {
        numbers.push_back(i * 10);
        std::cout << "Added " << (i * 10) << " - Size: " << numbers.size() 
                  << ", Capacity: " << numbers.capacity() << std::endl;
    }
    
    return 0;
}

Output (example - actual capacity growth may vary):

Initial state:
Size: 0, Capacity: 0
Added 10 - Size: 1, Capacity: 1
Added 20 - Size: 2, Capacity: 2
Added 30 - Size: 3, Capacity: 4
Added 40 - Size: 4, Capacity: 4
Added 50 - Size: 5, Capacity: 8
Added 60 - Size: 6, Capacity: 8
Added 70 - Size: 7, Capacity: 8
Added 80 - Size: 8, Capacity: 8
Added 90 - Size: 9, Capacity: 16
Added 100 - Size: 10, Capacity: 16

Notice how capacity grows in chunks (typically doubling) to avoid frequent reallocations.

Memory reallocation strategy

When a vector needs more space than its current capacity, it:

1. Allocates a new, larger block of memory (usually 2x the current capacity)
2. Copies all existing elements to the new memory
3. Destroys elements in the old memory
4. Deallocates the old memory

This process is expensive, so vectors try to minimize it by allocating extra space.

Demonstrating reallocation

#include <vector>
#include <iostream>

int main()
{
    std::vector<int> numbers;
    void* previousCapacityAddress = nullptr;
    
    std::cout << "Tracking memory reallocations:" << std::endl;
    
    for (int i = 0; i < 20; ++i)
    {
        numbers.push_back(i);
        
        // Check if memory location changed (indicating reallocation)
        void* currentAddress = numbers.data();
        if (currentAddress != previousCapacityAddress)
        {
            std::cout << "Reallocation at size " << numbers.size() 
                      << ", new capacity: " << numbers.capacity() << std::endl;
            previousCapacityAddress = currentAddress;
        }
    }
    
    std::cout << "Final size: " << numbers.size() 
              << ", capacity: " << numbers.capacity() << std::endl;
    
    return 0;
}

Output (example):

Tracking memory reallocations:
Reallocation at size 1, new capacity: 1
Reallocation at size 2, new capacity: 2
Reallocation at size 3, new capacity: 4
Reallocation at size 5, new capacity: 8
Reallocation at size 9, new capacity: 16
Final size: 20, capacity: 16

Resizing operations

resize() function

The resize() function changes the vector's size:

#include <vector>
#include <iostream>

int main()
{
    std::vector<int> numbers = {1, 2, 3, 4, 5};
    
    std::cout << "Original: ";
    for (int num : numbers) std::cout << num << " ";
    std::cout << " (size: " << numbers.size() << ")" << std::endl;
    
    // Resize to larger size - new elements are default-initialized (0 for int)
    numbers.resize(8);
    std::cout << "After resize(8): ";
    for (int num : numbers) std::cout << num << " ";
    std::cout << " (size: " << numbers.size() << ")" << std::endl;
    
    // Resize to larger size with specific value
    numbers.resize(10, 99);
    std::cout << "After resize(10, 99): ";
    for (int num : numbers) std::cout << num << " ";
    std::cout << " (size: " << numbers.size() << ")" << std::endl;
    
    // Resize to smaller size - elements are removed
    numbers.resize(6);
    std::cout << "After resize(6): ";
    for (int num : numbers) std::cout << num << " ";
    std::cout << " (size: " << numbers.size() << ")" << std::endl;
    
    return 0;
}

Output:

Original: 1 2 3 4 5  (size: 5)
After resize(8): 1 2 3 4 5 0 0 0  (size: 8)
After resize(10, 99): 1 2 3 4 5 0 0 0 99 99  (size: 10)
After resize(6): 1 2 3 4 5 0  (size: 6)

reserve() function

The reserve() function increases capacity without changing size:

#include <vector>
#include <iostream>

int main()
{
    std::vector<int> numbers;
    
    std::cout << "Initial - Size: " << numbers.size() 
              << ", Capacity: " << numbers.capacity() << std::endl;
    
    // Reserve space for 100 elements
    numbers.reserve(100);
    std::cout << "After reserve(100) - Size: " << numbers.size() 
              << ", Capacity: " << numbers.capacity() << std::endl;
    
    // Add some elements - no reallocation needed
    for (int i = 1; i <= 10; ++i)
    {
        numbers.push_back(i);
    }
    
    std::cout << "After adding 10 elements - Size: " << numbers.size() 
              << ", Capacity: " << numbers.capacity() << std::endl;
    
    // Cannot reserve less than current capacity
    numbers.reserve(5); // This has no effect
    std::cout << "After reserve(5) - Size: " << numbers.size() 
              << ", Capacity: " << numbers.capacity() << std::endl;
    
    return 0;
}

Output:

Initial - Size: 0, Capacity: 0
After reserve(100) - Size: 0, Capacity: 100
After adding 10 elements - Size: 10, Capacity: 100
After reserve(5) - Size: 0, Capacity: 100

Performance optimization strategies

Strategy 1: Pre-allocate with reserve()

#include <vector>
#include <iostream>
#include <chrono>

void withoutReserve()
{
    auto start = std::chrono::high_resolution_clock::now();
    
    std::vector<int> numbers;
    for (int i = 0; i < 1000000; ++i)
    {
        numbers.push_back(i);
    }
    
    auto end = std::chrono::high_resolution_clock::now();
    auto duration = std::chrono::duration_cast<std::chrono::microseconds>(end - start);
    
    std::cout << "Without reserve: " << duration.count() << " microseconds" << std::endl;
}

void withReserve()
{
    auto start = std::chrono::high_resolution_clock::now();
    
    std::vector<int> numbers;
    numbers.reserve(1000000); // Pre-allocate space
    for (int i = 0; i < 1000000; ++i)
    {
        numbers.push_back(i);
    }
    
    auto end = std::chrono::high_resolution_clock::now();
    auto duration = std::chrono::duration_cast<std::chrono::microseconds>(end - start);
    
    std::cout << "With reserve: " << duration.count() << " microseconds" << std::endl;
}

int main()
{
    std::cout << "Performance comparison:" << std::endl;
    withoutReserve();
    withReserve();
    
    return 0;
}

Output (example):

Performance comparison:
Without reserve: 45231 microseconds
With reserve: 12456 microseconds

Strategy 2: Use appropriate constructor

#include <vector>
#include <iostream>

int main()
{
    // ✅ Good: Size known in advance
    std::vector<double> scores;
    scores.reserve(1000); // If you know you'll have ~1000 scores
    
    // ✅ Even better: Use constructor if all elements are the same
    std::vector<double> zeros(1000, 0.0); // 1000 zeros
    
    // ✅ Best: Use initializer list if you know the values
    std::vector<std::string> days = {"Mon", "Tue", "Wed", "Thu", "Fri", "Sat", "Sun"};
    
    std::cout << "Scores capacity: " << scores.capacity() << std::endl;
    std::cout << "Zeros size: " << zeros.size() << std::endl;
    std::cout << "Days size: " << days.size() << std::endl;
    
    return 0;
}

Output:

Scores capacity: 1000
Zeros size: 1000
Days size: 7

Shrinking operations

shrink_to_fit() function

After removing many elements, you might want to reduce the capacity:

#include <vector>
#include <iostream>

int main()
{
    // Create a large vector
    std::vector<int> numbers(1000, 42);
    std::cout << "Initial - Size: " << numbers.size() 
              << ", Capacity: " << numbers.capacity() << std::endl;
    
    // Remove most elements
    numbers.resize(10);
    std::cout << "After resize(10) - Size: " << numbers.size() 
              << ", Capacity: " << numbers.capacity() << std::endl;
    
    // Shrink capacity to match size
    numbers.shrink_to_fit();
    std::cout << "After shrink_to_fit() - Size: " << numbers.size() 
              << ", Capacity: " << numbers.capacity() << std::endl;
    
    return 0;
}

Output:

Initial - Size: 1000, Capacity: 1000
After resize(10) - Size: 10, Capacity: 1000
After shrink_to_fit() - Size: 10, Capacity: 10

Note: shrink_to_fit() is a request, not a guarantee. The implementation may choose not to shrink.

clear() vs shrink_to_fit()

#include <vector>
#include <iostream>

int main()
{
    std::vector<int> numbers = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10};
    numbers.reserve(100); // Ensure large capacity
    
    std::cout << "Initial - Size: " << numbers.size() 
              << ", Capacity: " << numbers.capacity() << std::endl;
    
    // clear() removes elements but keeps capacity
    numbers.clear();
    std::cout << "After clear() - Size: " << numbers.size() 
              << ", Capacity: " << numbers.capacity() << std::endl;
    
    // To truly free memory, you can use swap trick or shrink_to_fit
    std::vector<int>().swap(numbers); // Swap with empty vector
    std::cout << "After swap trick - Size: " << numbers.size() 
              << ", Capacity: " << numbers.capacity() << std::endl;
    
    return 0;
}

Output:

Initial - Size: 10, Capacity: 100
After clear() - Size: 0, Capacity: 100
After swap trick - Size: 0, Capacity: 0

Practical examples

Example 1: Dynamic array for user input

#include <vector>
#include <iostream>
#include <string>

class DynamicArray
{
private:
    std::vector<int> data;
    
public:
    void addValue(int value)
    {
        data.push_back(value);
        
        // Show capacity changes
        static std::size_t lastCapacity = 0;
        if (data.capacity() != lastCapacity)
        {
            std::cout << "Capacity changed to: " << data.capacity() 
                      << " (size: " << data.size() << ")" << std::endl;
            lastCapacity = data.capacity();
        }
    }
    
    void optimizeForSize(std::size_t expectedSize)
    {
        std::cout << "Optimizing for " << expectedSize << " elements" << std::endl;
        data.reserve(expectedSize);
    }
    
    void removeAllNegatives()
    {
        auto oldSize = data.size();
        data.erase(std::remove_if(data.begin(), data.end(), 
                                 [](int x) { return x < 0; }), 
                  data.end());
        
        if (data.size() < oldSize / 2) // If we removed more than half
        {
            std::cout << "Shrinking after removing " << (oldSize - data.size()) 
                      << " elements" << std::endl;
            data.shrink_to_fit();
        }
    }
    
    void displayInfo() const
    {
        std::cout << "Size: " << data.size() 
                  << ", Capacity: " << data.capacity() << std::endl;
        std::cout << "Elements: ";
        for (int value : data)
        {
            std::cout << value << " ";
        }
        std::cout << std::endl;
    }
};

int main()
{
    DynamicArray arr;
    
    // Add elements without optimization
    std::cout << "Adding elements without optimization:" << std::endl;
    for (int i = 1; i <= 10; ++i)
    {
        arr.addValue(i);
    }
    arr.displayInfo();
    
    // Optimize for more elements
    arr.optimizeForSize(100);
    arr.displayInfo();
    
    // Add some negative numbers
    arr.addValue(-5);
    arr.addValue(-10);
    arr.addValue(15);
    arr.displayInfo();
    
    // Remove negatives
    arr.removeAllNegatives();
    arr.displayInfo();
    
    return 0;
}

Example 2: Buffer management

#include <vector>
#include <iostream>

class CircularBuffer
{
private:
    std::vector<int> buffer;
    std::size_t writePos;
    std::size_t readPos;
    std::size_t count;
    
public:
    CircularBuffer(std::size_t capacity) : writePos(0), readPos(0), count(0)
    {
        buffer.resize(capacity); // Pre-allocate fixed size
        std::cout << "Created buffer with capacity: " << buffer.capacity() << std::endl;
    }
    
    bool write(int value)
    {
        if (count >= buffer.size())
        {
            return false; // Buffer full
        }
        
        buffer[writePos] = value;
        writePos = (writePos + 1) % buffer.size();
        ++count;
        return true;
    }
    
    bool read(int& value)
    {
        if (count == 0)
        {
            return false; // Buffer empty
        }
        
        value = buffer[readPos];
        readPos = (readPos + 1) % buffer.size();
        --count;
        return true;
    }
    
    std::size_t size() const { return count; }
    std::size_t capacity() const { return buffer.size(); }
    
    void displayStatus() const
    {
        std::cout << "Buffer status - Used: " << count 
                  << "/" << buffer.size() << std::endl;
    }
};

int main()
{
    CircularBuffer buffer(5);
    
    // Fill buffer
    for (int i = 1; i <= 7; ++i)
    {
        if (buffer.write(i * 10))
        {
            std::cout << "Wrote: " << (i * 10) << std::endl;
        }
        else
        {
            std::cout << "Buffer full, couldn't write: " << (i * 10) << std::endl;
        }
    }
    
    buffer.displayStatus();
    
    // Read some values
    int value;
    for (int i = 0; i < 3; ++i)
    {
        if (buffer.read(value))
        {
            std::cout << "Read: " << value << std::endl;
        }
    }
    
    buffer.displayStatus();
    
    return 0;
}

Best practices

When to use reserve()

// ✅ Good: Known approximate final size
std::vector<std::string> readFile(const std::string& filename)
{
    std::vector<std::string> lines;
    lines.reserve(1000); // Estimate for typical file
    
    // Read file lines...
    
    return lines;
}

// ✅ Good: Loop with known iteration count
std::vector<int> generateSequence(int count)
{
    std::vector<int> result;
    result.reserve(count); // Exact size known
    
    for (int i = 0; i < count; ++i)
    {
        result.push_back(i * i);
    }
    
    return result;
}

When to use resize()

// ✅ Good: Need specific size with default values
std::vector<double> initializeMatrix(int rows, int cols)
{
    std::vector<double> matrix;
    matrix.resize(rows * cols, 0.0); // Initialize all to 0.0
    
    return matrix;
}

// ✅ Good: Adjusting vector size based on user input
void processUserData(std::vector<int>& data, std::size_t requiredSize)
{
    if (data.size() < requiredSize)
    {
        data.resize(requiredSize, -1); // Fill new elements with -1
    }
    else if (data.size() > requiredSize)
    {
        data.resize(requiredSize); // Truncate excess elements
    }
}

When to use shrink_to_fit()

// ✅ Good: After significant size reduction
void cleanup(std::vector<std::string>& cache)
{
    // Remove expired entries
    cache.erase(
        std::remove_if(cache.begin(), cache.end(), isExpired),
        cache.end()
    );
    
    // If we removed more than 75% of entries, shrink
    if (cache.capacity() > cache.size() * 4)
    {
        cache.shrink_to_fit();
    }
}

Summary

Understanding std::vector's memory management is crucial for writing efficient C++ programs:

Key concepts:

• Size: Current number of elements
• Capacity: Total space available without reallocation
• Reallocation: Expensive operation that copies all elements to new memory

Functions for memory management:

• reserve(n): Increase capacity to at least n (doesn't change size)
• resize(n): Change size to n (may change capacity)
• shrink_to_fit(): Request to reduce capacity to match size
• clear(): Remove all elements (doesn't change capacity)

Performance tips:

• Use reserve() when you know the approximate final size
• Use resize() when you need a specific size with default values
• Consider shrink_to_fit() after significant size reductions
• Pre-allocate using constructors when possible

In the next lesson, you'll learn about using std::vector as a stack data structure.

Quiz

1. What's the difference between size() and capacity() in std::vector?
2. When does std::vector reallocate memory and why is this expensive?
3. What's the difference between reserve() and resize()?
4. When should you use shrink_to_fit()?
5. Why might reserve() improve performance when adding many elements?

Practice exercises

Try these exercises to practice vector resizing and capacity management:

1. Performance analyzer: Write a program that compares the performance of adding 100,000 elements to a vector with and without using reserve(). Measure and display the time difference.

2. Memory-efficient cache: Implement a cache class that automatically shrinks its capacity when the stored data drops below 25% of capacity, but grows capacity intelligently when needed.

3. Dynamic matrix: Create a class that represents a 2D matrix using a 1D vector. Implement functions to resize the matrix and optimize memory usage based on the actual data stored.

4. Buffer optimizer: Write a function that takes a vector and optimizes its memory usage based on usage patterns - shrink if mostly empty, or reserve space if frequently growing.