Module 08: STL Containers, Iterators, and Algorithms

Download Official Subject PDF

Key Concepts:

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

---

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

---

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