After this lesson, you will be able to: Build a C++ data structure library with hash map, linked list, and binary search tree, fully tested with Google Test or Catch2.
The C++ resume project. Implementing these from scratch proves you understand memory, templates, iterators, and modern C++ idioms.
Build `mystl`, a tiny STL clone.
Three containers, all templated:
1. mystl::HashMap<K, V>, open-addressing or chaining
2. mystl::LinkedList<T>, doubly-linked, with iterators
3. mystl::BST<K, V>, binary search tree, in-order iterator
Each must support:
- Standard ops (insert, find, erase, size, empty)
- Iterators that satisfy std::forward_iterator (or std::bidirectional_iterator for list)
- Move semantics + copy semantics (Rule of Five)
- noexcept where applicable
- Tested with Google Test or Catch2, 90%+ line coverage
Order matters, get one right before the next.
Milestone 1: Project skeleton, CMakeLists, src/, include/, tests/. Set up Catch2 via FetchContent.
Milestone 2: LinkedList<T>, insert/erase/iterator. Pass tsan + asan.
Milestone 3: HashMap<K, V>, start with chaining (vector of LinkedList). Benchmark vs std::unordered_map.
Milestone 4: BST<K, V>, recursive insert/find/erase. In-order iterator.
Milestone 5: Test suite with edge cases (empty, single element, duplicates, large random inserts).
Milestone 6: Add GitHub Actions CI, build on Linux/Mac/Windows with -Wall -Wextra -Werror.
Milestone 7: README with architecture decisions, perf comparison, lessons learned.
Publish to public GitHub. Make it `git clone`-able + buildable with `cmake -B build && cmake --build build && ctest --test-dir build`. Add badges: CI status, code coverage (codecov.io), license. Optional stretch: package for vcpkg or Conan.
Sign in and purchase access to unlock this lesson.