Project 4: Generic Container Library

Build STL-like implementations of vector, list, and unordered_map with proper iterators, allocator support, and exception safety.

Quick Reference

Attribute Value
Difficulty Advanced
Time Estimate 3-4 weeks
Language C++
Prerequisites Projects 1-3, template basics, understanding of complexity
Key Topics Templates, iterators, memory allocation, exception safety, move semantics

1. Learning Objectives

After completing this project, you will:

  • Master C++ template class design and implementation
  • Understand iterator categories and how to implement them
  • Learn memory allocation strategies (growth factors, allocators)
  • Implement exception safety guarantees (basic, strong, nothrow)
  • Apply move semantics for efficient container operations
  • Understand why the STL is designed the way it is

2. Theoretical Foundation

2.1 Core Concepts

Template Classes

Templates let you write generic code that works with any type:

template<typename T>
class MyVector {
    T* data_;
    size_t size_;
    // Works with int, double, std::string, any type T
};

The compiler generates a new class for each type used:

  • MyVector<int> is a separate class from MyVector<double>
  • This is called template instantiation

Iterator Design

Iterators are the glue between containers and algorithms. The STL defines iterator categories:

Category Operations Examples
Input ++, *, == istream_iterator
Output ++, * ostream_iterator
Forward Input + multi-pass forward_list::iterator
Bidirectional Forward + – list::iterator
Random Access Bidirectional + +n, -n, [] vector::iterator

For vector, the iterator is just a pointer (random access). For list, the iterator wraps a node pointer (bidirectional).

// Random access iterator for vector
template<typename T>
class VectorIterator {
    T* ptr_;
public:
    T& operator*() { return *ptr_; }
    VectorIterator& operator++() { ++ptr_; return *this; }
    VectorIterator operator+(ptrdiff_t n) { return {ptr_ + n}; }
    bool operator==(const VectorIterator& other) { return ptr_ == other.ptr_; }
    // ... more operations
};

Allocators

Allocators abstract memory management:

template<typename T, typename Allocator = std::allocator<T>>
class MyVector {
    Allocator alloc_;

    T* allocate(size_t n) {
        return std::allocator_traits<Allocator>::allocate(alloc_, n);
    }

    void construct(T* p, const T& value) {
        std::allocator_traits<Allocator>::construct(alloc_, p, value);
    }
};

Why allocators?

  • Custom memory pools
  • Arena allocators for games
  • Shared memory allocators
  • Debug allocators that track allocations

Exception Safety Guarantees

Guarantee Meaning Example
Nothrow Never throws swap(), destructors
Strong If exception, state unchanged push_back() (usually)
Basic No leaks, valid (but changed) state insert() range

For push_back, strong guarantee means:

  • If reallocation fails, original vector unchanged
  • If element copy throws, new storage freed, original unchanged

Growth Strategy

Vector must grow when full. Options:

  • Add fixed amount: O(n) amortized push_back
  • Double capacity: O(1) amortized push_back

Why doubling works:

push_back operations: 1, 2, 3, 4, 5, 6, 7, 8, 9, ...
reallocations at:     1, 2, 4, 8 (capacity doubles)
cost at realloc:      1, 2, 4, 8 (copy old elements)
total cost for n:     O(n) copies for n elements = O(1) amortized

2.2 Why This Matters

Understanding container implementation:

  • Helps choose the right container for performance
  • Enables custom containers for specific needs
  • Prepares you for performance-critical code
  • Is frequently asked in interviews

Real-world applications:

  • Game engines use custom vector with arena allocation
  • Databases use custom containers for buffer management
  • High-frequency trading needs cache-friendly containers

2.3 Historical Context

The STL was designed by Alexander Stepanov in the 1990s, influenced by:

  • Generic programming ideas from Ada
  • Mathematical concepts of iterators and algorithms
  • Performance requirements for real systems

The key insight: separate containers, algorithms, and iterators:

  • Containers: how data is stored
  • Algorithms: operations on data
  • Iterators: abstraction connecting them

This means N containers + M algorithms = N*M combinations with only N+M implementations.

2.4 Common Misconceptions

Misconception 1: “vector::push_back is always O(1)” False. Individual push_back can be O(n) when reallocating. But amortized over many push_backs, it’s O(1).

Misconception 2: “list is always better for insertions” False. Vector is usually faster due to cache locality, even for middle insertions, unless you’re inserting many elements in the middle of a very large container.

Misconception 3: “Iterators are like pointers” Partially true. Vector iterators often are pointers. But list iterators are objects wrapping node pointers. Iterator invalidation rules differ.

Misconception 4: “unordered_map is always faster than map” False. For small sizes, map (tree-based) can be faster. Hash computation and cache effects matter.

3. Project Specification

3.1 What You Will Build

A mini-STL with:

  1. MyVector<T> - Dynamic array with amortized O(1) push_back
  2. MyList<T> - Doubly-linked list with O(1) insert/erase
  3. MyUnorderedMap<K, V> - Hash table with O(1) average lookup
  4. Iterators that work with standard algorithms (std::sort, std::find)

3.2 Functional Requirements

ID Requirement
F1 MyVector: dynamic growth with capacity doubling
F2 MyVector: push_back, pop_back, insert, erase
F3 MyVector: random access iterator compatible with std::sort
F4 MyVector: at() with bounds checking
F5 MyList: doubly-linked with O(1) insert/erase at iterator
F6 MyList: push_front, push_back, splice
F7 MyList: bidirectional iterator
F8 MyUnorderedMap: hash table with separate chaining
F9 MyUnorderedMap: operator[], at(), find(), insert(), erase()
F10 MyUnorderedMap: rehash when load factor exceeds threshold

3.3 Non-Functional Requirements

ID Requirement
N1 Vector: O(1) amortized push_back
N2 Vector: strong exception guarantee for push_back
N3 List: O(1) insert and erase
N4 HashMap: O(1) average lookup, insert, erase
N5 All containers: no memory leaks
N6 All iterators: work with standard algorithms

3.4 Example Usage / Output

// MyVector works like std::vector
MyVector<int> v;
v.push_back(1);
v.push_back(2);
v.push_back(3);

for (auto it = v.begin(); it != v.end(); ++it) {
    std::cout << *it << " ";  // 1 2 3
}

// Works with standard algorithms!
std::sort(v.begin(), v.end(), std::greater<int>());
// v is now: 3 2 1

v.insert(v.begin() + 1, 10);  // v: 3 10 2 1
v.erase(v.begin());            // v: 10 2 1

// MyList is a doubly-linked list
MyList<std::string> names;
names.push_back("Alice");
names.push_front("Bob");
auto it = std::find(names.begin(), names.end(), "Alice");
names.insert(it, "Charlie");  // Insert before Alice
// names: Bob Charlie Alice

// MyUnorderedMap is a hash map
MyUnorderedMap<std::string, int> ages;
ages["Alice"] = 30;
ages["Bob"] = 25;
ages.insert({"Charlie", 35});

std::cout << ages.at("Alice");  // 30
std::cout << ages["Unknown"];   // 0 (default-inserted)

if (ages.find("Bob") != ages.end()) {
    std::cout << "Found Bob!\n";
}

ages.erase("Charlie");
std::cout << ages.size();  // 2

3.5 Real World Outcome

After completing this project, you will:

  • Understand how STL containers work internally
  • Know when to use which container based on performance
  • Be able to implement custom containers for specific needs
  • Have deep knowledge for systems programming interviews

4. Solution Architecture

4.1 High-Level Design

MyVector

+------------------+
|    MyVector      |
|------------------|     +-----+-----+-----+-----+-----+
| T* data_         |---->|  0  |  1  |  2  |     |     |
| size_t size_     |     +-----+-----+-----+-----+-----+
| size_t capacity_ |      [0]   [1]   [2]  [unused space]
| Allocator alloc_ |
+------------------+
     size_ = 3, capacity_ = 5

MyList

+------------------+
|     MyList       |
|------------------|
| Node* head_      |
| Node* tail_      |
| size_t size_     |
+------------------+
         |
         v
+------+    +------+    +------+
| prev |<-->| prev |<-->| prev |
| data |    | data |    | data |
| next |    | next |    | next |
+------+    +------+    +------+
  head                    tail

MyUnorderedMap

+---------------------+
|  MyUnorderedMap     |
|---------------------|     +-------+-------+-------+-------+
| Bucket* buckets_    |---->|   0   |   1   |   2   |   3   |
| size_t bucket_count |     +---+---+---+---+---+---+---+---+
| size_t size_        |         |       |
| float max_load_     |         v       v
+---------------------+     +-----+ +-----+
                            |K1,V1| |K2,V2|
                            +--+--+ +--+--+
                               |       |
                               v       v
                            +-----+ nullptr
                            |K3,V3|
                            +-----+
                               |
                               v
                            nullptr

4.2 Key Components

MyVector

template<typename T, typename Allocator = std::allocator<T>>
class MyVector {
    T* data_ = nullptr;
    size_t size_ = 0;
    size_t capacity_ = 0;
    Allocator alloc_;

public:
    using iterator = T*;
    using const_iterator = const T*;

    iterator begin() { return data_; }
    iterator end() { return data_ + size_; }

    void push_back(const T& value);
    void push_back(T&& value);
    void pop_back();
    iterator insert(iterator pos, const T& value);
    iterator erase(iterator pos);
    void reserve(size_t new_cap);

    T& operator[](size_t i) { return data_[i]; }
    T& at(size_t i);
    size_t size() const { return size_; }
    size_t capacity() const { return capacity_; }
    bool empty() const { return size_ == 0; }
};

MyList

template<typename T>
class MyList {
    struct Node {
        T data;
        Node* prev = nullptr;
        Node* next = nullptr;
    };

    Node* head_ = nullptr;
    Node* tail_ = nullptr;
    size_t size_ = 0;

public:
    class iterator {
        Node* node_;
    public:
        T& operator*() { return node_->data; }
        iterator& operator++() { node_ = node_->next; return *this; }
        iterator& operator--() { node_ = node_->prev; return *this; }
        bool operator==(const iterator& other) { return node_ == other.node_; }
    };

    iterator begin() { return iterator(head_); }
    iterator end() { return iterator(nullptr); }

    void push_front(const T& value);
    void push_back(const T& value);
    iterator insert(iterator pos, const T& value);
    iterator erase(iterator pos);
};

MyUnorderedMap

template<typename K, typename V, typename Hash = std::hash<K>>
class MyUnorderedMap {
    struct Node {
        std::pair<const K, V> kv;
        Node* next = nullptr;
    };

    Node** buckets_ = nullptr;
    size_t bucket_count_ = 0;
    size_t size_ = 0;
    float max_load_factor_ = 1.0f;
    Hash hash_;

public:
    V& operator[](const K& key);
    V& at(const K& key);
    iterator find(const K& key);
    std::pair<iterator, bool> insert(const std::pair<K, V>& kv);
    size_t erase(const K& key);
    void rehash(size_t new_bucket_count);
};

4.3 Data Structures

Container Internal Structure Iterator Type
MyVector Contiguous array Raw pointer (random access)
MyList Doubly-linked nodes Node pointer wrapper (bidirectional)
MyUnorderedMap Array of buckets + linked nodes Node pointer wrapper (forward)

4.4 Algorithm Overview

Vector Growth (push_back)

if size == capacity:
    new_cap = capacity == 0 ? 1 : capacity * 2
    new_data = allocate(new_cap)

    for i in 0 to size:
        construct(new_data + i, move_if_noexcept(data[i]))

    destroy all in old data
    deallocate old data

    data = new_data
    capacity = new_cap

construct(data + size, value)
size++

List Insert

new_node = new Node(value)
new_node->prev = pos.node->prev
new_node->next = pos.node

if pos.node->prev:
    pos.node->prev->next = new_node
else:
    head = new_node

pos.node->prev = new_node
size++
return iterator(new_node)

HashMap Insert

if size / bucket_count > max_load_factor:
    rehash(bucket_count * 2)

bucket_idx = hash(key) % bucket_count

for node in buckets[bucket_idx]:
    if node->key == key:
        return {iterator(node), false}  // Already exists

new_node = new Node{key, value}
new_node->next = buckets[bucket_idx]
buckets[bucket_idx] = new_node
size++
return {iterator(new_node), true}

5. Implementation Guide

5.1 Development Environment Setup

mkdir containers && cd containers
touch my_vector.hpp my_list.hpp my_unordered_map.hpp
touch test_containers.cpp

# Compile with all warnings
g++ -std=c++17 -Wall -Wextra -Wpedantic -o test test_containers.cpp

# With sanitizers
g++ -std=c++17 -Wall -Wextra -fsanitize=address,undefined -o test test_containers.cpp

5.2 Project Structure

containers/
├── include/
│   ├── my_vector.hpp
│   ├── my_list.hpp
│   └── my_unordered_map.hpp
├── tests/
│   ├── test_vector.cpp
│   ├── test_list.cpp
│   └── test_unordered_map.cpp
└── benchmarks/
    └── benchmark.cpp

5.3 The Core Question You’re Answering

“How do I create generic, efficient, and safe data structures that work with any type and any algorithm?”

This decomposes into:

  1. How do I write type-generic code (templates)?
  2. How do I manage memory for dynamic containers (allocators)?
  3. How do I provide a uniform interface for traversal (iterators)?
  4. How do I maintain safety when operations fail (exception safety)?

5.4 Concepts You Must Understand First

Question Book Reference
How do template classes work? C++ Programming Language Ch. 23
What are iterator categories? Effective STL Items 1-4
How does std::allocator work? C++ Programming Language Ch. 34
What is the strong exception guarantee? Exceptional C++ Items 8-17
How does placement new work? C++ Programming Language Ch. 11

5.5 Questions to Guide Your Design

Vector Design

  • What growth factor should you use? (1.5x, 2x, or other?)
  • How do you handle types that throw on copy?
  • What should operator[] return for out-of-bounds?
  • How do you implement insert in the middle efficiently?

List Design

  • How do you handle end() iterator (past the last element)?
  • Should you use a sentinel node?
  • How do you implement splice in O(1)?
  • What happens when you erase the only element?

HashMap Design

  • What hash function to use for strings?
  • How do you handle hash collisions?
  • When do you rehash?
  • What if the user provides a bad hash function?

Iterator Design

  • What traits must your iterator provide?
  • How do you handle const_iterator vs iterator?
  • What happens when container is modified during iteration?
  • How do you make iterators work with standard algorithms?

5.6 Thinking Exercise

Trace through this code:

MyVector<std::string> v;
v.reserve(2);             // capacity = 2, size = 0
v.push_back("hello");     // size = 1
v.push_back("world");     // size = 2
v.push_back("!");         // reallocation happens

// What is capacity after the third push_back?
// What if std::string copy throws during reallocation?

Trace:

  1. reserve(2): allocate space for 2 strings, size=0, capacity=2
  2. push_back("hello"): construct at data[0], size=1
  3. push_back("world"): construct at data[1], size=2, capacity=2 (full)
  4. push_back("!"):
    • Allocate new buffer of capacity 4 (doubled)
    • Move “hello” and “world” to new buffer (using move_if_noexcept)
    • Destroy old strings and deallocate old buffer
    • Construct “!” at position 2
    • size=3, capacity=4

If string copy throws during step 4:

  • Destroy any strings already copied to new buffer
  • Deallocate new buffer
  • Original vector unchanged (strong guarantee)

5.7 Hints in Layers

Hint 1: Starting Point (Conceptual) Start with a minimal vector: just push_back, size, and operator[]. No iterators, no allocators yet. Get that working first.

Hint 2: Next Level (Vector skeleton)

template<typename T>
class MyVector {
    T* data_ = nullptr;
    size_t size_ = 0;
    size_t capacity_ = 0;

public:
    ~MyVector() {
        for (size_t i = 0; i < size_; ++i)
            data_[i].~T();
        ::operator delete(data_);
    }

    void push_back(const T& value) {
        if (size_ == capacity_) {
            size_t new_cap = capacity_ == 0 ? 1 : capacity_ * 2;
            T* new_data = static_cast<T*>(::operator new(new_cap * sizeof(T)));

            for (size_t i = 0; i < size_; ++i)
                new (new_data + i) T(std::move(data_[i]));

            for (size_t i = 0; i < size_; ++i)
                data_[i].~T();
            ::operator delete(data_);

            data_ = new_data;
            capacity_ = new_cap;
        }
        new (data_ + size_) T(value);
        ++size_;
    }

    T& operator[](size_t i) { return data_[i]; }
    size_t size() const { return size_; }
};

Hint 3: Adding Allocator Support

template<typename T, typename Allocator = std::allocator<T>>
class MyVector {
    using AllocTraits = std::allocator_traits<Allocator>;

    T* data_ = nullptr;
    size_t size_ = 0;
    size_t capacity_ = 0;
    Allocator alloc_;

    T* allocate(size_t n) {
        return AllocTraits::allocate(alloc_, n);
    }

    void deallocate(T* p, size_t n) {
        AllocTraits::deallocate(alloc_, p, n);
    }

    template<typename... Args>
    void construct(T* p, Args&&... args) {
        AllocTraits::construct(alloc_, p, std::forward<Args>(args)...);
    }

    void destroy(T* p) {
        AllocTraits::destroy(alloc_, p);
    }
};

Hint 4: Exception-Safe reserve

void reserve(size_t new_cap) {
    if (new_cap <= capacity_) return;

    T* new_data = allocate(new_cap);
    size_t constructed = 0;

    try {
        for (; constructed < size_; ++constructed) {
            construct(new_data + constructed,
                      std::move_if_noexcept(data_[constructed]));
        }
    } catch (...) {
        for (size_t i = 0; i < constructed; ++i) {
            destroy(new_data + i);
        }
        deallocate(new_data, new_cap);
        throw;
    }

    for (size_t i = 0; i < size_; ++i) {
        destroy(data_ + i);
    }
    if (data_) {
        deallocate(data_, capacity_);
    }

    data_ = new_data;
    capacity_ = new_cap;
}

5.8 The Interview Questions They’ll Ask

  1. “What is the amortized complexity of vector::push_back?”
    • O(1) amortized
    • Individual push_back can be O(n) when reallocating
    • But doubling strategy means total cost is O(n) for n pushes
  2. “Why does vector use contiguous memory?”
    • Cache locality: prefetching works well
    • Random access: O(1) by pointer arithmetic
    • Interoperability: can pass data_ to C APIs
  3. “When would you use list over vector?”
    • Frequent insertions/deletions in the middle (with iterator)
    • Never invalidating iterators is required
    • Objects are very large (no copying on reallocation)
  4. “How does unordered_map handle collisions?”
    • Separate chaining: each bucket is a linked list
    • Or open addressing: probe for next empty slot
    • Standard library uses separate chaining
  5. “What is iterator invalidation?”
    • Some operations invalidate existing iterators
    • Vector: push_back may invalidate all; insert/erase invalidates at/after position
    • List: only erase invalidates the erased iterator
    • Map: only erase invalidates the erased iterator

5.9 Books That Will Help

Topic Book Chapter
Templates The C++ Programming Language Chapters 23-25
STL Design Effective STL All
Iterator Concepts C++ Standard Library Chapter 7
Allocators The C++ Programming Language Chapter 34
Exception Safety Exceptional C++ Items 8-17

5.10 Implementation Phases

Phase 1: Basic Vector (Day 1-4)

  • Constructor, destructor
  • push_back (with growth)
  • operator[], at()
  • size(), capacity(), empty()
  • Test: basic operations work

Phase 2: Vector Iterators (Day 5-6)

  • typedef T* as iterator
  • begin(), end()
  • Test: std::sort and std::find work

Phase 3: Vector Full API (Day 7-9)

  • insert, erase
  • reserve, resize
  • Move semantics (push_back with T&&)
  • Copy/move constructors and assignment
  • Test: exception safety

Phase 4: List (Day 10-14)

  • Node struct, head/tail pointers
  • push_front, push_back
  • Bidirectional iterator
  • insert, erase
  • Test: all operations, splice

Phase 5: Unordered Map (Day 15-21)

  • Bucket array with linked lists
  • operator[], at(), find()
  • insert, erase
  • rehash when load factor exceeded
  • Test: correctness and O(1) average

Phase 6: Polish (Day 22-24)

  • Add const_iterator to all
  • Ensure no leaks (Valgrind)
  • Compare performance with std::

5.11 Key Implementation Decisions

Decision Options Recommendation
Vector growth 1.5x vs 2x 2x (simpler, standard)
List sentinel With vs without Without (simpler for learning)
HashMap collision Chaining vs open addressing Chaining (easier)
HashMap bucket count Prime vs power of 2 Power of 2 (faster modulo)
Iterator validity Strict checks vs trust Trust (like STL)

6. Testing Strategy

6.1 Unit Tests

// Vector tests
void testVectorGrowth() {
    MyVector<int> v;
    for (int i = 0; i < 1000; ++i) {
        v.push_back(i);
    }
    assert(v.size() == 1000);
    assert(v.capacity() >= 1000);
    for (int i = 0; i < 1000; ++i) {
        assert(v[i] == i);
    }
}

void testVectorWithStdSort() {
    MyVector<int> v;
    v.push_back(3);
    v.push_back(1);
    v.push_back(2);
    std::sort(v.begin(), v.end());
    assert(v[0] == 1 && v[1] == 2 && v[2] == 3);
}

// List tests
void testListInsert() {
    MyList<int> list;
    list.push_back(1);
    list.push_back(3);
    auto it = list.begin();
    ++it;
    list.insert(it, 2);  // Insert 2 before 3
    // List should be: 1, 2, 3
    it = list.begin();
    assert(*it++ == 1);
    assert(*it++ == 2);
    assert(*it++ == 3);
}

// HashMap tests
void testHashMapBasic() {
    MyUnorderedMap<std::string, int> map;
    map["one"] = 1;
    map["two"] = 2;
    assert(map.size() == 2);
    assert(map["one"] == 1);
    assert(map.at("two") == 2);

    map.erase("one");
    assert(map.find("one") == map.end());
}

6.2 Edge Cases to Test

Container Edge Case Expected
Vector push_back to empty Works, capacity >= 1
Vector erase last element size decreases, valid
Vector insert at begin All elements shifted
List erase only element Empty list, valid
List push_front to empty size 1, head == tail
HashMap many collisions Still O(n) worst case
HashMap rehash during iteration Implementation-defined
All const container Only const methods work

7. Common Pitfalls & Debugging

Problem Symptom Root Cause Fix
Double free Crash Shallow copy Implement copy constructor properly
Iterator invalidation Crash or wrong data Using iterator after push_back Re-obtain iterator after modifications
Memory leak Growing memory Not destroying elements Call destructor before deallocate
Undefined behavior Anything Out of bounds access Check bounds in at()
Hash collision loop Infinite loop Bad equality check Ensure operator== is correct

Debugging Tips

  1. Add bounds checking: In debug mode, check all accesses
  2. Print on construct/destruct: Track object lifetimes
  3. Use Valgrind: Catch leaks and invalid access
  4. Test with throwing types: Verify exception safety
  5. Compare with std: Same operations should give same results

8. Extensions & Challenges

Extension Difficulty Concepts Learned
Small buffer optimization (vector) Medium In-place storage for small containers
Intrusive list Medium Embedding links in elements
Robin Hood hashing Hard Open addressing variant
Custom allocator Medium Pool allocation
Concurrent containers Hard Lock-free or lock-based thread safety

9. Real-World Connections

How the Standard Library Implements These

Container libstdc++ libc++
vector Dynamic array, growth ~2x Similar
list Doubly-linked with sentinel Similar
unordered_map Separate chaining Separate chaining

When to Use Each

Use Case Container Why
Unknown size, random access vector Cache friendly, fast
Frequent middle insertion list O(1) insert
Key-value lookup unordered_map O(1) average
Ordered traversal map (tree) Sorted iteration
Priority queue priority_queue (heap) O(log n) push/pop

10. Resources

Primary References

  • Stroustrup, B. “The C++ Programming Language” - Chapters 23-25, 34
  • Meyers, S. “Effective STL” - All items
  • cppreference: Containers

Online Resources

11. Self-Assessment Checklist

Before considering this project complete, verify:

  • Vector grows correctly (capacity doubles)
  • Vector iterators work with std::sort
  • Vector provides strong exception guarantee for push_back
  • List insert/erase are O(1)
  • List iterators are bidirectional (work with std::reverse)
  • HashMap has O(1) average lookup
  • HashMap rehashes when load factor exceeded
  • All containers: no memory leaks
  • All containers: const versions of methods work
  • Performance comparable to std:: versions

12. Submission / Completion Criteria

This project is complete when:

  1. All functional requirements (F1-F10) are implemented
  2. Example code from section 3.4 works correctly
  3. Iterators work with standard algorithms (sort, find, reverse)
  4. Exception safety maintained (strong for push_back)
  5. Performance within 2x of standard library
  6. No memory leaks (Valgrind clean)
  7. All unit tests pass
  8. You can explain the amortized complexity of vector::push_back

Deliverables:

  • Header files for each container
  • Comprehensive test suite
  • Benchmark comparing to std:: versions
  • Brief writeup explaining design decisions

This project teaches you how the tools you use every day actually work. Understanding container internals helps you choose the right container, debug performance issues, and write your own specialized containers when needed. The patterns here—templates, iterators, allocators—are the foundation of modern C++ library design.