16.x — Chapter 16 summary and quiz

Congratulations! You've completed Chapter 16 on Dynamic Arrays and std::vector. This chapter covered one of the most important and frequently used containers in C++. Let's review what you've learned and test your understanding.

Chapter summary

Core concepts learned

1. Introduction to containers and arrays (16.1)

• Containers: Data structures that hold collections of elements
• C-style arrays: Fixed-size, minimal overhead, but limited functionality
• Modern containers: Dynamic sizing, bounds checking, rich functionality
• Memory layout: Contiguous storage for performance efficiency

2. std::vector constructors (16.2)

• Default constructor: Creates empty vector
• Fill constructor: Creates vector with specified size and values
• Initializer list constructor: Creates vector from list of values
• Copy constructor: Creates independent copy of another vector
• Range constructor: Creates vector from iterator range

3. Signed/unsigned challenges (16.3)

• size() returns unsigned type (std::size_t)
• Mixed comparisons create compiler warnings and potential bugs
• Unsigned underflow in reverse iteration causes infinite loops
• Solutions: Cast to signed, use range-based loops, or be careful with unsigned arithmetic

4. Passing vectors to functions (16.4)

• By value: Creates copy, expensive for large vectors
• By const reference: Read-only access, efficient
• By non-const reference: Allows modification of original
• By pointer: Rarely needed, allows null values
• By move: Transfers ownership, efficient for large temporary objects

5. Returning vectors and move semantics (16.5)

• Return Value Optimization (RVO): Compiler eliminates unnecessary copies
• Move semantics: Transfer ownership instead of copying
• std::move: Explicitly request move operation
• Best practice: Return by value and trust compiler optimizations

6. Arrays and loops (16.6)

• Index-based loops: Traditional approach with manual index management
• Range-based loops: Modern, cleaner syntax for simple iteration
• Iterator-based loops: Flexible navigation through containers
• Performance: All approaches have similar performance when optimized

7. Sign challenge solutions (16.7)

• Safe reverse iteration: Use signed integers or careful unsigned arithmetic
• Safe element removal: Iterate backwards or use iterators properly
• Bounds checking: Validate indices before accessing elements
• Best practices: Choose appropriate loop type and handle edge cases

8. Range-based for loops (16.8)

• Syntax: for (declaration : container)
• By value: Creates copies, good for small types
• By const reference: Read-only access, avoids copying
• By reference: Allows modification of original elements
• Limitations: No index access, can't skip elements, can't iterate backwards

9. Array indexing with enumerators (16.9)

• Magic numbers problem: Hard-coded indices are error-prone
• Enumerators solution: Named constants for array indices
• Self-documenting code: Clear intent and meaning
• Maintenance benefits: Easy to reorder or add new fields

10. Vector resizing and capacity (16.10)

• Size vs capacity: Current elements vs allocated space
• Reallocation strategy: Grow capacity exponentially to minimize reallocations
• resize(): Change the number of elements
• reserve(): Pre-allocate capacity for better performance
• shrink_to_fit(): Reduce capacity to match size

11. Vector as stack (16.11)

• LIFO behavior: Last In, First Out operations
• Stack operations: push_back(), pop_back(), back(), empty()
• Applications: Expression parsing, undo functionality, call stack simulation
• Performance: O(1) operations with excellent cache locality

12. std::vector specialization (16.12)

• Space efficiency: Uses 1 bit per bool instead of 1 byte
• Proxy references: Returns proxy objects instead of real references
• Special functions: flip() for bit manipulation
• Trade-offs: Memory efficiency vs reference semantics
• Alternatives: std::vector, std::bitset for different needs

Key takeaways

When to use std::vector

✅ Use std::vector when:

• You need a dynamic array that can grow and shrink
• You want good general-purpose performance
• You need frequent access to elements by index
• You're adding/removing elements primarily at the end
• You want standard container compatibility

Best practices summary

Memory management

// Pre-allocate when you know the size
std::vector<int> numbers;
numbers.reserve(expectedSize);

// Use appropriate constructor
std::vector<int> zeros(100, 0);        // 100 zeros
std::vector<int> values = {1, 2, 3};   // Known values

Function parameters

// Read-only access
void process(const std::vector<int>& data);

// Modify original
void modify(std::vector<int>& data);

// Need a copy for local work
std::vector<int> process(std::vector<int> data);

Iteration patterns

// Simple iteration
for (const auto& item : container) { /* use item */ }

// Need index
for (int i = 0; i < static_cast<int>(container.size()); ++i) { /* use i */ }

// Complex navigation
for (auto it = container.begin(); it != container.end(); ++it) { /* use *it */ }

Error prevention

// Always check before accessing
if (!vec.empty()) {
    auto first = vec.front();
    auto last = vec.back();
}

// Validate indices
if (index >= 0 && static_cast<size_t>(index) < vec.size()) {
    auto value = vec[index];
}

Performance characteristics

Common pitfalls to avoid

1. Signed/unsigned mixing

// ❌ Dangerous
for (int i = vec.size() - 1; i >= 0; --i) // Unsigned underflow!

// ✅ Safe
for (int i = static_cast<int>(vec.size()) - 1; i >= 0; --i)

2. Invalidated iterators

// ❌ Dangerous
for (auto it = vec.begin(); it != vec.end(); ++it) {
    if (*it == target) {
        vec.erase(it); // Invalidates iterator!
    }
}

// ✅ Safe
for (auto it = vec.begin(); it != vec.end();) {
    if (*it == target) {
        it = vec.erase(it); // Update iterator
    } else {
        ++it;
    }
}

3. Unnecessary copying

// ❌ Expensive
void processData(std::vector<LargeObject> data) // Copies entire vector

// ✅ Efficient
void processData(const std::vector<LargeObject>& data) // No copy

Chapter 16 comprehensive quiz

Test your understanding of std::vector and dynamic arrays:

Basic concepts (Questions 1-5)

1. What is the main difference between C-style arrays and std::vector? a) std::vector is faster b) C-style arrays use more memory c) std::vector can change size during runtime d) C-style arrays are more secure

2. What does std::vector::size() return? a) The number of bytes used by the vector b) The number of elements currently stored c) The maximum number of elements that can be stored d) The number of elements allocated in memory

3. Which constructor creates a vector with 5 elements, each initialized to 42? a) std::vector<int> v(5, 42); b) std::vector<int> v{5, 42}; c) std::vector<int> v[5] = {42}; d) std::vector<int> v = 5 * 42;

4. What happens when you call push_back() on a vector that is at capacity? a) The operation fails b) The oldest element is removed c) New memory is allocated and elements are copied d) The program crashes

5. Which range-based for loop declaration should you use to modify vector elements? a) for (auto item : vec) b) for (const auto& item : vec) c) for (auto& item : vec) d) for (auto* item : vec)

Advanced concepts (Questions 6-10)

6. Why is this loop dangerous?

   for (std::size_t i = vec.size() - 1; i >= 0; --i)
   

   a) It accesses elements out of bounds b) std::size_t is unsigned and will wrap around when decremented below 0 c) It's too slow d) It doesn't work with empty vectors only

7. What is the time complexity of inserting an element at the beginning of std::vector? a) O(1) b) O(log n) c) O(n) d) O(n²)

8. When should you use reserve() instead of resize()? a) When you want to add elements to the vector b) When you want to allocate memory without changing the size c) When you want to remove elements from the vector d) When you want to sort the vector

9. What is special about std::vector? a) It stores each bool in a separate byte b) It uses bit-level storage and returns proxy references c) It's faster than other vector types d) It can only store true values

10. Which is the most appropriate way to pass a large vector to a function for read-only access? a) void func(std::vector<int> v) b) void func(std::vector<int>& v) c) void func(const std::vector<int>& v) d) void func(std::vector<int>* v)

Problem solving (Questions 11-15)

11. How would you safely iterate backwards through a vector to remove elements? a) Use a range-based for loop b) Use iterators with std::reverse c) Use signed integer indices and decrement d) Use unsigned indices with special checking

12. What's the best way to create a vector of 1000 zeros for performance? a) std::vector<int> v; for(int i=0; i<1000; ++i) v.push_back(0); b) std::vector<int> v(1000, 0); c) std::vector<int> v = {0}; v.resize(1000); d) std::vector<int> v; v.reserve(1000); /* add zeros */

13. Which operation is NOT naturally supported by using std::vector as a stack? a) Adding an element to the top b) Removing an element from the top c) Looking at the top element d) Adding an element to the middle

14. How do you fix this compilation error?

    std::vector<bool> flags = {true, false};
    bool& ref = flags[0]; // Error!
    

    a) Use auto& ref = flags[0]; b) Use bool ref = flags[0]; c) Use std::vector<int> instead d) Use const bool& ref = flags[0];

15. What's the most memory-efficient way to store 10,000 boolean flags? a) std::vector<bool> b) std::vector<int> c) std::vector<char> d) bool array[10000]

Quiz answers

1. c) std::vector can change size during runtime
2. b) The number of elements currently stored
3. a) std::vector<int> v(5, 42);
4. c) New memory is allocated and elements are copied
5. c) for (auto& item : vec)
6. b) std::size_t is unsigned and will wrap around
7. c) O(n) - must shift all existing elements
8. b) When you want to allocate memory without changing the size
9. b) It uses bit-level storage and returns proxy references
10. c) void func(const std::vector<int>& v)
11. c) Use signed integer indices and decrement
12. b) std::vector<int> v(1000, 0);
13. d) Adding an element to the middle
14. b) Use bool ref = flags[0];
15. a) std::vector<bool>

What's next?

You now have a solid foundation in using std::vector, one of the most important containers in C++. In future chapters, you'll learn about:

• Other containers: std::array, std::deque, std::list, std::set, std::map
• Algorithms: std::sort, std::find, std::copy, and many others
• Iterators: More advanced iterator types and their usage
• Custom containers: How to create your own container classes

Recommended practice

Before moving on, make sure you can:

• Create and initialize vectors in different ways
• Safely iterate through vectors using different methods
• Pass vectors to functions appropriately
• Use vectors as stacks when needed
• Handle the signed/unsigned integer challenges
• Choose the right container for your needs

Keep practicing with std::vector - it's a container you'll use frequently throughout your C++ programming career!

Final exercises

Try these comprehensive exercises to solidify your understanding:

1. Vector statistics: Create a class that calculates and maintains statistics (min, max, average, median) for a vector of numbers, updating efficiently as elements are added or removed.

2. Generic stack: Implement a template stack class using std::vector that provides type safety and proper error handling for stack operations.

3. Dynamic 2D matrix: Create a Matrix class that uses std::vector internally to provide 2D array functionality with proper bounds checking and memory management.

4. Text processor: Build a text processing utility that uses vectors to store words, lines, and characters, implementing features like search, replace, and statistical analysis.

Congratulations on completing Chapter 16! You're now well-equipped to use std::vector effectively in your C++ programs.