Project 1: The Exception-Safe Vector

Build a Vector<T> that never corrupts state, even when allocations or element construction fail.

Quick Reference

Attribute Value
Difficulty Advanced
Time Estimate 1-2 weeks
Main Programming Language C++17 (Alternatives: Rust for comparison)
Coolness Level Genuinely Clever
Business Potential Resume Gold
Prerequisites C++ fundamentals, RAII, templates, basic allocator knowledge
Key Topics Exception guarantees, RAII, copy-and-swap, noexcept

1. Learning Objectives

By completing this project, you will:

  1. Provide strong exception safety for container mutation.
  2. Use RAII to guarantee cleanup on failure.
  3. Apply copy-and-swap to implement safe assignment.
  4. Reason about noexcept and move vs copy trade-offs.
  5. Build a failure-injection test harness for std::bad_alloc.

2. All Theory Needed (Per-Concept Breakdown)

2.1 Exception Guarantees

Description

C++ code is correct only if it remains correct under failure. The three guarantees define what remains true after an exception: basic (valid but changed), strong (unchanged), and no-throw (never throws).

Definitions & Key Terms

  • Basic guarantee: invariants preserved, no leaks.
  • Strong guarantee: commit-or-rollback semantics.
  • No-throw guarantee: operation never throws.

Mental Model Diagram (ASCII)

Operation
  | success -> new state
  | failure -> rollback (strong) OR valid-but-changed (basic)

How It Works (Step-by-Step)

  1. Identify every operation that can throw.
  2. Perform risky work on temporary state.
  3. Commit only after all risk passes.

Minimal Concrete Example

T& operator=(T other) noexcept { swap(other); return *this; }

Common Misconceptions

  • “Strong guarantee is always required” -> not always achievable or needed.

Check-Your-Understanding Questions

  • Which operations inside push_back can throw?
  • Why is swap central to strong guarantees?

Where You’ll Apply It

  • Project 1 (this file), also referenced in P02 (lock guards)

2.2 RAII and Ownership

Description

RAII ties resource lifetime to object lifetime. It is the foundation of exception-safe code because destructors always run during stack unwinding.

Definitions & Key Terms

  • RAII: resource acquisition is initialization.
  • Ownership: single clear owner responsible for cleanup.

Mental Model Diagram (ASCII)

[Resource] --owned by--> [Object] --destroyed--> [Resource released]

How It Works (Step-by-Step)

  1. Acquire resource in constructor.
  2. Store resource handle in object.
  3. Release in destructor.

Minimal Concrete Example

std::unique_ptr<T[]> buf(new T[n]);

Common Misconceptions

  • “RAII is just smart pointers” -> it applies to any resource.

Check-Your-Understanding Questions

  • Why do destructors run during exception unwinding?
  • What is the difference between owning and non-owning pointers?

Where You’ll Apply It

  • Project 1 resize logic and temporary buffers

2.3 Copy-and-Swap

Description

Copy-and-swap builds a safe new state, then atomically swaps it with the old state. It makes assignment strongly exception-safe if swap is noexcept.

Definitions & Key Terms

  • Swap: exchange two object states.
  • Commit step: point where new state replaces old.

Mental Model Diagram (ASCII)

old_state ----copy----> temp
old_state <---swap---- temp
(temp destroys old)

How It Works (Step-by-Step)

  1. Create a copy of the right-hand side.
  2. Swap with *this.
  3. Old state destructs when temp goes out of scope.

Minimal Concrete Example

void swap(Vector& other) noexcept { std::swap(data_, other.data_); }

Common Misconceptions

  • “Swap is always cheap” -> it is if it only swaps pointers.

Check-Your-Understanding Questions

  • Why is self-assignment safe with copy-and-swap?
  • What happens if swap throws?

Where You’ll Apply It

  • Project 1 assignment operator

2.4 noexcept and Move Semantics

Description

The standard library uses noexcept to decide whether moves are safe. If move can throw, containers may copy instead.

Definitions & Key Terms

  • noexcept: declared non-throwing function.
  • Move constructor: steals resources from a temporary.

Mental Model Diagram (ASCII)

if (move is noexcept) -> move elements
else -> copy elements

How It Works (Step-by-Step)

  1. The compiler sees a move constructor.
  2. If it is noexcept, containers prefer it.
  3. If not, containers may copy to preserve strong guarantees.

Minimal Concrete Example

Vector(Vector&& other) noexcept : data_(other.data_) { other.data_ = nullptr; }

Common Misconceptions

  • “Mark everything noexcept” -> only if truly safe.

Check-Your-Understanding Questions

  • Why do containers avoid throwing moves during reallocation?

Where You’ll Apply It

  • Project 1 move constructor, swap, destructor

3. Project Specification

3.1 What You Will Build

A minimal Vector<T> supporting push_back, size, capacity, and safe copy/move operations, with strong exception guarantees for reallocation paths.

3.2 Functional Requirements

  1. Dynamic storage with doubling growth strategy.
  2. push_back provides strong exception safety.
  3. Copy/move constructors follow value semantics.
  4. Safe assignment using copy-and-swap.
  5. Iterators or index access for validation.

3.3 Non-Functional Requirements

  • Reliability: no leaks under ASan/Valgrind.
  • Exception safety: strong guarantee on push_back.
  • Performance: no unnecessary deep copies during reallocation.

3.4 Example Usage / Output

Vector<int> v;
for (int i = 0; i < 3; ++i) v.push_back(i);
std::cout << v.size() << "/" << v.capacity() << "\n";

3.5 Data Formats / Schemas / Protocols

  • Internal layout: T* data_, size_t size_, size_t capacity_
  • Growth: capacity_ = max(1, capacity_ * 2)

3.6 Edge Cases

  • push_back on empty vector
  • push_back when allocation fails
  • Self-assignment
  • Move from empty vector

3.7 Real World Outcome

3.7.1 How to Run (Copy/Paste)

cmake -S . -B build
cmake --build build
./build/vector_test --fail-after=5 --seed=42

3.7.2 Golden Path Demo (Deterministic)

[TEST] push_back with failure injection
[ALLOC] countdown=5
[ALLOC] countdown=4
[ALLOC] countdown=3
[ALLOC] countdown=2
[ALLOC] countdown=1
[ALLOC] countdown=0 -> throwing std::bad_alloc
[OK] caught std::bad_alloc
[OK] size=5 capacity=8
[OK] elements intact: 0 1 2 3 4

3.7.3 Failure Demo

[FAIL] size changed after exception -> BUG

4. Solution Architecture

4.1 High-Level Design

[Vector<T>]
  |-- data_ (T*)
  |-- size_
  |-- capacity_
  |-- push_back -> maybe reallocate -> swap commit

4.2 Key Components

| Component | Responsibility | Key Decisions | |—————–|————————|——————————| | Storage pointer | Owns contiguous memory | unique_ptr for temp safety | | Reallocator | Grows capacity | doubling strategy | | Assignment | strong guarantee | copy-and-swap |

4.3 Data Structures (No Full Code)

struct Vector {
    T* data_;
    size_t size_;
    size_t capacity_;
};

4.4 Algorithm Overview

Reallocate and Push

  1. Allocate new buffer.
  2. Copy/move existing elements into new buffer.
  3. Commit swap.

Complexity Analysis:

  • Amortized push_back: O(1)
  • Reallocation: O(n)

5. Implementation Guide

5.1 Development Environment Setup

cmake -S . -B build
cmake --build build

5.2 Project Structure

vector-safe/
├── src/vector.hpp
├── src/vector.cpp
├── tests/vector_tests.cpp
└── CMakeLists.txt

5.3 The Core Question You’re Answering

“How can I guarantee that a container never corrupts its state when an allocation or copy throws?”

5.4 Concepts You Must Understand First

  • RAII and stack unwinding
  • Strong vs basic exception guarantees
  • noexcept and move semantics

5.5 Questions to Guide Your Design

  • Which lines in push_back can throw?
  • When is it safe to update size_?
  • How can you guarantee cleanup of partially constructed data?

5.6 Thinking Exercise

Simulate a push_back that throws on the 3rd element copy. What is the state of your old buffer and size?

5.7 The Interview Questions They’ll Ask

  1. What is the strong exception guarantee?
  2. Why should destructors be noexcept?
  3. How does copy-and-swap avoid leaks?
  4. When is std::vector allowed to invalidate iterators?

5.8 Hints in Layers

Hint 1: Use unique_ptr<T[]> for temporary allocations. Hint 2: Only increment size_ after element construction succeeds. Hint 3: Use std::swap for commit.

5.9 Books That Will Help

| Topic | Book | Chapter | |——————|——————————|————————| | Exception safety | Effective C++ | Exception safety items | | RAII | A Tour of C++ | Resource management | | Containers | The C++ Programming Language | Containers chapter |

5.10 Implementation Phases

Phase 1: Core Container (2-3 days)

  • Build storage pointer, size, capacity.
  • Implement push_back without exceptions.
  • Checkpoint: basic tests pass.

Phase 2: Strong Guarantee (3-4 days)

  • Implement reallocation via temp buffer and swap.
  • Add failure injection.
  • Checkpoint: bad_alloc does not corrupt state.

Phase 3: Polish (2-3 days)

  • Add move constructor, noexcept swap.
  • Add tests for self-assignment.
  • Checkpoint: ASan clean.

5.11 Key Implementation Decisions

| Decision | Options | Recommendation | Rationale | |—————|—————————|—————-|—————————| | Growth factor | 1.5x / 2x | 2x | standard vector strategy | | Copy vs move | always move / conditional | conditional | preserve strong guarantee |

6. Testing Strategy

6.1 Test Categories

| Category | Purpose | Examples | |———–|——————–|—————————| | Unit | individual methods | push_back, size, capacity | | Exception | failure handling | bad_alloc injection | | Memory | leaks/UB | ASan/Valgrind |

6.2 Critical Test Cases

  1. Reallocation throws and state is unchanged.
  2. Self-assignment leaves state valid.
  3. Move leaves source empty but valid.

6.3 Test Data

inputs: 0..100, fail-after=5
expected: size <= 5, elements intact

7. Common Pitfalls & Debugging

7.1 Frequent Mistakes

| Pitfall | Symptom | Solution | |———————–|——————————|———————-| | Update size too early | size changes after exception | commit after success | | Not using RAII | leak on throw | wrap temp buffer | | Throwing destructor | terminate on unwind | mark noexcept |

7.2 Debugging Strategies

  • Use ASan to catch leaks and UAF.
  • Add logs around allocation and copy.

7.3 Performance Traps

  • Deep copies on every push -> fix with capacity doubling.

8. Extensions & Challenges

8.1 Beginner Extensions

  • Add reserve and shrink_to_fit.
  • Add at() with bounds checking.

8.2 Intermediate Extensions

  • Add iterator support.
  • Add emplace_back.

8.3 Advanced Extensions

  • Add allocator support.
  • Optimize with small-buffer optimization.

9. Real-World Connections

9.1 Industry Applications

  • Standard library containers
  • High-performance systems needing deterministic cleanup
  • libc++ / libstdc++ vector implementations

9.3 Interview Relevance

  • Exception safety and RAII are common senior C++ interview topics.

10. Resources

10.1 Essential Reading

  • Effective C++ (exception safety items)
  • The C++ Programming Language (resource management)

10.2 Tools & Documentation

  • ASan / UBSan (compiler flags)
  • Next: P02 Thread-Safe Queue

11. Self-Assessment Checklist

11.1 Understanding

  • I can explain strong vs basic guarantees.
  • I can explain why swap must be noexcept.

11.2 Implementation

  • All requirements met and tests pass.
  • ASan shows no leaks.

11.3 Growth

  • I can explain this project in an interview.

12. Submission / Completion Criteria

Minimum Viable Completion:

  • Strong guarantee on push_back
  • Clean ASan run

Full Completion:

  • Copy/move constructors + assignment
  • Failure injection tests

Excellence:

  • Custom allocator support and benchmarking