Module 08: STL Containers, Iterators, and Algorithms

Download Official Subject PDF

Prerequisites

Complete Modules 00-07 first. STL containers are built with templates from Module 07.

Key Concepts:

• Containers (vector, list, map, stack, etc.)
• Iterators
• Algorithms
• Function objects (functors)

---

Why This Matters

The STL provides battle-tested data structures so you don’t have to implement them from scratch. Choosing the right container for your problem is crucial for performance.

Real-World Analogy

STL containers are like different storage solutions. A vector is like a row of lockers—fast to access any locker by number. A list is like a chain of paper clips—easy to insert or remove in the middle. A map is like a phone book—find entries by name quickly.

Real-World Analogy

Iterators are like bookmarks. They point to a specific position in a container and can move forward (and sometimes backward). Just as you can use a bookmark in any book, iterators provide a uniform way to traverse any container.

---

Understanding STL Iterator Syntax

This module introduces STL containers and iterators. Here’s the syntax explained:

The ::iterator Syntax

std::vector<int>::iterator it = vec.begin();
std::map<string, int>::iterator it = map.begin();

• ::iterator is a nested type defined inside container classes
• It represents a “position” in the container (like an index, but more general)
• Different containers have different iterator types
• vector<int>::iterator is different from list<int>::iterator

The -> Operator with Iterators

it->first;   // Access key in map iterator
it->second;  // Access value in map iterator

• -> with iterators dereferences the iterator AND accesses a member
• For map iterators, it->first gets the key, it->second gets the value
• Same as (*it).first but more concise
• Use -> when the iterator contains objects with members

The * Operator with Iterators

*it;  // Dereference to get the value

• * with iterators gets the actual element at that position
• For vectors, *it gives the element value
• For lists, *it gives the element value
• For maps, *it gives a pair object (use ->first and ->second instead)

The ++ and -- Operators with Iterators

++it;   // Move to next element
--it;   // Move to previous element

• ++ advances the iterator to the next position
• -- moves the iterator to the previous position
• For bidirectional iterators (list, map, set), both work
• For forward-only iterators, only ++ works
• Pre-increment (++it) is preferred over post-increment (it++) for efficiency

The begin() and end() Methods

it = vec.begin();  // Iterator to first element
it != vec.end();   // Loop condition - end is "past the last"

• begin() returns an iterator to the first element
• end() returns an iterator to “past the last” element (not a valid element!)
• end() acts like a sentinel - you use != end() to check if you’re done
• The range [begin, end) is “half-open” - includes first, excludes last

The typename Keyword with Container Types

typename T::iterator easyfind(T& container, int value);

• typename tells the compiler that T::iterator is a type, not a static member
• Required when writing templates that work with containers
• Without typename, the compiler doesn’t know if iterator is a nested type or a member

The container_type:: Access

typename std::stack<T>::container_type::iterator iterator;

• container_type is a typedef inside std::stack that reveals the underlying container
• :: chains to access nested types: stack<T> -> container_type (which is deque<T>) -> iterator
• Used when inheriting from STL containers to expose their internal types

---

1. STL Overview

Three Components

1. Containers: Store collections of objects
2. Iterators: Access elements in containers
3. Algorithms: Perform operations on containers

#include <vector>      // vector container
#include <algorithm>   // algorithms
#include <iterator>    // iterator utilities

---

2. Sequence Containers

vector - Dynamic Array

#include <vector>

std::vector<int> v;

// Add elements
v.push_back(10);
v.push_back(20);
v.push_back(30);

// Access elements
v[0];           // 10 (no bounds check)
v.at(0);        // 10 (with bounds check)
v.front();      // 10 (first element)
v.back();       // 30 (last element)

// Size
v.size();       // 3
v.empty();      // false
v.capacity();   // Implementation-defined

// Remove
v.pop_back();   // Remove last
v.clear();      // Remove all

// Iterate
for (size_t i = 0; i < v.size(); i++)
    std::cout << v[i] << std::endl;

list - Doubly Linked List

#include <list>

std::list<int> lst;

lst.push_back(10);
lst.push_front(5);   // Can add to front efficiently

lst.front();         // 5
lst.back();          // 10

// No random access!
// lst[0];           // ERROR - list doesn't support []

// Iterate
std::list<int>::iterator it;
for (it = lst.begin(); it != lst.end(); ++it)
    std::cout << *it << std::endl;

deque - Double-Ended Queue

#include <deque>

std::deque<int> dq;

dq.push_back(10);
dq.push_front(5);    // Efficient front insertion
dq[0];               // Random access supported

---

3. Associative Containers

map - Key-Value Pairs (Sorted)

#include <map>

std::map<std::string, int> ages;

// Insert
ages["Alice"] = 25;
ages["Bob"] = 30;
ages.insert(std::make_pair("Charlie", 35));

// Access
ages["Alice"];       // 25
ages.at("Alice");    // 25 (throws if not found)

// Check existence
if (ages.find("David") != ages.end())
    std::cout << "Found" << std::endl;

// Count (0 or 1 for map)
ages.count("Alice"); // 1

// Iterate (sorted by key!)
std::map<std::string, int>::iterator it;
for (it = ages.begin(); it != ages.end(); ++it)
    std::cout << it->first << ": " << it->second << std::endl;

set - Unique Sorted Values

#include <set>

std::set<int> s;

s.insert(10);
s.insert(5);
s.insert(10);  // Ignored - already exists

s.size();      // 2
s.count(10);   // 1
s.find(5);     // Iterator to element

---

4. Container Adapters

stack - LIFO

#include <stack>

std::stack<int> st;

st.push(10);
st.push(20);

st.top();     // 20 (peek)
st.pop();     // Remove top
st.top();     // 10
st.empty();   // false
st.size();    // 1

// NOTE: stack has NO iterators by default!

Stack Internals: container_type and c

std::stack is a container adapter - it wraps another container:

// stack definition (simplified)
template <typename T, typename Container = std::deque<T> >
class stack {
protected:
    Container c;  // The underlying container

public:
    typedef Container container_type;  // Exposes container type

    void push(const T& x) { c.push_back(x); }
    void pop() { c.pop_back(); }
    T& top() { return c.back(); }
    bool empty() const { return c.empty(); }
    size_t size() const { return c.size(); }
};

Key points:

• c: Protected member holding the actual data (default: std::deque<T>)
• container_type: Typedef for the underlying container type
• No iterators: Stack intentionally hides iteration to enforce LIFO

queue - FIFO

#include <queue>

std::queue<int> q;

q.push(10);
q.push(20);

q.front();    // 10 (first in)
q.back();     // 20 (last in)
q.pop();      // Remove front

---

5. Iterators

Types of Iterators

Type	Operations	Example Containers
Input	Read only, single pass	istream
Output	Write only, single pass	ostream
Forward	Read/write, multi-pass	forward_list
Bidirectional	+/-, multi-pass	list, map, set
Random Access	+/-, +n, -n, []	vector, deque

Basic Iterator Usage

std::vector<int> v;
v.push_back(10);
v.push_back(20);
v.push_back(30);

// Iterator declaration
std::vector<int>::iterator it;

// Traverse container
for (it = v.begin(); it != v.end(); ++it) {
    std::cout << *it << std::endl;  // Dereference
}

// Reverse traverse
std::vector<int>::reverse_iterator rit;
for (rit = v.rbegin(); rit != v.rend(); ++rit) {
    std::cout << *rit << std::endl;
}

// Const iterator (read-only)
std::vector<int>::const_iterator cit;
for (cit = v.begin(); cit != v.end(); ++cit) {
    // *cit = 100;  // ERROR - const iterator
    std::cout << *cit << std::endl;
}

---

6. Algorithms

Include Header

#include <algorithm>

Search Algorithms

std::vector<int> v;
// ... fill v ...

// find - linear search
std::vector<int>::iterator it = std::find(v.begin(), v.end(), 42);
if (it != v.end())
    std::cout << "Found at index: " << (it - v.begin()) << std::endl;

// count - count occurrences
int n = std::count(v.begin(), v.end(), 42);

// binary_search - requires sorted container
std::sort(v.begin(), v.end());
bool found = std::binary_search(v.begin(), v.end(), 42);

Sorting

// sort - ascending order
std::sort(v.begin(), v.end());

// sort - custom comparator
bool compareDesc(int a, int b) { return a > b; }
std::sort(v.begin(), v.end(), compareDesc);

Min/Max

std::vector<int>::iterator minIt = std::min_element(v.begin(), v.end());
std::vector<int>::iterator maxIt = std::max_element(v.begin(), v.end());

Transform

std::vector<int> src;
std::vector<int> dst(src.size());

// Apply function to each element
int square(int x) { return x * x; }
std::transform(src.begin(), src.end(), dst.begin(), square);

---

7. Module 08 Exercises

ex00: easyfind

// Find integer in any container
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");
    return it;
}

// Usage
std::vector<int> v;
v.push_back(10);
v.push_back(20);
v.push_back(30);

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

ex01: Span

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);

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

    int shortestSpan() const;
    int longestSpan() const;
};

// Implementation
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");

    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");

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

ex02: MutantStack (Inheriting from Template Containers)

// Make std::stack iterable by inheriting and exposing c
template <typename T>
class MutantStack : public std::stack<T> {
public:
    MutantStack() {}
    MutantStack(const MutantStack& other) : std::stack<T>(other) {}
    MutantStack& operator=(const MutantStack& other) {
        std::stack<T>::operator=(other);
        return *this;
    }
    ~MutantStack() {}

    // Expose underlying container's iterator types using typedef
    // std::stack<T>::container_type is std::deque<T> by default
    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;

    // Forward iterator access to underlying container
    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 access
    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(); }
};

Why This Works:

• std::stack has a protected member c (the underlying container)
• As a derived class, MutantStack can access this->c
• We expose the iterator types using container_type::iterator
• The typename keyword is required because the type depends on template parameter T

Understanding the typename Keyword

// When accessing nested types in templates, use typename:
typedef typename std::stack<T>::container_type::iterator iterator;
//      ^^^^^^^^ Required! Tells compiler this is a type, not a value

// Without typename, compiler might think container_type::iterator is a value

Reverse Iterators (rbegin/rend)

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

// Forward iteration: 1, 2, 3
for (std::vector<int>::iterator it = v.begin(); it != v.end(); ++it)
    std::cout << *it << " ";

// Reverse iteration: 3, 2, 1
for (std::vector<int>::reverse_iterator rit = v.rbegin(); rit != v.rend(); ++rit)
    std::cout << *rit << " ";

lower_bound Algorithm

Finds first position where element could be inserted while maintaining sorted order:

#include <algorithm>

std::vector<int> v;  // Must be sorted!
v.push_back(10);
v.push_back(20);
v.push_back(30);
v.push_back(40);

// Find where 25 would go
std::vector<int>::iterator it = std::lower_bound(v.begin(), v.end(), 25);
// it points to 30 (first element >= 25)

// Insert while maintaining sorted order
v.insert(it, 25);  // v is now: 10, 20, 25, 30, 40

// If element exists, lower_bound returns iterator to it
it = std::lower_bound(v.begin(), v.end(), 20);
// it points to 20

lower_bound vs upper_bound

std::vector<int> v = {10, 20, 20, 20, 30};

std::lower_bound(v.begin(), v.end(), 20);  // Points to first 20
std::upper_bound(v.begin(), v.end(), 20);  // Points to 30 (first > 20)

---

8. Container Selection Guide

Need	Container
Fast random access	vector, deque
Fast front/back insertion	deque, list
Fast middle insertion	list
Sorted unique keys	set
Key-value pairs	map
LIFO operations	stack
FIFO operations	queue

---

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 (dereferencing end() is invalid)
}

// 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

---

Quick Reference

// Vector operations
v.push_back(x);    v.pop_back();
v[i];              v.at(i);
v.begin();         v.end();
v.size();          v.empty();

// Map operations
m[key] = value;    m.at(key);
m.find(key);       m.count(key);
m.insert(pair);    m.erase(key);

// Algorithms
std::find(begin, end, value);
std::sort(begin, end);
std::count(begin, end, value);
std::min_element(begin, end);
std::max_element(begin, end);

---

Related Concepts

Continue your C++ journey:

• Previous: Module 07: Templates - Review how STL is built
• Next: Module 09: STL Practical - Apply STL to real problems

Key Terms from This Module

Visit the Glossary for definitions of:

• Container
• Iterator