Project 1: The Exception-Safe Vector
Build a simplified
std::vectorwith fanatical focus on the strong exception guarantee
Quick Reference
| Attribute | Value |
|---|---|
| Difficulty | Advanced |
| Time Estimate | 1-2 weeks |
| Language | C++17 |
| Prerequisites | C++ fundamentals, memory management, basic templates |
| Key Topics | RAII, exception guarantees, copy-and-swap, noexcept |
| Main Book | “Effective C++, 3rd Edition” by Scott Meyers |
| Coolness Level | Genuinely Clever |
| Portfolio Value | Resume Gold |
1. Learning Objectives
By completing this project, you will:
- Master the three exception guarantees: Explain the basic, strong, and nothrow guarantees and implement code that provides each
- Implement RAII correctly: Design classes where resource acquisition happens in constructors and release happens in destructors, with no possible leaks
- Apply the copy-and-swap idiom: Write assignment operators that provide strong exception safety using a classic C++ technique
- Use
noexceptcorrectly: Understand when and why to mark functionsnoexcept, and how the compiler uses this information - Handle
std::bad_alloc: Write code that recovers gracefully from memory allocation failures - Reason about exception safety: Analyze existing code for exception safety holes and design fixes
2. Theoretical Foundation
2.1 Core Concepts
The Three Exception Guarantees
Every function in C++ implicitly or explicitly provides one of three levels of exception safety:
┌─────────────────────────────────────────────────────────────────────────────┐
│ THE THREE EXCEPTION GUARANTEES │
├─────────────────────────────────────────────────────────────────────────────┤
│ │
│ ┌─────────────────────────────────────────────────────────────────────┐ │
│ │ NOTHROW GUARANTEE │ │
│ │ "I will never throw an exception" │ │
│ │ │ │
│ │ Examples: destructors, swap, move operations │ │
│ │ Marked: noexcept │ │
│ │ The strongest guarantee - operations always succeed │ │
│ └─────────────────────────────────────────────────────────────────────┘ │
│ ↑ │
│ │ (strongest) │
│ ┌─────────────────────────────────────────────────────────────────────┐ │
│ │ STRONG GUARANTEE │ │
│ │ "If I throw, the state is unchanged (rollback semantics)" │ │
│ │ │ │
│ │ Examples: vector::push_back, container copy constructors │ │
│ │ Implemented via: copy-and-swap, temporary objects │ │
│ │ Think: database transactions with ROLLBACK │ │
│ └─────────────────────────────────────────────────────────────────────┘ │
│ ↑ │
│ │ │
│ ┌─────────────────────────────────────────────────────────────────────┐ │
│ │ BASIC GUARANTEE │ │
│ │ "If I throw, no resources leak and invariants are preserved" │ │
│ │ │ │
│ │ Examples: many mutating operations │ │
│ │ The object is valid but in some unspecified state │ │
│ │ Think: the car works, but we don't know what gear it's in │ │
│ └─────────────────────────────────────────────────────────────────────┘ │
│ ↑ │
│ │ (weakest) │
│ ┌─────────────────────────────────────────────────────────────────────┐ │
│ │ NO GUARANTEE │ │
│ │ "If I throw, anything can happen" │ │
│ │ │ │
│ │ This is a BUG. Resources may leak, invariants may be broken. │ │
│ │ NEVER write code with no exception guarantee. │ │
│ └─────────────────────────────────────────────────────────────────────┘ │
│ │
└─────────────────────────────────────────────────────────────────────────────┘
RAII: Resource Acquisition Is Initialization
RAII is the C++ idiom where resource lifetime is tied to object lifetime:
// WITHOUT RAII - Manual resource management (dangerous)
void process_file_dangerous(const char* path) {
FILE* f = fopen(path, "r");
if (!f) return;
// What if this throws? Memory leak!
std::string data = read_all(f);
// What if this throws? Memory leak!
transform(data);
fclose(f); // Never reached if exception thrown
}
// WITH RAII - Automatic resource management (safe)
void process_file_safe(const char* path) {
std::ifstream file(path); // Resource acquired in constructor
if (!file) return;
// Even if these throw, ~ifstream() will run and close the file
std::string data = read_all(file);
transform(data);
} // Resource released in destructor - GUARANTEED
The Copy-and-Swap Idiom
The copy-and-swap idiom provides strong exception safety for assignment operators:
┌─────────────────────────────────────────────────────────────────────────────┐
│ THE COPY-AND-SWAP IDIOM │
├─────────────────────────────────────────────────────────────────────────────┤
│ │
│ Traditional Assignment: Copy-and-Swap Assignment: │
│ ┌───────────────────────┐ ┌───────────────────────────────────┐ │
│ │ 1. Free old resources │ │ 1. Copy construct parameter │ │
│ │ (can't undo!) │ │ (if this throws, self is safe) │ │
│ │ 2. Copy new resources │ │ 2. Swap (noexcept - can't fail) │ │
│ │ (if this throws, │ │ 3. Destructor cleans old data │ │
│ │ we're corrupted!) │ │ (when temp goes out of scope) │ │
│ └───────────────────────┘ └───────────────────────────────────┘ │
│ │
│ Problem: If step 2 throws, Benefit: If step 1 throws, │
│ old data is already gone. self is completely unchanged. │
│ Object is left in broken state. Strong exception guarantee! │
│ │
│ ┌─────────────────────────────────────────────────────────────────────┐ │
│ │ Visual Flow │ │
│ │ │ │
│ │ Before: After Copy: After Swap: After Destruction: │
│ │ ┌─────┐ ┌─────┐ ┌─────┐ ┌─────┐ ┌─────┐ ┌─────┐ │
│ │ │self │ │self │ │temp │ │self │ │temp │ │self │ │
│ │ │ A │ │ A │ │ B' │ │ B' │ │ A │ │ B' │ Success! │
│ │ └─────┘ └─────┘ └─────┘ └─────┘ └─────┘ └─────┘ │
│ │ ↑ unchanged ↑ swapped ↑ A destroyed │
│ │ │
│ │ If exception here: ──────────────────────────────────────────────▶ │
│ │ self still has A, temp destroyed, no harm done │
│ └─────────────────────────────────────────────────────────────────────┘ │
│ │
└─────────────────────────────────────────────────────────────────────────────┘
The noexcept Specifier
noexcept tells the compiler a function will not throw exceptions:
// Functions that MUST be noexcept:
~Vector() noexcept; // Destructors (implicitly noexcept)
void swap(Vector& other) noexcept; // Swap operations
Vector(Vector&& other) noexcept; // Move constructor
Vector& operator=(Vector&& other) noexcept; // Move assignment
// Why does noexcept matter?
// 1. Performance: compiler can optimize differently
// 2. Correctness: std::vector uses noexcept to choose between move and copy
// 3. Documentation: clearly states the function's contract
2.2 Why This Matters
Exception-safe code is the difference between production-quality and prototype-quality C++:
Without Exception Safety:
- Memory leaks under error conditions
- Corrupted data structures after partial failures
- Security vulnerabilities from inconsistent states
- Impossible to write reliable higher-level abstractions
With Exception Safety:
- Resources automatically cleaned up
- Operations are atomic (succeed completely or have no effect)
- Code can be safely composed into larger systems
- Enables writing generic code that works with any type
Real-World Impact:
- Financial systems: A half-completed trade is a disaster
- Databases: Partial writes corrupt data
- Games: Resource leaks accumulate and crash the game
- Embedded systems: No memory to leak, must be correct
2.3 Historical Context
The exception safety guarantees were formalized in the 1990s by Dave Abrahams during the standardization of the C++ Standard Library. The key insight was that exception safety is not about catching exceptions - it’s about maintaining invariants.
Key Milestones:
- 1994: Dave Abrahams formalizes the three guarantees
- 1998: C++98 standard library designed with exception safety
- 2003: Herb Sutter’s “Exceptional C++” popularizes the concepts
- 2011: C++11 adds
noexceptfor explicit specification - 2017: C++17 makes
noexceptpart of the type system
2.4 Common Misconceptions
Misconception 1: “Exception safety means catching all exceptions” Reality: Exception safety is about maintaining invariants and cleaning up resources, not about catching. Often the best thing to do is let exceptions propagate.
Misconception 2: “If I don’t throw exceptions, I don’t need exception safety”
Reality: Code you call might throw. new can throw std::bad_alloc. Any STL operation can throw.
Misconception 3: “Strong guarantee is always best” Reality: Strong guarantee has overhead. For some operations (like vector::insert in the middle), basic guarantee is acceptable and more efficient.
Misconception 4: “Move operations are always safe”
Reality: Move operations should be noexcept but aren’t always. If your move throws, std::vector will copy instead (slower but safe).
Misconception 5: “I can make any operation strongly exception-safe” Reality: Some operations (like swap of non-trivial objects) are fundamentally not strongly exception-safe unless the components are.
3. Project Specification
3.1 What You Will Build
A simplified but robust Vector<T> class template that:
- Dynamically manages memory for elements of type
T - Provides
push_backwith the strong exception guarantee - Uses RAII for all resource management
- Implements the copy-and-swap idiom for assignment
- Correctly uses
noexceptthroughout
3.2 Functional Requirements
- Construction & Destruction
- Default constructor creates an empty vector
- Copy constructor performs deep copy
- Move constructor transfers ownership (
noexcept) - Destructor releases all memory (
noexcept)
- Element Access
operator[]for unchecked accessat()for bounds-checked access (throwsstd::out_of_range)front()andback()for first/last element
- Capacity Management
size()returns current element countcapacity()returns current allocationempty()returns whether size is zeroreserve(n)ensures capacity for n elements (strong guarantee)
- Modification
push_back(value)adds element with strong exception guaranteepop_back()removes last element (noexcept)clear()removes all elements (noexcept)
- Assignment
- Copy assignment using copy-and-swap (strong guarantee)
- Move assignment transfers ownership (
noexcept)
- Utility
swap()member function (noexcept)- Non-member
swap()(noexcept)
3.3 Non-Functional Requirements
- Exception Safety: All operations must provide at least the basic guarantee;
push_backand assignment must provide the strong guarantee - Correctness: No memory leaks, no double-frees, no use-after-free
- Efficiency: Amortized O(1) for
push_back, 2x growth factor - Testability: Must be verifiable with allocation failure injection
3.4 Example Usage / Output
#include "Vector.hpp"
#include <iostream>
#include <string>
// A type with non-trivial copy that can throw
struct Widget {
int value;
Widget(int v) : value(v) {}
Widget(const Widget& other) : value(other.value) {
// Simulating a potentially throwing copy
if (value < 0) throw std::runtime_error("Negative widget");
}
};
int main() {
// Basic usage
Vector<int> v;
v.push_back(1);
v.push_back(2);
v.push_back(3);
std::cout << "Size: " << v.size() << "\n"; // Size: 3
std::cout << "Capacity: " << v.capacity() << "\n"; // Capacity: 4
std::cout << "First: " << v.front() << "\n"; // First: 1
std::cout << "Last: " << v.back() << "\n"; // Last: 3
// Demonstrating strong exception guarantee
Vector<Widget> widgets;
widgets.push_back(Widget(1));
widgets.push_back(Widget(2));
std::cout << "Widgets before: " << widgets.size() << "\n"; // 2
try {
// This will throw during copy construction
widgets.push_back(Widget(-1));
} catch (const std::runtime_error& e) {
std::cout << "Caught: " << e.what() << "\n";
}
// STRONG GUARANTEE: widgets unchanged!
std::cout << "Widgets after: " << widgets.size() << "\n"; // Still 2!
std::cout << "Widget[0]: " << widgets[0].value << "\n"; // Still 1
std::cout << "Widget[1]: " << widgets[1].value << "\n"; // Still 2
// Copy and assignment
Vector<int> copy = v; // Copy construction
Vector<int> moved = std::move(copy); // Move construction (noexcept)
v = moved; // Copy assignment (strong guarantee)
moved = std::move(v); // Move assignment (noexcept)
return 0;
}
Output:
Size: 3
Capacity: 4
First: 1
Last: 3
Widgets before: 2
Caught: Negative widget
Widgets after: 2
Widget[0]: 1
Widget[1]: 2
3.5 Real World Outcome
When complete, you’ll have a vector that survives allocation failures:
#include "Vector.hpp"
#include "AllocationTracker.hpp" // Your test utility
int main() {
AllocationTracker tracker; // Counts allocations
Vector<int> v;
// Fill vector with some data
for (int i = 0; i < 100; ++i) {
v.push_back(i);
}
std::cout << "Elements before test: " << v.size() << "\n";
std::cout << "Allocations so far: " << tracker.count() << "\n";
// Now force allocations to fail after a few more
tracker.set_failure_countdown(5);
try {
for (int i = 100; i < 1000; ++i) {
v.push_back(i); // Will eventually throw bad_alloc
}
} catch (const std::bad_alloc& e) {
std::cout << "Caught expected bad_alloc\n";
}
// THE CRITICAL TEST: Vector is still valid!
std::cout << "Elements after failure: " << v.size() << "\n";
std::cout << "First element: " << v[0] << "\n";
std::cout << "Last element: " << v[v.size()-1] << "\n";
// Vector can still be used
v.pop_back();
std::cout << "After pop_back: " << v.size() << "\n";
// Reset allocation tracking
tracker.reset();
// Vector can grow again when memory is available
v.push_back(999);
std::cout << "After recovery: " << v.size() << "\n";
std::cout << "New last element: " << v.back() << "\n";
return 0;
}
// Expected output:
// Elements before test: 100
// Allocations so far: 7 (due to growth: 1,2,4,8,16,32,64,128)
// Caught expected bad_alloc
// Elements after failure: 100 (or slightly more, unchanged from point of failure)
// First element: 0
// Last element: 99 (or the last successful push)
// After pop_back: 99
// After recovery: 100
// New last element: 999
The key verification: Run with Valgrind or AddressSanitizer and see ZERO leaks or errors, even after exception handling.
4. Solution Architecture
4.1 High-Level Design
┌─────────────────────────────────────────────────────────────────────────────┐
│ Vector<T> Memory Layout │
├─────────────────────────────────────────────────────────────────────────────┤
│ │
│ Vector<T> Object (on stack or as member): │
│ ┌─────────────────────────────────────────────────────────────────────┐ │
│ │ T* data_ ───────────────────────────────────┐ │ │
│ │ size_t size_ = 3 │ │ │
│ │ size_t capacity_ = 8 │ │ │
│ └───────────────────────────────────────────────────│──────────────────┘ │
│ │ │
│ ▼ │
│ Heap Memory: │
│ ┌─────────────────────────────────────────────────────────────────────┐ │
│ │ ┌─────┬─────┬─────┬─────┬─────┬─────┬─────┬─────┐ │ │
│ │ │ T │ T │ T │ │ │ │ │ │ │ │
│ │ │ [0] │ [1] │ [2] │ --- │ --- │ --- │ --- │ --- │ │ │
│ │ └─────┴─────┴─────┴─────┴─────┴─────┴─────┴─────┘ │ │
│ │ ◄──── size_ ────► ◄───── uninitialized ─────────► │ │
│ │ ◄─────────────────── capacity_ ─────────────────► │ │
│ └─────────────────────────────────────────────────────────────────────┘ │
│ │
│ Key insight: Elements [0, size_) are constructed objects │
│ Elements [size_, capacity_) are raw memory │
│ │
└─────────────────────────────────────────────────────────────────────────────┘
4.2 Resize Operation with Exception Safety
┌─────────────────────────────────────────────────────────────────────────────┐
│ Exception-Safe Resize Operation │
├─────────────────────────────────────────────────────────────────────────────┤
│ │
│ STEP 1: Allocate new buffer (wrapped in unique_ptr) │
│ ┌─────────────────────────────────────────────────────────────────────┐ │
│ │ unique_ptr<T[]> new_data = allocate(new_capacity); │ │
│ │ │ │
│ │ If this throws bad_alloc: │ │
│ │ → unique_ptr destructor runs (nothing to free yet) │ │
│ │ → Original vector unchanged ✓ │ │
│ │ → Strong guarantee satisfied ✓ │ │
│ └─────────────────────────────────────────────────────────────────────┘ │
│ │
│ STEP 2: Copy/Move elements to new buffer │
│ ┌─────────────────────────────────────────────────────────────────────┐ │
│ │ for (size_t i = 0; i < size_; ++i) { │ │
│ │ new(new_data.get() + i) T(data_[i]); // or move │ │
│ │ } │ │
│ │ │ │
│ │ If any copy/move throws: │ │
│ │ → unique_ptr destructor frees new_data │ │
│ │ → But wait! Partially constructed elements need destruction! │ │
│ │ → Solution: Track how many succeeded, destroy them │ │
│ │ → Original vector unchanged ✓ │ │
│ │ → Strong guarantee satisfied ✓ │ │
│ └─────────────────────────────────────────────────────────────────────┘ │
│ │
│ STEP 3: Commit the change (noexcept operations only!) │
│ ┌─────────────────────────────────────────────────────────────────────┐ │
│ │ destroy_all(data_, size_); // Destroy old elements (noexcept) │ │
│ │ deallocate(data_); // Free old memory (noexcept) │ │
│ │ data_ = new_data.release(); // Take ownership (noexcept) │ │
│ │ capacity_ = new_capacity; // Update bookkeeping (noexcept) │ │
│ │ │ │
│ │ All operations are noexcept → cannot fail → success! │ │
│ └─────────────────────────────────────────────────────────────────────┘ │
│ │
│ ┌─────────────────────────────────────────────────────────────────────┐ │
│ │ Visual Timeline │ │
│ │ │ │
│ │ Before: During Copy: After Commit: │ │
│ │ ┌───────┐ ┌───────┐ ┌───────────┐ ┌───────────┐ │ │
│ │ │ A B C │ │ A B C │ │ A' B' C' │ │ A' B' C' │ │ │
│ │ └───────┘ └───────┘ └───────────┘ └───────────┘ │ │
│ │ data_ data_ new_data data_ │ │
│ │ (still (unique_ptr) (now owns │ │
│ │ valid) new memory) │ │
│ │ │ │
│ │ If exception at any point before commit: │ │
│ │ → new_data destroyed, old data_ still valid │ │
│ └─────────────────────────────────────────────────────────────────────┘ │
│ │
└─────────────────────────────────────────────────────────────────────────────┘
4.3 Copy-and-Swap Idiom Flow
┌─────────────────────────────────────────────────────────────────────────────┐
│ Copy-and-Swap Assignment Flow │
├─────────────────────────────────────────────────────────────────────────────┤
│ │
│ Vector& operator=(Vector other) // Note: passed BY VALUE │
│ { │
│ swap(other); // noexcept │
│ return *this; │
│ } // other's destructor cleans up │
│ │
│ ┌─────────────────────────────────────────────────────────────────────┐ │
│ │ Step-by-Step Visualization: │ │
│ │ │ │
│ │ Initial State: │ │
│ │ ┌──────────────────┐ ┌──────────────────┐ │ │
│ │ │ this (target) │ │ rhs (source) │ │ │
│ │ │ data_: [1,2,3] │ │ data_: [A,B,C,D] │ │ │
│ │ │ size_: 3 │ │ size_: 4 │ │ │
│ │ └──────────────────┘ └──────────────────┘ │ │
│ │ │ │
│ │ Step 1: Copy construction of parameter 'other' from rhs │ │
│ │ ┌──────────────────┐ ┌──────────────────┐ ┌──────────────────┐ │ │
│ │ │ this │ │ other (copy) │ │ rhs (unchanged) │ │ │
│ │ │ [1,2,3] │ │ [A',B',C',D'] │ │ [A,B,C,D] │ │ │
│ │ └──────────────────┘ └──────────────────┘ └──────────────────┘ │ │
│ │ │ │
│ │ ⚠️ If copy throws here: this is unchanged, other destroyed │ │
│ │ Strong guarantee preserved! │ │
│ │ │ │
│ │ Step 2: swap(other) - exchanges all internal state │ │
│ │ ┌──────────────────┐ ┌──────────────────┐ │ │
│ │ │ this │ │ other │ │ │
│ │ │ [A',B',C',D'] │ │ [1,2,3] │ ← swapped! │ │
│ │ └──────────────────┘ └──────────────────┘ │ │
│ │ │ │
│ │ Step 3: Function returns, 'other' goes out of scope │ │
│ │ ┌──────────────────┐ │ │
│ │ │ this │ other destroyed, taking old [1,2,3] with it │ │
│ │ │ [A',B',C',D'] │ │ │
│ │ └──────────────────┘ │ │
│ │ │ │
│ └─────────────────────────────────────────────────────────────────────┘ │
│ │
│ Why pass by value? │
│ 1. If caller passes lvalue: copy made (as expected for copy assignment) │
│ 2. If caller passes rvalue: move made (free move optimization!) │
│ 3. Self-assignment handled automatically (swap with copy of self) │
│ │
└─────────────────────────────────────────────────────────────────────────────┘
4.4 Key Components
| Component | Responsibility |
|---|---|
data_ |
Raw pointer to heap-allocated array |
size_ |
Count of constructed elements |
capacity_ |
Size of allocated array (elements, not bytes) |
grow() |
Internal function to reallocate with larger capacity |
swap() |
Exchange state with another vector (must be noexcept) |
4.5 Data Structures
template<typename T>
class Vector {
private:
T* data_; // Pointer to heap array (may be nullptr)
size_t size_; // Number of constructed elements [0, capacity_]
size_t capacity_; // Number of elements we can hold without reallocation
// INVARIANTS:
// - If capacity_ > 0, data_ points to valid memory for capacity_ T's
// - If capacity_ == 0, data_ may be nullptr
// - size_ <= capacity_
// - Elements at [data_, data_ + size_) are constructed
// - Memory at [data_ + size_, data_ + capacity_) is uninitialized
public:
// ... member functions ...
};
4.6 Algorithm Overview: Resize Strategy
Growth Policy:
When push_back needs more space:
- If
capacity_ == 0: allocate space for 1 element - Otherwise: double the capacity (amortized O(1) for n insertions)
Why 2x growth?
- With 1.5x: still amortized O(1) but more allocations
- With 2x: fewer allocations, uses ~2x the minimum required space
- Trade-off between memory overhead and allocation frequency
5. Implementation Guide
5.1 Development Environment Setup
# Required: C++17 compiler, Valgrind or ASan
# macOS
brew install llvm
export CXX=/opt/homebrew/opt/llvm/bin/clang++
# Linux (Ubuntu/Debian)
sudo apt install g++ valgrind
# Verify C++17 support
echo 'int main() { if constexpr(true) {} }' | $CXX -std=c++17 -x c++ -
# Create project structure
mkdir -p exception-safe-vector/{src,tests,include}
cd exception-safe-vector
5.2 Project Structure
exception-safe-vector/
├── include/
│ └── Vector.hpp # Your Vector implementation
├── src/
│ └── main.cpp # Usage examples
├── tests/
│ ├── test_basic.cpp # Basic functionality tests
│ ├── test_exception.cpp # Exception safety tests
│ ├── test_allocation.cpp # Allocation failure tests
│ └── AllocationTracker.hpp # Helper for injection
├── Makefile
└── README.md
5.3 The Core Question You’re Answering
“How do I write C++ code that never leaks resources and never corrupts state, even when any operation might fail with an exception?”
This question is fundamental because:
- In C++, any operation that allocates memory can throw
std::bad_alloc - Any operation that copies user-defined types can throw
- If you’re not exception-safe, your code is correct only on the happy path
- The C++ standard library is designed around these guarantees
5.4 Concepts You Must Understand First
Before starting, verify you can answer these questions:
| Concept | Self-Assessment Question | Reference |
|---|---|---|
| Object lifetime | What exactly triggers a destructor call? | Effective C++ Item 13 |
| Move semantics | What’s the difference between T&& and const T&? |
Effective Modern C++ Ch. 5 |
new/delete |
What does new T[n] return and how must it be deleted? |
C++ Primer Ch. 12 |
| Placement new | How do you construct an object in pre-allocated memory? | Josuttis, “The C++ Standard Library” |
| Templates | Can you write a function template that works with any type? | C++ Templates book Ch. 1-2 |
| Smart pointers | When would you use unique_ptr vs shared_ptr? |
Effective Modern C++ Items 18-21 |
5.5 Questions to Guide Your Design
Work through these before writing code:
Memory Management:
- Will you use
new T[n]oroperator new+ placement new? (Hint: you need the latter for exception safety) - How do you construct an object in pre-allocated memory?
- How do you destroy an object without freeing memory?
Exception Safety:
- In
push_back, at what points can an exception occur? - If an exception occurs during resize, what must be cleaned up?
- How will you ensure the original vector is unchanged if resize fails?
Copy-and-Swap:
- Why is the parameter to
operator=passed by value? - Why must
swapbenoexcept? - What members need to be swapped?
Testing:
- How will you simulate allocation failures?
- How will you verify no memory leaks?
- How will you test that state is unchanged after an exception?
5.6 Thinking Exercise
Before writing any code, work through this scenario by hand:
You have a Vector<std::string> with 4 elements, capacity 4:
data_ = [ptr] -> ["Hello", "World", "Foo", "Bar"]
size_ = 4
capacity_ = 4
Now push_back("Baz") is called. Trace through:
- What check determines we need to resize?
- What’s the new capacity?
- In what order do we:
- Allocate new memory
- Copy elements
- Destroy old elements
- Free old memory
- Update pointers
Now consider: what if std::string’s copy constructor throws while copying “Foo”?
- What memory exists at that point?
- What gets destroyed/freed?
- What is the final state of the vector?
Write your answers before proceeding. This is the core of exception safety.
5.7 Hints in Layers
Hint 1: Starting Point - Use Placement New
You cannot use new T[n] because it constructs all n elements. You need:
operator new(sizeof(T) * n)to allocate raw memory- Placement
new (ptr) T(value)to construct individual elements - Explicit destructor call
ptr->~T()to destroy without freeing
// Allocate raw memory (no construction)
void* raw = operator new(sizeof(T) * capacity);
T* data = static_cast<T*>(raw);
// Construct one element
new (data + index) T(value);
// Destroy one element (no deallocation)
(data + index)->~T();
// Deallocate raw memory
operator delete(data);
Hint 2: RAII Wrapper for New Allocation
Use std::unique_ptr with a custom deleter to guard the new allocation:
void grow() {
size_t new_capacity = capacity_ == 0 ? 1 : capacity_ * 2;
// Custom deleter for raw memory
auto deleter = [](T* p) { operator delete(p); };
std::unique_ptr<T, decltype(deleter)> new_data(
static_cast<T*>(operator new(sizeof(T) * new_capacity)),
deleter
);
// If any exception occurs from here on, new_data is automatically freed
// Copy elements...
// ...
// Commit (noexcept from here):
// destroy old elements
// deallocate old memory
// data_ = new_data.release();
// capacity_ = new_capacity;
}
Hint 3: Handling Partial Construction
If copying throws mid-way, you must destroy the already-copied elements:
size_t copied = 0;
try {
for (size_t i = 0; i < size_; ++i) {
new (new_data.get() + i) T(data_[i]);
++copied; // Track successful copies
}
} catch (...) {
// Destroy elements that were successfully copied
for (size_t i = 0; i < copied; ++i) {
(new_data.get() + i)->~T();
}
throw; // Re-throw, unique_ptr will free memory
}
Or use a helper RAII class that tracks construction progress.
Hint 4: Copy-and-Swap Implementation
The classic pattern:
// noexcept swap - fundamental building block
void swap(Vector& other) noexcept {
using std::swap;
swap(data_, other.data_);
swap(size_, other.size_);
swap(capacity_, other.capacity_);
}
// Copy-and-swap assignment
// Note: parameter passed by VALUE (triggers copy or move)
Vector& operator=(Vector other) {
swap(other); // noexcept
return *this;
} // other's destructor runs, freeing old data
// Non-member swap (calls member swap)
friend void swap(Vector& a, Vector& b) noexcept {
a.swap(b);
}
This handles:
- Self-assignment (swap with copy of self = no-op effect)
- Exception safety (copy happens before swap)
- Move optimization (if passed rvalue, no copy made)
5.8 The Interview Questions They’ll Ask
After completing this project, you’ll be ready for these questions:
- “Explain the three exception guarantees in C++”
- They want: basic (no leaks, invariants preserved), strong (rollback on failure), nothrow (never throws)
- Bonus: give examples of standard library functions at each level
- “What is RAII and why does it matter for exception safety?”
- They want: tie resource lifetime to object lifetime; destructors run during stack unwinding
- Example:
unique_ptr, lock guards, file handles
- “How would you implement a strongly exception-safe assignment operator?”
- They want: copy-and-swap idiom
- Explain: copy parameter, swap state, let destructor clean up
- “When should a function be marked
noexcept?”- They want: move operations, swap, destructors, operations where failure is unrecoverable
- Discuss: performance implications,
std::vectormove optimization
- “What happens if
newthrows in the middle of an operation?”- They want: discussion of cleanup, RAII wrappers, maintaining invariants
- Show understanding of stack unwinding
- “What’s the difference between
new T[n]and placement new?”- They want: array new constructs all elements; placement new constructs in existing memory
- Discuss: why vector needs placement new for efficiency and exception safety
- “How does
std::vectorachieve amortized O(1) push_back?”- They want: geometric growth (typically 2x), copy/move on resize
- Discuss: trade-off between memory usage and reallocation frequency
5.9 Books That Will Help
| Topic | Book | Chapter/Section |
|---|---|---|
| Exception Safety Fundamentals | Effective C++, 3rd Ed (Meyers) | Item 29: “Strive for exception-safe code” |
| RAII Principle | Effective C++, 3rd Ed (Meyers) | Item 13: “Use objects to manage resources” |
| Copy-and-Swap Idiom | Effective C++, 3rd Ed (Meyers) | Item 11: “Handle assignment to self” |
noexcept Specification |
Effective Modern C++ (Meyers) | Item 14: “Declare functions noexcept if they won’t emit exceptions” |
| Move Semantics | Effective Modern C++ (Meyers) | Items 23-25 (Move semantics chapter) |
| Placement New | The C++ Programming Language (Stroustrup) | Section 11.2.4 |
| Smart Pointers | Effective Modern C++ (Meyers) | Items 18-21 |
| Exception Handling Details | Exceptional C++ (Sutter) | Items 8-19 |
| Strong Guarantee Patterns | More Exceptional C++ (Sutter) | Items 17-23 |
| STL Container Implementation | C++ Standard Library (Josuttis) | Chapter 7: STL Containers |
5.10 Implementation Phases
Phase 1: Foundation (Days 1-3)
Goals:
- Set up project with build system
- Implement basic memory management (allocate, deallocate, construct, destroy)
- Implement constructors and destructor
Tasks:
- Create
Vector.hppwith class skeleton - Implement raw memory allocation/deallocation helpers
- Implement default constructor
- Implement destructor (must handle nullptr data)
- Implement
size(),capacity(),empty()
Checkpoint: Can create empty vector, destructor runs cleanly (verify with Valgrind).
Phase 2: Basic Operations (Days 4-6)
Goals:
- Implement element access
- Implement simple modifications (without resize)
Tasks:
- Implement
operator[]andat() - Implement
front()andback() - Implement
pop_back()andclear()(both noexcept) - Implement
reserve()with strong guarantee
Checkpoint: Can reserve capacity, add elements manually (placement new), access them, clear them.
Phase 3: Exception-Safe Resize (Days 7-9)
Goals:
- Implement
push_backwith strong exception guarantee - Handle allocation and copy failures correctly
Tasks:
- Implement internal
grow()with RAII for new buffer - Implement
push_back(const T&)using grow - Implement
push_back(T&&)with move semantics - Test with throwing types
- Test with allocation failure injection
Checkpoint: push_back leaves vector unchanged if any exception occurs.
Phase 4: Copy and Move Semantics (Days 10-12)
Goals:
- Implement copy constructor
- Implement move constructor (noexcept)
- Implement copy-and-swap assignment
- Implement move assignment (noexcept)
Tasks:
- Implement copy constructor
- Implement move constructor
- Implement noexcept
swap()member function - Implement
operator=using copy-and-swap - Add non-member
swap() - Test all assignment scenarios including self-assignment
Checkpoint: All copy/move operations work correctly; assignment provides strong guarantee.
Phase 5: Testing and Polish (Days 13-14)
Goals:
- Comprehensive testing
- Edge case handling
- Code cleanup
Tasks:
- Write tests for all operations
- Test with Valgrind/ASan for all code paths
- Test with ThreadSanitizer if using multi-threaded tests
- Edge cases: empty vector operations, self-assignment, move from empty
- Add assertions for invariant checking (debug mode)
- Clean up code, add comments
Checkpoint: All tests pass with zero memory errors under sanitizers.
5.11 Key Implementation Decisions
| Decision | Options | Recommendation | Rationale |
|---|---|---|---|
| Memory allocation | new[] vs operator new |
operator new |
Need to separate allocation from construction for exception safety |
| Growth factor | 1.5x vs 2x | 2x | Fewer reallocations, simpler implementation |
| Move strategy | Always move vs conditional | Use std::move_if_noexcept |
Preserve strong guarantee if T’s move can throw |
| Allocator support | None vs allocator-aware | None (initially) | Focus on core exception safety first |
| Small buffer optimization | None vs SBO | None | Adds complexity, learn fundamentals first |
| Debug checks | None vs assertions | Assertions in debug | Catch bugs early without release overhead |
6. Testing Strategy
Test Categories
| Category | Purpose | Priority |
|---|---|---|
| Correctness | Basic operations work | Must have |
| Exception Safety | State unchanged on exception | Must have |
| Memory Safety | No leaks, no corruption | Must have |
| Edge Cases | Empty vectors, self-assignment | Should have |
| Performance | Amortized O(1) push_back | Nice to have |
Critical Test Cases
Test 1: Basic Operations
void test_basic() {
Vector<int> v;
assert(v.empty());
assert(v.size() == 0);
v.push_back(1);
v.push_back(2);
v.push_back(3);
assert(v.size() == 3);
assert(v[0] == 1);
assert(v[1] == 2);
assert(v[2] == 3);
assert(v.front() == 1);
assert(v.back() == 3);
v.pop_back();
assert(v.size() == 2);
assert(v.back() == 2);
v.clear();
assert(v.empty());
}
Test 2: Exception Safety on Push
struct ThrowingType {
static int throw_after;
static int constructions;
int value;
ThrowingType(int v) : value(v) {
if (++constructions >= throw_after) {
throw std::runtime_error("Planned failure");
}
}
ThrowingType(const ThrowingType& other) : ThrowingType(other.value) {}
};
void test_push_exception_safety() {
Vector<ThrowingType> v;
ThrowingType::throw_after = 1000;
ThrowingType::constructions = 0;
// Fill with some elements
for (int i = 0; i < 10; ++i) {
v.push_back(ThrowingType(i));
}
// Now cause next copy to throw
ThrowingType::throw_after = ThrowingType::constructions + 5;
size_t size_before = v.size();
try {
// Try to add many elements (will trigger resize and throw)
for (int i = 0; i < 100; ++i) {
v.push_back(ThrowingType(100 + i));
}
assert(false); // Should have thrown
} catch (const std::runtime_error&) {
// Strong guarantee: size unchanged or slightly increased
// (depending on when throw happened)
assert(v.size() >= size_before);
// And all original elements intact
for (size_t i = 0; i < size_before; ++i) {
assert(v[i].value == static_cast<int>(i));
}
}
}
Test 3: Allocation Failure
// In AllocationTracker.hpp
extern size_t allocations_until_failure;
void* operator new(size_t size) {
if (allocations_until_failure == 0) {
throw std::bad_alloc();
}
if (allocations_until_failure != SIZE_MAX) {
--allocations_until_failure;
}
return malloc(size);
}
void test_bad_alloc() {
Vector<int> v;
// Add some elements
for (int i = 0; i < 100; ++i) {
v.push_back(i);
}
size_t size_before = v.size();
// Force next allocation to fail
allocations_until_failure = 0;
try {
// Try to trigger resize
for (int i = 0; i < 1000; ++i) {
v.push_back(i);
}
assert(false);
} catch (const std::bad_alloc&) {
// Vector should still be usable
assert(v.size() == size_before || v.size() > size_before);
}
// Reset and verify vector still works
allocations_until_failure = SIZE_MAX;
v.push_back(999);
assert(v.back() == 999);
}
Test 4: Copy-and-Swap Semantics
void test_copy_assignment() {
Vector<int> v1;
v1.push_back(1);
v1.push_back(2);
Vector<int> v2;
v2.push_back(10);
v2.push_back(20);
v2.push_back(30);
v1 = v2; // Copy assignment
assert(v1.size() == 3);
assert(v1[0] == 10);
// v2 unchanged
assert(v2.size() == 3);
assert(v2[0] == 10);
// Self-assignment
v1 = v1;
assert(v1.size() == 3);
assert(v1[0] == 10);
}
void test_move_operations() {
Vector<int> v1;
v1.push_back(1);
v1.push_back(2);
Vector<int> v2 = std::move(v1); // Move construction
assert(v2.size() == 2);
assert(v2[0] == 1);
// v1 is now in valid but unspecified state
Vector<int> v3;
v3 = std::move(v2); // Move assignment
assert(v3.size() == 2);
assert(v3[0] == 1);
}
Testing with Sanitizers
# AddressSanitizer (ASan) - catches memory errors
g++ -std=c++17 -fsanitize=address -g tests/test_all.cpp -o test_asan
./test_asan
# UndefinedBehaviorSanitizer (UBSan)
g++ -std=c++17 -fsanitize=undefined -g tests/test_all.cpp -o test_ubsan
./test_ubsan
# Valgrind (alternative to ASan)
g++ -std=c++17 -g tests/test_all.cpp -o test
valgrind --leak-check=full ./test
7. Common Pitfalls & Debugging
Frequent Mistakes
| Pitfall | Symptom | Solution |
|---|---|---|
Using new T[n] |
Constructs n elements, inefficient | Use operator new + placement new |
| Forgetting to destroy elements | Memory leaks in complex types | Always call destructor before deallocation |
| Non-noexcept swap | Copy-and-swap doesn’t provide strong guarantee | Mark swap as noexcept |
| Throwing destructor | std::terminate called |
Destructors must be noexcept |
| Double free | Crash or corruption | Ensure clear ownership, set pointers to nullptr |
| Not handling self-assignment | Corruption or crash | Copy-and-swap handles this automatically |
| Raw pointer member after throw | Use-after-free | Wrap allocations in RAII |
Debugging Strategies
For memory issues:
- Run with AddressSanitizer or Valgrind
- Add logging to constructors/destructors
- Use a custom allocator that tracks allocations
For exception safety issues:
- Create a type that throws on Nth construction
- Add logging before and after each potentially-throwing operation
- Verify state after catching exception
For logic errors:
- Add assertions for invariants
- Check size <= capacity at every operation
- Verify all elements in [0, size) are constructed
Performance Traps
| Trap | Impact | Fix |
|---|---|---|
| Copying when moving possible | 2x slower for large objects | Use std::move appropriately |
| Growing by +1 each time | O(n^2) for n insertions | Use geometric growth (2x) |
| Reconstructing elements on clear | Unnecessary destructor calls | Just call destructors |
| Not reserving before bulk insert | Many reallocations | reserve(expected_size) first |
8. Extensions & Challenges
Beginner Extensions
- Add
emplace_back()using variadic templates - Add iterator support (
begin(),end()) - Add
insert()at specific position - Add
erase()single element and range
Intermediate Extensions
- Add
shrink_to_fit()to reduce capacity - Support allocator-aware design
- Implement
small_vectorwith inline storage (SBO) - Add
constexprsupport for compile-time vectors (C++20)
Advanced Extensions
- Thread-safe vector with copy-on-write semantics
- Support for non-copyable, move-only types
- Implement
std::vector-compatible interface fully - Benchmark against
std::vectoron various operations - Add exception safety documentation comments (like
noexcept(noexcept(T(args))))
9. Real-World Connections
Industry Applications
Financial Systems:
- Trading systems must never corrupt state on failure
- Order books use exception-safe containers
- Recovery from
bad_allocis critical during market spikes
Game Development:
- Custom allocators combined with exception-safe containers
- Memory pools for performance with RAII semantics
- Entity component systems use similar patterns
Database Engines:
- Transaction rollback is conceptually similar to strong guarantee
- B-tree implementations need exception-safe node operations
- Write-ahead logging enables recovery
Embedded Systems:
noexceptcritical for predictable timing- Custom containers with static allocation
- RAII for peripheral handles
Related Standard Library Components
std::vector- The standard implementationstd::unique_ptr- RAII for single ownershipstd::scoped_lock- RAII for mutex lockingstd::optional- Exception-safe “maybe” value
Interview Relevance
This project prepares you for:
- Google: Strong emphasis on exception safety in C++ interviews
- Bloomberg: Financial C++ requires robust error handling
- Microsoft: STL team questions about container implementation
- Gaming companies: Custom container implementation questions
- Embedded companies: Resource management and
noexcept
10. Resources
Essential Reading
- Effective C++, 3rd Ed by Scott Meyers - Items 13, 14, 29
- Exceptional C++ by Herb Sutter - Exception safety deep dive
- C++ Concurrency in Action Ch. 3 - Thread-safe data structures
Online Resources
- C++ Core Guidelines - E section on exceptions
- cppreference: Exception safety
- Howard Hinnant’s talks on move semantics
- Arthur O’Dwyer’s blog on allocators
Video Resources
- CppCon talks on exception safety
- Back to Basics: Exception Safety (CppCon)
- Jason Turner’s C++ Weekly on move semantics
Tools
- Valgrind: Memory error detection
- AddressSanitizer: Fast memory error detection
- UndefinedBehaviorSanitizer: Catches undefined behavior
- Compiler Explorer (godbolt.org): See generated assembly
11. Self-Assessment Checklist
Understanding
- I can explain the basic, strong, and nothrow guarantees without notes
- I understand why RAII is essential for exception safety
- I can describe the copy-and-swap idiom and why it provides strong guarantee
- I know when and why to use
noexcept - I understand the difference between
new T[n]and placement new - I can explain why destructors must be
noexcept
Implementation
- Default constructor creates empty vector
- Destructor never leaks memory (verified by sanitizers)
push_backprovides strong exception guarantee- Copy constructor performs deep copy
- Move constructor is
noexceptand efficient swapisnoexcept- Copy assignment works correctly (including self-assignment)
- Move assignment is
noexcept at()throwsstd::out_of_rangefor invalid indices- All operations maintain class invariants
Testing
- Basic operations tested with multiple types
- Exception safety tested with throwing types
- Allocation failure tested
- Zero memory errors under Valgrind/ASan
- Self-assignment tested
- Edge cases tested (empty vector, single element, etc.)
Growth
- I debugged at least one exception safety issue
- I can now read
std::vectorimplementation and understand it - I’m comfortable reasoning about exception safety in new code
- I understand the trade-offs in container design
12. Submission / Completion Criteria
Minimum Viable Completion
- Vector correctly stores and retrieves elements
push_backworks for growing the vector- No memory leaks under normal operation
- Basic copy construction works
Full Completion
- All five operations provide their documented guarantee
- All tests pass including exception safety tests
- Copy-and-swap assignment implemented
- Move operations are
noexcept - Zero memory errors under sanitizers
- Code handles
std::bad_allocgracefully
Excellence (Going Above & Beyond)
emplace_backwith perfect forwarding- Iterator support
- Allocator awareness
- Comparison with
std::vectorperformance - Small buffer optimization (SBO)
- Complete documentation with exception specifications
Learning Milestones
Track your progress through these milestones:
Milestone 1: Foundation (End of Phase 1)
Your Vector works for basic cases
- Can create, destroy, query size/capacity
- No memory leaks in simple scenarios
- Basic understanding of memory layout
Milestone 2: Correctness (End of Phase 2)
All basic operations work correctly
- push_back, pop_back, clear work
- Element access works
- reserve() allocates correct amount
Milestone 3: Exception Safety (End of Phase 3)
Your push_back doesn’t leak or corrupt on failure
- Using RAII for temporary allocations
- Partial construction handled correctly
- Strong guarantee verified with tests
Milestone 4: Complete (End of Phase 4)
All copy/move semantics correct
- Copy-and-swap for assignment
- Move operations are noexcept
- Self-assignment safe
Milestone 5: Production Quality (End of Phase 5)
Code is robust and well-tested
- All sanitizer checks pass
- Edge cases handled
- Code is clean and documented
This guide was expanded from LEARN_ADVANCED_CPP_DEEP_DIVE.md. For the complete learning path, see the project index.