Teaching Notes: Module 08

Key Learning Objectives

• STL containers (vector, list, map, stack, etc.)
• Iterators
• STL algorithms
• When to use which container

---

Exercise 00: easyfind

Key Concept

Generic function to find int in any container.

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

Common Mistakes

1. Not handling “not found” case

   • Return iterator to end, OR throw exception

2. Forgetting typename

   typename T::iterator  // 'typename' required for dependent types

3. Trying to use with map

   • Subject says: don’t handle associative containers
   • map stores pairs, not individual values

---

Exercise 01: Span

Key Concept

Store N integers, find shortest/longest span (distance).

Implementation Hints

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

Common Mistakes

1. Not using STL algorithms

   • Use std::sort, std::min_element, std::max_element

2. Range addition

   // Subject wants: add many numbers at once
   template <typename Iterator>
   void addNumber(Iterator begin, Iterator end);

3. Testing with small data

   • Subject requires testing with 10,000+ numbers

---

Exercise 02: MutantStack

Key Insight

std::stack has a protected member c (the underlying container).

template <typename T>
class MutantStack : public std::stack<T> {
public:
    typedef typename std::stack<T>::container_type::iterator iterator;

    iterator begin() { return this->c.begin(); }
    iterator end() { return this->c.end(); }
};

Common Mistakes

1. Not exposing all iterator types

   • iterator
   • const_iterator
   • reverse_iterator

2. Forgetting this->c

   • Need this-> to access base class protected member

Why This Works

• std::stack is an adapter around a container (default: std::deque)
• The container is accessible via protected member c
• We just expose its iterators

Testing

Replace MutantStack with std::list - output should match (with appropriate method name changes).