Dynamic Arrays with `std::vector`

1. From Fixed Arrays to Dynamic Vectors

In C, and in our early C++ lessons, we've used C-style arrays. Their biggest limitation is their fixed size, which must be known at compile time. This is often impractical. For example, in your data analysis work, you rarely know in advance how many data points you'll need to process.

std::vector solves this problem by providing a "dynamic array" that can grow or shrink as needed during your program's execution. It handles all the complex memory management for you, making your code safer and simpler.

Let's watch a video that introduces this concept, contrasting the limitations of traditional arrays with the flexibility of std::vector.

2. Basic std::vector Operations

Using a std::vector is straightforward. You first need to include the <vector> header. Then, you can declare a vector of a specific type.

Here are the essential operations you'll use most often:

• Declaration: std::vector<int> my_numbers;
• Adding elements: my_numbers.push_back(10); (adds an element to the end)
• Getting the size: my_numbers.size(); (returns the number of elements)
• Accessing elements: my_numbers[0]; or my_numbers.at(0);

A key difference between [] and .at() is that .at() performs bounds checking. If you try to access an index that doesn't exist, .at() will throw an exception, which can help you catch bugs. The [] operator does not perform this check, so accessing an invalid index leads to undefined behavior, which is much harder to debug.

This next segment of the video demonstrates these core operations in a live-coding example.

To provide a quick reference for these common operations, you can review the following article.

3. Under the Hood: Size vs. Capacity

Now for the part that I think you'll find particularly interesting: how does a std::vector actually work? The magic lies in how it manages memory on the heap.

A std::vector object itself is small and lives on the stack. It contains a few pieces of information, most importantly:

1. A pointer to a large block of contiguous memory on the heap, where the elements are actually stored.
2. The size: the number of elements currently in the vector.
3. The capacity: the number of elements the allocated heap memory can hold before it needs to be resized.

When you push_back an element and the size equals the capacity, the vector performs a reallocation:

1. It allocates a new, larger block of memory on the heap (typically doubling the capacity).
2. It copies or moves all the elements from the old memory block to the new one.
3. It deallocates the old memory block.
4. Finally, it adds the new element.

This is why size() can be different from capacity().

Understanding this process is crucial for writing efficient C++ code. Let's return to our video, which provides an excellent deep dive into this mechanism.

4. Optimizing Performance with reserve()

While automatic reallocation is convenient, it can be a performance bottleneck if it happens frequently, as each reallocation involves memory allocation and copying all elements.

If you have a reasonable estimate of how many elements you will store, you can give the vector a hint using the reserve() method. This tells the vector to allocate enough capacity upfront, preventing reallocations as you add elements up to that capacity.

std::vector<int> numbers;
numbers.reserve(1000); // Allocates capacity for 1000 ints right away

for (int i = 0; i < 1000; ++i) {
    numbers.push_back(i); // No reallocations will occur in this loop
}

Let's watch a short video that explains this important optimization.

The advice on passing vectors by const reference is a critical C++ idiom. It directly builds on what we've learned about references and efficiency. Copying a vector with thousands of elements just to pass it to a function is very wasteful.

5. Practical Exercise

Time to apply what you've learned.

1. Create a new C++ file.
2. Write a program that prompts the user to enter a series of integers.
3. Use a while loop and std::cin to read integers into a std::vector<int>. The loop should terminate when the user enters a non-integer value (e.g., the letter 'q').
4. Inside the loop, print the vector's current size() and capacity() after each number is added. This will let you see the reallocation in action.
5. After the loop terminates, print all the numbers stored in the vector.

Example Interaction:

Enter numbers (q to quit):
10
Size: 1, Capacity: 1
20
Size: 2, Capacity: 2
30
Size: 3, Capacity: 4
40
Size: 4, Capacity: 4
50
Size: 5, Capacity: 8
q

You entered: 10 20 30 40 50

(Note: Your exact capacity values may differ depending on your compiler's STL implementation, but you should see them grow exponentially.)

Bonus Challenge: Modify your program to reserve(10) on the vector before the loop starts. Run it again and see how the capacity changes (or doesn't change) as you enter the first 10 numbers.

Conclusion

In this lesson, you've taken your first step into the C++ Standard Template Library by mastering std::vector. It is a powerful and essential tool that you will use constantly in your C++ journey.

Key Takeaways:

• std::vector is a dynamic array that automatically manages its memory on the heap.
• The most common operations are push_back(), size(), at(), and the [] operator.
• A vector's size is the number of elements it contains, while its capacity is the total space it has allocated. When size exceeds capacity, a reallocation occurs.
• Reallocation can be costly. You can use reserve() to pre-allocate capacity and improve performance if you know the approximate number of elements you'll need.
• To avoid expensive copies, pass vectors to functions by const reference (const std::vector<T>&) when you only need to read their contents.

Next Up

We used a traditional for loop with an index to iterate over our vector today. In the next lesson, we'll explore a more modern, safer, and often more readable way to iterate over containers like std::vector: the range-based for loop.