Module 08 Tutorial

Prerequisites: Review Module 08 Concepts first.

This module introduces the Standard Template Library (STL). You’ll work with containers, iterators, and algorithms - the building blocks of efficient C++ programming.

---

Exercise 00: Easy Find

Subject Analysis

Create a function template easyfind that:

• Takes a container of integers (type T)
• Takes an integer value to search for
• Returns an iterator to the found element
• Handles the “not found” case appropriately

Key constraints:

• Works with any sequence container (vector, list, deque)
• Does NOT need to work with associative containers (map, set)
• Subject leaves “not found” handling to your discretion

Approach Strategy

Think before coding:

1. What containers must it work with?

   • std::vector<int>
   • std::list<int>
   • std::deque<int>
   • NOT std::map (stores pairs, not plain integers)

2. What STL algorithm should we use?

   • std::find(begin, end, value) - returns iterator to element or end()

3. How to handle “not found”?

   • Option A: Return container.end() (caller checks)
   • Option B: Throw exception (cleaner for this exercise)

4. Why typename T::iterator?

   • T::iterator is a “dependent type” (depends on template parameter T)
   • Compiler needs typename hint to parse it correctly

Progressive Code Building

Stage 1: Basic structure with std::find

easyfind.hpp

#ifndef EASYFIND_HPP
#define EASYFIND_HPP

#include <algorithm>  // std::find

template <typename T>
typename T::iterator easyfind(T& container, int value) {
    return std::find(container.begin(), container.end(), value);
}

#endif

Stage 2: Add exception for “not found”

easyfind.hpp - with exception

#include <algorithm>
#include <stdexcept>

template <typename T>
typename T::iterator easyfind(T& container, int value) {
    typename T::iterator it = std::find(container.begin(), container.end(), value);
    if (it == container.end()) {
        throw std::runtime_error("Value not found in container");
    }
    return it;
}

Line-by-Line Explanation

The typename keyword:

Code	Why
typename T::iterator	Tells compiler that T::iterator is a type, not a static member
Without typename	Compiler error: “expected ’;’ before ‘it’”

// WRONG: Compiler thinks T::iterator is a value
T::iterator it = ...;  // Error!

// RIGHT: Explicitly mark as type
typename T::iterator it = ...;  // OK

std::find behavior:

Found	Returns
Yes	Iterator pointing to the element
No	Iterator equal to container.end()

std::vector<int> v;
v.push_back(1);
v.push_back(2);
v.push_back(3);

std::vector<int>::iterator it = std::find(v.begin(), v.end(), 2);
// it now points to the element with value 2

it = std::find(v.begin(), v.end(), 99);
// it == v.end() (not found)

Common Pitfalls

1. Forgetting typename:

// WRONG: Compilation error
template <typename T>
T::iterator easyfind(T& container, int value) { ... }

// RIGHT: Mark dependent type
template <typename T>
typename T::iterator easyfind(T& container, int value) { ... }

2. Taking container by value:

// WRONG: Copies entire container, iterator points to copy
template <typename T>
typename T::iterator easyfind(T container, int value) { ... }

// RIGHT: Reference to original container
template <typename T>
typename T::iterator easyfind(T& container, int value) { ... }

3. Not handling “not found”:

// PROBLEMATIC: Caller might dereference end()
template <typename T>
typename T::iterator easyfind(T& container, int value) {
    return std::find(container.begin(), container.end(), value);
}

int main() {
    std::vector<int> v;
    std::cout << *easyfind(v, 42);  // UB if not found!
}

// BETTER: Throw exception
if (it == container.end())
    throw std::runtime_error("Not found");

4. Trying with associative containers:

// WON'T WORK as expected
std::map<int, std::string> m;
m[1] = "one";
easyfind(m, 1);  // std::find looks for std::pair<int,string>, not int!

Testing Tips

main.cpp

#include <iostream>
#include <vector>
#include <list>
#include <deque>
#include "easyfind.hpp"

int main() {
    // Test with vector
    std::vector<int> vec;
    vec.push_back(1);
    vec.push_back(2);
    vec.push_back(3);
    vec.push_back(4);
    vec.push_back(5);

    try {
        std::vector<int>::iterator it = easyfind(vec, 3);
        std::cout << "Found in vector: " << *it << std::endl;
    } catch (std::exception& e) {
        std::cout << "Vector: " << e.what() << std::endl;
    }

    try {
        easyfind(vec, 99);
    } catch (std::exception& e) {
        std::cout << "Vector (99): " << e.what() << std::endl;
    }

    // Test with list
    std::list<int> lst;
    lst.push_back(10);
    lst.push_back(20);
    lst.push_back(30);

    try {
        std::list<int>::iterator it = easyfind(lst, 20);
        std::cout << "Found in list: " << *it << std::endl;
    } catch (std::exception& e) {
        std::cout << "List: " << e.what() << std::endl;
    }

    // Test with deque
    std::deque<int> deq;
    deq.push_back(100);
    deq.push_front(50);

    try {
        std::deque<int>::iterator it = easyfind(deq, 50);
        std::cout << "Found in deque: " << *it << std::endl;
    } catch (std::exception& e) {
        std::cout << "Deque: " << e.what() << std::endl;
    }

    return 0;
}

Final Code

easyfind.hpp

#ifndef EASYFIND_HPP
#define EASYFIND_HPP

#include <algorithm>
#include <stdexcept>

template <typename T>
typename T::iterator easyfind(T& container, int value) {
    typename T::iterator it = std::find(container.begin(), container.end(), value);
    if (it == container.end()) {
        throw std::runtime_error("Value not found in container");
    }
    return it;
}

#endif

---

Exercise 01: Span

Subject Analysis

Create a Span class that:

• Stores up to N integers (N given in constructor)
• addNumber(int) - add a single number
• addNumber(begin, end) - add a range of numbers
• shortestSpan() - return smallest difference between any two numbers
• longestSpan() - return largest difference between any two numbers
• Throws exceptions when appropriate

Key constraints:

• Must test with minimum 10,000 numbers
• Use STL containers internally
• Range addition required (iterators)

Approach Strategy

Think before coding:

1. Which container internally?

   • std::vector<int> - dynamic size, fast random access, efficient sorting

2. How to find shortest span?

   • Sort the numbers
   • Shortest span is between adjacent elements
   • Compare each pair of neighbors

3. How to find longest span?

   • Simply max - min
   • No need to sort

4. What exceptions to throw?

   • addNumber: Span is full
   • shortestSpan/longestSpan: Less than 2 numbers

Progressive Code Building

Stage 1: Basic class structure

Span.hpp

#ifndef SPAN_HPP
#define SPAN_HPP

#include <vector>
#include <stdexcept>

class Span {
private:
    std::vector<int> _numbers;
    unsigned int     _maxSize;

public:
    Span(unsigned int n);
    Span(const Span& other);
    Span& operator=(const Span& other);
    ~Span();

    void addNumber(int n);
    int shortestSpan() const;
    int longestSpan() const;
};

#endif

Stage 2: Basic operations

Span.cpp

#include "Span.hpp"
#include <algorithm>

Span::Span(unsigned int n) : _maxSize(n) {}

Span::Span(const Span& other) : _numbers(other._numbers), _maxSize(other._maxSize) {}

Span& Span::operator=(const Span& other) {
    if (this != &other) {
        _numbers = other._numbers;
        _maxSize = other._maxSize;
    }
    return *this;
}

Span::~Span() {}

void Span::addNumber(int n) {
    if (_numbers.size() >= _maxSize) {
        throw std::runtime_error("Span is full");
    }
    _numbers.push_back(n);
}

Stage 3: Span calculations

Span.cpp - spans

int Span::shortestSpan() const {
    if (_numbers.size() < 2) {
        throw std::runtime_error("Not enough numbers for span");
    }

    // Sort a copy
    std::vector<int> sorted = _numbers;
    std::sort(sorted.begin(), sorted.end());

    // Find minimum difference between adjacent elements
    int minSpan = sorted[1] - sorted[0];
    for (size_t i = 2; i < sorted.size(); i++) {
        int span = sorted[i] - sorted[i - 1];
        if (span < minSpan) {
            minSpan = span;
        }
    }
    return minSpan;
}

int Span::longestSpan() const {
    if (_numbers.size() < 2) {
        throw std::runtime_error("Not enough numbers for span");
    }

    int min = *std::min_element(_numbers.begin(), _numbers.end());
    int max = *std::max_element(_numbers.begin(), _numbers.end());
    return max - min;
}

Stage 4: Range addition (template member)

Span.hpp - range addition

class Span {
    // ... existing code ...

public:
    // Template member function for range addition
    template <typename Iterator>
    void addNumber(Iterator begin, Iterator end) {
        while (begin != end) {
            addNumber(*begin);  // Reuse single-add (includes full check)
            ++begin;
        }
    }
};

Line-by-Line Explanation

Why sort for shortest span?

// Unsorted: [5, 1, 9, 3, 7]
// All pairs: (5,1)=4, (5,9)=4, (5,3)=2, (5,7)=2, (1,9)=8, ...
// O(n²) comparisons!

// Sorted: [1, 3, 5, 7, 9]
// Only check neighbors: (1,3)=2, (3,5)=2, (5,7)=2, (7,9)=2
// O(n log n) sort + O(n) scan

min_element and max_element:

Algorithm	Returns
std::min_element(begin, end)	Iterator to smallest element
std::max_element(begin, end)	Iterator to largest element

std::vector<int> v;
v.push_back(5);
v.push_back(1);
v.push_back(9);

int min = *std::min_element(v.begin(), v.end());  // 1
int max = *std::max_element(v.begin(), v.end());  // 9

Common Pitfalls

1. Modifying original for shortest span:

// WRONG: Sorts the actual stored numbers
int Span::shortestSpan() const {
    std::sort(_numbers.begin(), _numbers.end());  // Modifies _numbers!
}

// RIGHT: Sort a copy
int Span::shortestSpan() const {
    std::vector<int> sorted = _numbers;  // Copy
    std::sort(sorted.begin(), sorted.end());  // Sort copy
}

2. No range addition:

// WRONG: Subject requires adding many numbers at once
// Only having addNumber(int n)

// RIGHT: Template for any iterator type
template <typename Iterator>
void addNumber(Iterator begin, Iterator end);

3. Not testing with large data:

// WRONG: Only testing with 5 numbers
Span sp(5);

// RIGHT: Subject requires 10,000+
Span sp(10000);
for (int i = 0; i < 10000; i++) {
    sp.addNumber(i);
}

4. Integer overflow in span calculation:

// POTENTIAL ISSUE with extreme values
int span = sorted[i] - sorted[i - 1];  // Could overflow

// For safety, could use unsigned or long
// But for this exercise, int is typically sufficient

Testing Tips

main.cpp

#include <iostream>
#include <cstdlib>
#include "Span.hpp"

int main() {
    // Basic test from subject
    Span sp = Span(5);
    sp.addNumber(6);
    sp.addNumber(3);
    sp.addNumber(17);
    sp.addNumber(9);
    sp.addNumber(11);

    std::cout << "Shortest: " << sp.shortestSpan() << std::endl;  // 2
    std::cout << "Longest: " << sp.longestSpan() << std::endl;    // 14

    // Test exceptions
    try {
        sp.addNumber(42);  // Should throw - full
    } catch (std::exception& e) {
        std::cout << "Full: " << e.what() << std::endl;
    }

    Span empty(5);
    try {
        empty.shortestSpan();  // Should throw - not enough
    } catch (std::exception& e) {
        std::cout << "Empty: " << e.what() << std::endl;
    }

    // Large test (10,000+ numbers)
    Span big(10000);
    std::vector<int> manyNumbers;
    for (int i = 0; i < 10000; i++) {
        manyNumbers.push_back(i);
    }
    big.addNumber(manyNumbers.begin(), manyNumbers.end());

    std::cout << "Big shortest: " << big.shortestSpan() << std::endl;  // 1
    std::cout << "Big longest: " << big.longestSpan() << std::endl;    // 9999

    return 0;
}

Test bash script:

c++ -Wall -Wextra -Werror -std=c++98 main.cpp Span.cpp -o span
./span

# Expected:
# Shortest: 2
# Longest: 14
# Full: Span is full
# Empty: Not enough numbers for span
# Big shortest: 1
# Big longest: 9999

Final Code

Span.hpp

#ifndef SPAN_HPP
#define SPAN_HPP

#include <vector>
#include <stdexcept>

class Span {
private:
    std::vector<int> _numbers;
    unsigned int     _maxSize;

public:
    Span(unsigned int n);
    Span(const Span& other);
    Span& operator=(const Span& other);
    ~Span();

    void addNumber(int n);
    int shortestSpan() const;
    int longestSpan() const;

    template <typename Iterator>
    void addNumber(Iterator begin, Iterator end) {
        while (begin != end) {
            addNumber(*begin);
            ++begin;
        }
    }
};

#endif

Span.cpp

#include "Span.hpp"
#include <algorithm>

Span::Span(unsigned int n) : _maxSize(n) {}

Span::Span(const Span& other)
    : _numbers(other._numbers), _maxSize(other._maxSize) {}

Span& Span::operator=(const Span& other) {
    if (this != &other) {
        _numbers = other._numbers;
        _maxSize = other._maxSize;
    }
    return *this;
}

Span::~Span() {}

void Span::addNumber(int n) {
    if (_numbers.size() >= _maxSize) {
        throw std::runtime_error("Span is full");
    }
    _numbers.push_back(n);
}

int Span::shortestSpan() const {
    if (_numbers.size() < 2) {
        throw std::runtime_error("Not enough numbers for span");
    }

    std::vector<int> sorted = _numbers;
    std::sort(sorted.begin(), sorted.end());

    int minSpan = sorted[1] - sorted[0];
    for (size_t i = 2; i < sorted.size(); i++) {
        int span = sorted[i] - sorted[i - 1];
        if (span < minSpan) {
            minSpan = span;
        }
    }
    return minSpan;
}

int Span::longestSpan() const {
    if (_numbers.size() < 2) {
        throw std::runtime_error("Not enough numbers for span");
    }

    int min = *std::min_element(_numbers.begin(), _numbers.end());
    int max = *std::max_element(_numbers.begin(), _numbers.end());
    return max - min;
}

---

Exercise 02: Mutated Abomination

Subject Analysis

Create MutantStack that:

• Inherits from std::stack
• Adds iterator support (begin, end, rbegin, rend)
• Behaves exactly like a stack but can be iterated

Key insight: std::stack is a container adapter. It wraps another container (default: std::deque) and restricts its interface. The underlying container is accessible via protected member c.

Approach Strategy

Think before coding:

1. What is std::stack internally?

   template <typename T, typename Container = std::deque<T>>
   class stack {
   protected:
       Container c;  // The underlying container!
   public:
       void push(const T& val) { c.push_back(val); }
       void pop() { c.pop_back(); }
       T& top() { return c.back(); }
       // ...
   };

2. How to add iterators?

   • Access the protected member c
   • Expose its iterators through our public interface

3. What iterator types do we need?

   • iterator - forward iteration
   • const_iterator - const forward iteration
   • reverse_iterator - backward iteration
   • const_reverse_iterator - const backward iteration

Progressive Code Building

Stage 1: Basic inheritance

MutantStack.hpp

#ifndef MUTANTSTACK_HPP
#define MUTANTSTACK_HPP

#include <stack>

template <typename T>
class MutantStack : public std::stack<T> {
public:
    MutantStack();
    MutantStack(const MutantStack& other);
    MutantStack& operator=(const MutantStack& other);
    ~MutantStack();
};

#endif

Stage 2: Implement OCF

MutantStack.hpp - OCF

template <typename T>
MutantStack<T>::MutantStack() : std::stack<T>() {}

template <typename T>
MutantStack<T>::MutantStack(const MutantStack& other) : std::stack<T>(other) {}

template <typename T>
MutantStack<T>& MutantStack<T>::operator=(const MutantStack& other) {
    std::stack<T>::operator=(other);
    return *this;
}

template <typename T>
MutantStack<T>::~MutantStack() {}

Stage 3: Add iterator types

MutantStack.hpp - typedefs

template <typename T>
class MutantStack : public std::stack<T> {
public:
    // Type aliases for iterators
    typedef typename std::stack<T>::container_type::iterator iterator;
    typedef typename std::stack<T>::container_type::const_iterator const_iterator;
    typedef typename std::stack<T>::container_type::reverse_iterator reverse_iterator;
    typedef typename std::stack<T>::container_type::const_reverse_iterator const_reverse_iterator;

    // ... rest of class
};

Stage 4: Add iterator methods

MutantStack.hpp - iterators

// Access underlying container's iterators
iterator begin() { return this->c.begin(); }
iterator end() { return this->c.end(); }
const_iterator begin() const { return this->c.begin(); }
const_iterator end() const { return this->c.end(); }
reverse_iterator rbegin() { return this->c.rbegin(); }
reverse_iterator rend() { return this->c.rend(); }
const_reverse_iterator rbegin() const { return this->c.rbegin(); }
const_reverse_iterator rend() const { return this->c.rend(); }

Line-by-Line Explanation

Understanding container_type:

Expression	Meaning
std::stack<T>	The stack class template
std::stack<T>::container_type	The underlying container type (default: std::deque<T>)
container_type::iterator	Iterator type of that container

// std::stack is defined roughly as:
template <typename T, typename Container = std::deque<T>>
class stack {
public:
    typedef Container container_type;  // Exposes container type
protected:
    Container c;  // The actual container instance
};

Why this->c?

// Without 'this->', compiler doesn't look in base class
iterator begin() { return c.begin(); }  // May fail to compile

// With 'this->', explicitly tells compiler to look in base class
iterator begin() { return this->c.begin(); }  // Always works

Why typedef typename?

// container_type::iterator is a dependent type
// Must use 'typename' to tell compiler it's a type

// WRONG
typedef std::stack<T>::container_type::iterator iterator;

// RIGHT
typedef typename std::stack<T>::container_type::iterator iterator;

Common Pitfalls

1. Forgetting typename in typedef:

// WRONG: Compilation error
typedef std::stack<T>::container_type::iterator iterator;

// RIGHT: typename required for dependent type
typedef typename std::stack<T>::container_type::iterator iterator;

2. Forgetting this-> for c:

// WRONG: In some compilers/standards
iterator begin() { return c.begin(); }

// RIGHT: Always works
iterator begin() { return this->c.begin(); }

3. Missing const versions:

// WRONG: Only non-const iterators
iterator begin() { return this->c.begin(); }

// RIGHT: Both const and non-const
iterator begin() { return this->c.begin(); }
const_iterator begin() const { return this->c.begin(); }

4. Not testing comparison with std::list:

// Subject requires: output should be same as std::list
// (with appropriate method name changes: push_back -> push, etc.)

Testing Tips

main.cpp

#include <iostream>
#include <list>
#include "MutantStack.hpp"

int main() {
    // Test from subject
    MutantStack<int> mstack;

    mstack.push(5);
    mstack.push(17);

    std::cout << "Top: " << mstack.top() << std::endl;

    mstack.pop();

    std::cout << "Size: " << mstack.size() << std::endl;

    mstack.push(3);
    mstack.push(5);
    mstack.push(737);
    mstack.push(0);

    MutantStack<int>::iterator it = mstack.begin();
    MutantStack<int>::iterator ite = mstack.end();

    ++it;
    --it;

    std::cout << "Stack contents:" << std::endl;
    while (it != ite) {
        std::cout << *it << std::endl;
        ++it;
    }

    // Test copy
    std::stack<int> s(mstack);

    // Compare with std::list
    std::cout << "\n--- std::list comparison ---" << std::endl;
    std::list<int> lst;

    lst.push_back(5);
    lst.push_back(17);

    std::cout << "Back: " << lst.back() << std::endl;

    lst.pop_back();

    std::cout << "Size: " << lst.size() << std::endl;

    lst.push_back(3);
    lst.push_back(5);
    lst.push_back(737);
    lst.push_back(0);

    std::list<int>::iterator lit = lst.begin();
    std::list<int>::iterator lite = lst.end();

    std::cout << "List contents:" << std::endl;
    while (lit != lite) {
        std::cout << *lit << std::endl;
        ++lit;
    }

    return 0;
}

Test reverse iterators:

// Reverse iteration
MutantStack<int>::reverse_iterator rit = mstack.rbegin();
MutantStack<int>::reverse_iterator rite = mstack.rend();

std::cout << "Reversed:" << std::endl;
while (rit != rite) {
    std::cout << *rit << std::endl;
    ++rit;
}

Final Code

MutantStack.hpp

#ifndef MUTANTSTACK_HPP
#define MUTANTSTACK_HPP

#include <stack>

template <typename T>
class MutantStack : public std::stack<T> {
public:
    MutantStack();
    MutantStack(const MutantStack& other);
    MutantStack& operator=(const MutantStack& other);
    ~MutantStack();

    // Iterator types
    typedef typename std::stack<T>::container_type::iterator iterator;
    typedef typename std::stack<T>::container_type::const_iterator const_iterator;
    typedef typename std::stack<T>::container_type::reverse_iterator reverse_iterator;
    typedef typename std::stack<T>::container_type::const_reverse_iterator const_reverse_iterator;

    // Iterator accessors
    iterator begin();
    iterator end();
    const_iterator begin() const;
    const_iterator end() const;
    reverse_iterator rbegin();
    reverse_iterator rend();
    const_reverse_iterator rbegin() const;
    const_reverse_iterator rend() const;
};

// OCF Implementation
template <typename T>
MutantStack<T>::MutantStack() : std::stack<T>() {}

template <typename T>
MutantStack<T>::MutantStack(const MutantStack& other) : std::stack<T>(other) {}

template <typename T>
MutantStack<T>& MutantStack<T>::operator=(const MutantStack& other) {
    std::stack<T>::operator=(other);
    return *this;
}

template <typename T>
MutantStack<T>::~MutantStack() {}

// Iterator methods
template <typename T>
typename MutantStack<T>::iterator MutantStack<T>::begin() {
    return this->c.begin();
}

template <typename T>
typename MutantStack<T>::iterator MutantStack<T>::end() {
    return this->c.end();
}

template <typename T>
typename MutantStack<T>::const_iterator MutantStack<T>::begin() const {
    return this->c.begin();
}

template <typename T>
typename MutantStack<T>::const_iterator MutantStack<T>::end() const {
    return this->c.end();
}

template <typename T>
typename MutantStack<T>::reverse_iterator MutantStack<T>::rbegin() {
    return this->c.rbegin();
}

template <typename T>
typename MutantStack<T>::reverse_iterator MutantStack<T>::rend() {
    return this->c.rend();
}

template <typename T>
typename MutantStack<T>::const_reverse_iterator MutantStack<T>::rbegin() const {
    return this->c.rbegin();
}

template <typename T>
typename MutantStack<T>::const_reverse_iterator MutantStack<T>::rend() const {
    return this->c.rend();
}

#endif

main.cpp

#include <iostream>
#include <list>
#include "MutantStack.hpp"

int main() {
    MutantStack<int> mstack;

    mstack.push(5);
    mstack.push(17);
    std::cout << mstack.top() << std::endl;
    mstack.pop();
    std::cout << mstack.size() << std::endl;

    mstack.push(3);
    mstack.push(5);
    mstack.push(737);
    mstack.push(0);

    MutantStack<int>::iterator it = mstack.begin();
    MutantStack<int>::iterator ite = mstack.end();

    ++it;
    --it;
    while (it != ite) {
        std::cout << *it << std::endl;
        ++it;
    }

    std::stack<int> s(mstack);
    return 0;
}

---

Module 08 Summary: STL

Concept	Key Point
Containers	vector, list, deque, stack, map, set
Iterators	Pointers to container elements
Algorithms	find, sort, min_element, max_element
typename	Required for dependent types in templates

When to use which container:

Container	Best For
vector	Random access, contiguous memory
list	Frequent insertions/deletions in middle
deque	Fast insertion at both ends
stack	LIFO operations only
map	Key-value pairs with fast lookup
set	Unique elements with fast lookup