Data Structures, STL & Design Patterns in C++

A curated set of Kent State CS3 lab implementations covering STL containers, STL algorithms, and the classic Gang-of-Four design patterns.

Overview

This repository collects the lab work I wrote for CS34001 (Data Structures, CS3) at Kent State in Spring 2025. The course walks through the C++ Standard Template Library and then through the design patterns from the Gang of Four book. Each folder is a self-contained program or pair of programs, so this is a reference collection rather than one integrated application. Some files started as instructor-provided skeletons that I completed; I have kept the original attribution comments and noted in the wiki where the work is mine.

Contents

Folder	Topic / pattern	What it demonstrates	Wiki
02-word-list	Dynamic array, rule of three	A WordList that counts word occurrences in a file, backed by a hand-grown dynamic array with copy constructor, destructor, and assignment operator	Word-List
03-templated-linked-list	Templated singly linked list	A generic node<T> and Collection<T> with add, remove, copy, assignment, and a Collection<Collection<char>> test	Templated-Linked-List
04-stl-vector-list-move	vector, list, move semantics	Merging course rosters with std::list and std::vector, plus a MovableInt that shows move constructor and move assignment	STL-Vector-List-Move
05-stl-map-set	map, set, multiset	A roster keyed by a custom Student type with operator<, built once with map and once with set	STL-Map-Set
06-stl-algorithms-priority-queue	STL algorithms, priority_queue, multimap	Replacing hand loops with generate, for_each, count_if, accumulate, transform, and the erase-remove idiom, plus a priority_queue and a multimap range example	STL-Algorithms-Priority-Queue
07-hashmap	Custom hash table	A templated hashmap using separate chaining: a vector of buckets, each a list of key/value pairs, with safe insert, erase, indexing, and rehash	Hashmap
08-singleton-template-method	Singleton, Template Method	A Meyers singleton Logger and a Game base class whose playGame fixes the algorithm while subclasses fill in the moves	Singleton-Template-Method
09-bridge-abstract-factory	Bridge, Abstract Factory	A Figure split from its Fill so the two vary independently, and a CarFactory hierarchy that builds Ford and Toyota products	Bridge-Abstract-Factory
10-adapter-state	Adapter, State	A class adapter that fits a LegacyRectangle behind a Square interface, and a process scheduler whose Process changes behavior by swapping state objects	Adapter-State
11-decorator-chain-of-responsibility	Decorator, Chain of Responsibility	A coffee Drink wrapped by Sugar, Cream, and Honey decorators, served by a chain of baristas that pass an order up the line until one can handle it	Decorator-Chain-Of-Responsibility
12-composite-command-memento	Composite, Visitor, Command, Memento, Prototype	A genealogy tree visited recursively, and a text document with undo (Command), checkpoint/rollback (Memento), and redo by cloning (Prototype)	Composite-Command-Memento

Lab mapping

I renamed each folder from its original course lab number to a name the code earns. This table keeps the provenance.

Course lab	Folder	Verified topic
Lab 02	02-word-list	Dynamic array with the rule of three
Lab 03	03-templated-linked-list	Templated node<T> and Collection<T>
Lab 04	04-stl-vector-list-move	vector, list, and move semantics
Lab 05	05-stl-map-set	map, set, multiset with a custom comparator
Lab 06	06-stl-algorithms-priority-queue	<algorithm>, priority_queue, multimap
Lab 07	07-hashmap	Custom hash table with separate chaining
Lab 08	08-singleton-template-method	Singleton, Template Method
Lab 09	09-bridge-abstract-factory	Bridge, Abstract Factory
Lab 10	10-adapter-state	Adapter, State
Lab 11	11-decorator-chain-of-responsibility	Decorator, Chain of Responsibility
Lab 12	12-composite-command-memento	Composite, Visitor, Command, Memento, Prototype

Highlights

A few pieces are worth more than a glance.

Custom hash table with separate chaining (07-hashmap). The hashmap stores a vector of buckets where each bucket is a list of key/value pairs. Insert and erase return a pair<pointer, bool> so the caller learns both the location and whether the operation changed the container. rehash rebuilds the bucket array at a larger size and re-places every element. The wiki page has a diagram of the bucket layout and a walk through a collision.

The design-pattern set (08 through 12). These labs implement Singleton, Template Method, Bridge, Abstract Factory, Adapter, State, Decorator, Chain of Responsibility, Composite, Visitor, Command, Memento, and Prototype. Each wiki page states the pattern's intent, points to the exact classes in my code, and includes a class diagram.

STL map and set with a custom comparator (05-stl-map-set). The Student type defines operator< over last name then first name, which lets std::map and std::set order students with no extra comparator object. The same roster problem is solved twice so the trade-off between the two containers is visible side by side.

Tech Stack

• C++17
• The C++ Standard Template Library: vector, list, map, set, multiset, multimap, queue, priority_queue, deque, <algorithm>, <numeric>
• g++ and GNU Make
• GitHub Actions for continuous integration

Architecture

flowchart TD
    Root["CS3: Data Structures, STL & Design Patterns"]

    Root --> Containers["Containers I built by hand"]
    Root --> STL["STL containers & algorithms"]
    Root --> Patterns["Gang-of-Four design patterns"]

    Containers --> C1["02 word list (dynamic array)"]
    Containers --> C2["03 templated linked list"]
    Containers --> C3["07 hashmap (separate chaining)"]

    STL --> S1["04 vector, list, move semantics"]
    STL --> S2["05 map, set, multiset"]
    STL --> S3["06 algorithms, priority_queue, multimap"]

    Patterns --> P1["08 Singleton, Template Method"]
    Patterns --> P2["09 Bridge, Abstract Factory"]
    Patterns --> P3["10 Adapter, State"]
    Patterns --> P4["11 Decorator, Chain of Responsibility"]
    Patterns --> P5["12 Composite, Visitor, Command, Memento, Prototype"]

Loading

Getting Started

Every folder compiles with g++ and the C++17 standard. Pick a program and build it directly. For example:

# the custom hash table
g++ -std=c++17 07-hashmap/testHashmap.cpp -o testHashmap
./testHashmap

# the decorator + chain-of-responsibility coffee shop
g++ -std=c++17 11-decorator-chain-of-responsibility/drink.cpp -o drink
./drink

The two multi-file labs need their helper translation units on the command line:

# abstract factory: client plus the factory implementation
g++ -std=c++17 09-bridge-abstract-factory/CarTest.cpp \
    09-bridge-abstract-factory/CarFactory.cpp -o cartest
./cartest

Some folders ship a Makefile. In those, make builds the default target and make clean removes it.

Project Structure

cs3-projects/
├── 02-word-list/                          dynamic array, rule of three
├── 03-templated-linked-list/              generic node<T> + Collection<T>
├── 04-stl-vector-list-move/               vector, list, move semantics
├── 05-stl-map-set/                        map, set, custom comparator
├── 06-stl-algorithms-priority-queue/      <algorithm>, priority_queue, multimap
├── 07-hashmap/                            custom hash table, separate chaining
├── 08-singleton-template-method/          Singleton + Template Method
├── 09-bridge-abstract-factory/            Bridge + Abstract Factory
├── 10-adapter-state/                      Adapter + State
├── 11-decorator-chain-of-responsibility/  Decorator + Chain of Responsibility
├── 12-composite-command-memento/          Composite, Visitor, Command, Memento, Prototype
├── .github/workflows/ci.yml               builds every folder on push
├── LICENSE
└── README.md

Roadmap

• Add a short unit test per folder so the CI proves behavior, not just that the code compiles.
• Replace the raw new/delete in the pattern labs with smart pointers and note the change in each wiki page.
• Give the custom hashmap an iterator so it reads more like an STL container.
• Capture sample runs for the interactive programs (the adapter, the coffee shop, the document editor) so the wiki can show input and output together.

Author & Acknowledgments

Brandon Robare. I wrote this for CS34001 (Data Structures, CS3) at Kent State University, Spring 2025. Several programs began as skeletons provided by the instructor, Mikhail Nesterenko, and I have kept his attribution comments in those files. The design-pattern catalog follows Design Patterns: Elements of Reusable Object-Oriented Software by Gamma, Helm, Johnson, and Vlissides.

License

Released under the MIT License. See LICENSE and the wiki for the full reference.