📝 Lesson 16: Standard Template Library

What is the STL?

The Standard Template Library is like a well-equipped kitchen - it has all the tools (containers), techniques (algorithms), and helpers (iterators) you need to cook up any program efficiently!

STL Containers: Data Storage Solutions

STL containers are like different types of storage boxes - each designed for specific needs!

Vector: The Workhorse Container

Vector is like a stretchy array - it grows as needed but keeps everything in a neat line!

Vector Examples

#include <vector>
#include <algorithm>
#include <iostream>
using namespace std;

int main() {
    // Creating and initializing vectors
    vector<int> v1;                      // Empty vector
    vector<int> v2(5);                   // 5 elements, value-initialized to 0
    vector<int> v3(5, 10);              // 5 elements, all set to 10
    vector<int> v4 = {1, 2, 3, 4, 5};   // Initializer list

    // Adding elements
    v1.push_back(10);
    v1.push_back(20);
    v1.push_back(30);

    // Accessing elements
    cout << "First: " << v1[0] << endl;           // No bounds check
    cout << "Second: " << v1.at(1) << endl;       // With bounds check
    cout << "Last: " << v1.back() << endl;

    // Size and capacity
    cout << "Size: " << v1.size() << endl;
    cout << "Capacity: " << v1.capacity() << endl;
    v1.reserve(100);  // Reserve space for 100 elements

    // Iterating
    for (int val : v1) {
        cout << val << " ";
    }

    // Using iterators
    for (auto it = v1.begin(); it != v1.end(); ++it) {
        *it *= 2;  // Double each element
    }

    // Algorithms
    sort(v4.begin(), v4.end());                    // Sort ascending
    sort(v4.rbegin(), v4.rend());                 // Sort descending

    auto it = find(v4.begin(), v4.end(), 3);      // Find element
    if (it != v4.end()) {
        cout << "Found at position: " << distance(v4.begin(), it) << endl;
    }

    // Removing elements
    v4.pop_back();                                 // Remove last
    v4.erase(v4.begin() + 2);                     // Remove at index 2
    v4.erase(remove(v4.begin(), v4.end(), 3), v4.end()); // Remove all 3s

    return 0;
}

Modern note (C++20): You can drop the begin()/end() pairs entirely with the std::ranges versions — ranges::sort(v4) and ranges::find(v4, 3) — which are harder to misuse (no chance of mismatched iterators from different containers). We use them throughout the Modern STL Features section below.

Container Comparison

Choosing the right container is like picking the right tool for the job!

Maps and Sets: Associative Containers

Maps are like dictionaries - look up values by key. Sets are like exclusive clubs - each member is unique!

Map and Set Examples

// Map example - Phone book
map<string, string> phoneBook;

// Insert methods
phoneBook["Alice"] = "555-1234";
phoneBook.insert({"Bob", "555-5678"});
phoneBook.insert(make_pair("Charlie", "555-9012"));

// Access and check
if (phoneBook.find("Alice") != phoneBook.end()) {
    cout << "Alice's number: " << phoneBook["Alice"] << endl;
}

// Safe access with at()
try {
    cout << phoneBook.at("David") << endl;  // Throws if not found
} catch (const out_of_range& e) {
    cout << "David not found" << endl;
}

// Iterate over map (sorted by key)
for (const auto& [name, number] : phoneBook) {
    cout << name << ": " << number << endl;
}

// Set example - Unique values
set<int> uniqueNumbers = {5, 2, 8, 2, 9, 1, 5};  // Duplicates removed
cout << "Set size: " << uniqueNumbers.size() << endl;  // 5

// Set operations
uniqueNumbers.insert(3);
uniqueNumbers.erase(2);

// Check if exists
if (uniqueNumbers.count(5) > 0) {
    cout << "5 is in the set" << endl;
}

// Multiset - allows duplicates
multiset<int> scores = {85, 90, 85, 75, 90, 85};
cout << "Count of 85: " << scores.count(85) << endl;  // 3

// Unordered map - Hash table
unordered_map<string, int> wordCount;
string text = "the quick brown fox jumps over the lazy dog";
stringstream ss(text);
string word;
while (ss >> word) {
    wordCount[word]++;
}

// Custom comparator for set
struct Person {
    string name;
    int age;
};

auto compareByAge = [](const Person& a, const Person& b) {
    return a.age < b.age;
};

set<Person, decltype(compareByAge)> people(compareByAge);
people.insert({"Alice", 30});
people.insert({"Bob", 25});
people.insert({"Charlie", 35});

Modern note (C++20): For a simple "is this key present?" check, prefer phoneBook.contains("Alice") over the older find(...) != end() or count(...) > 0 patterns above — it returns a bool directly and reads more clearly. When iterating a map, reach for structured bindings (for (const auto& [key, value] : m)) as shown, and pass string keys as std::string_view where you only need to read them to avoid needless copies.

STL Algorithms: Ready-Made Solutions

STL algorithms are like kitchen appliances - they do common tasks efficiently so you don't have to reinvent the wheel!

Algorithm Examples

vector<int> nums = {5, 2, 8, 1, 9, 3, 7, 4, 6};

// Sorting algorithms
sort(nums.begin(), nums.end());                    // Ascending
sort(nums.begin(), nums.end(), greater<int>());   // Descending

// Partial sort - only first 3 elements sorted
partial_sort(nums.begin(), nums.begin() + 3, nums.end());

// Find algorithms
auto it = find(nums.begin(), nums.end(), 5);
if (it != nums.end()) {
    cout << "Found 5 at position " << distance(nums.begin(), it) << endl;
}

// Find first even number
auto even = find_if(nums.begin(), nums.end(),
    [](int n) { return n % 2 == 0; });

// Count algorithms
int count5 = count(nums.begin(), nums.end(), 5);
int evens = count_if(nums.begin(), nums.end(),
    [](int n) { return n % 2 == 0; });

// Transform algorithm
vector<int> doubled;
transform(nums.begin(), nums.end(), back_inserter(doubled),
    [](int n) { return n * 2; });

// Accumulate (sum)
int sum = accumulate(nums.begin(), nums.end(), 0);
int product = accumulate(nums.begin(), nums.end(), 1, multiplies<int>());

// Copy with condition
vector<int> evensOnly;
copy_if(nums.begin(), nums.end(), back_inserter(evensOnly),
    [](int n) { return n % 2 == 0; });

// Remove elements (erase-remove idiom)
nums.erase(remove_if(nums.begin(), nums.end(),
    [](int n) { return n < 5; }), nums.end());

// Binary search (requires sorted container)
sort(nums.begin(), nums.end());
bool found = binary_search(nums.begin(), nums.end(), 5);

// Min/Max algorithms
auto minmax = minmax_element(nums.begin(), nums.end());
cout << "Min: " << *minmax.first << ", Max: " << *minmax.second << endl;

// Permutations
vector<int> perm = {1, 2, 3};
do {
    for (int n : perm) cout << n << " ";
    cout << endl;
} while (next_permutation(perm.begin(), perm.end()));

Modern note (C++20): Nearly every algorithm above has a std::ranges:: counterpart in <algorithm> that takes the whole container instead of an iterator pair — ranges::sort(nums), ranges::count_if(nums, pred), ranges::find(nums, 5). They eliminate a whole class of bugs (passing begin() of one container with end() of another) and compose cleanly with the lazy views shown in the Modern STL Features section.

Iterators: The Bridge Between Containers and Algorithms

Iterators are like cursors or pointers that know how to navigate through containers - they're the universal remote control for STL!

Iterator Usage

// Basic iterator usage
vector<int> v = {1, 2, 3, 4, 5};

// Iterator types
vector<int>::iterator it = v.begin();
vector<int>::const_iterator cit = v.cbegin();
vector<int>::reverse_iterator rit = v.rbegin();

// Traversing with iterators
for (auto it = v.begin(); it != v.end(); ++it) {
    *it *= 2;  // Double each element
}

// Const iterator (read-only)
for (auto cit = v.cbegin(); cit != v.cend(); ++cit) {
    cout << *cit << " ";  // Can't modify through const_iterator
}

// Reverse iteration
for (auto rit = v.rbegin(); rit != v.rend(); ++rit) {
    cout << *rit << " ";  // Prints in reverse order
}

// Iterator arithmetic (random access only)
auto it1 = v.begin();
auto it2 = it1 + 3;  // Jump to 4th element
auto gap = it2 - it1;  // 3 (ptrdiff_t; avoid naming it 'distance' — that shadows std::distance)

// Iterator with algorithms
sort(v.begin(), v.end());
auto pos = find(v.begin(), v.end(), 3);
if (pos != v.end()) {
    v.erase(pos);  // Remove the found element
}

// Insert iterator adapters
vector<int> src = {1, 2, 3};
vector<int> dest;

// Back inserter
copy(src.begin(), src.end(), back_inserter(dest));

// Front inserter (for deque/list)
deque<int> d;
copy(src.begin(), src.end(), front_inserter(d));

// Insert at specific position
vector<int> v2 = {10, 20, 30};
copy(src.begin(), src.end(), inserter(v2, v2.begin() + 1));

Container Adapters: Specialized Interfaces

Container adapters are like specialized tools built on top of basic containers - they provide a specific interface for specific needs!

Container Adapter Examples

// Stack - LIFO (Last In, First Out)
stack<int> s;
s.push(10);
s.push(20);
s.push(30);

while (!s.empty()) {
    cout << s.top() << " ";  // 30 20 10
    s.pop();
}

// Queue - FIFO (First In, First Out)
queue<string> q;
q.push("First");
q.push("Second");
q.push("Third");

while (!q.empty()) {
    cout << q.front() << " ";  // First Second Third
    q.pop();
}

// Priority Queue - Heap
priority_queue<int> pq;  // Max heap by default
pq.push(10);
pq.push(30);
pq.push(20);

while (!pq.empty()) {
    cout << pq.top() << " ";  // 30 20 10
    pq.pop();
}

// Min heap
priority_queue<int, vector<int>, greater<int>> minHeap;
minHeap.push(10);
minHeap.push(30);
minHeap.push(20);

// Custom comparator
struct Task {
    string name;
    int priority;
};

auto taskCompare = [](const Task& a, const Task& b) {
    return a.priority < b.priority;  // Higher priority first
};

priority_queue<Task, vector<Task>, decltype(taskCompare)> tasks(taskCompare);
tasks.push({"Low priority", 1});
tasks.push({"High priority", 10});
tasks.push({"Medium priority", 5});

Practice Exercise: Student Management System

struct Student {
    int id;
    string name;
    vector<double> grades;

    double getAverage() const {
        // TODO: Calculate average grade
    }
};

class StudentManager {
private:
    map<int, Student> studentsById;
    multimap<string, int> studentsByName;

public:
    void addStudent(const Student& student);
    void removeStudent(int id);
    Student* findStudent(int id);
    vector<Student*> findStudentsByName(const string& name);

    void printReport(/* sorting criteria */);
    double getClassAverage();

    // TODO: Implement methods using STL algorithms
};

STL Performance Tips

Modern STL Features

The STL has grown a lot since C++11. Ranges, std::span, and std::format (all C++20) are fully standardized and widely available in 2026 compilers — treat them as the default modern toolkit, not experimental extras.

// C++11: Auto and range-based for
auto numbers = vector<int>{1, 2, 3, 4, 5};
for (const auto& num : numbers) {
    cout << num << " ";
}

// C++11: Initializer lists
map<string, int> ages = {
    {"Alice", 30},
    {"Bob", 25},
    {"Charlie", 35}
};

// C++11: Emplace methods (construct in-place)
vector<pair<string, int>> people;
people.emplace_back("David", 28);  // More efficient than push_back

// C++14: Generic lambdas
auto print = [](const auto& container) {
    for (const auto& elem : container) {
        cout << elem << " ";
    }
};

// C++17: Structured bindings
for (const auto& [name, age] : ages) {
    cout << name << " is " << age << " years old\n";
}

// C++17: Optional
optional<int> findValue(const vector<int>& v, int target) {
    auto it = find(v.begin(), v.end(), target);
    if (it != v.end()) {
        return *it;
    }
    return nullopt;
}

// C++20: Ranges algorithms — pass the container directly (from <algorithm>)
ranges::sort(numbers);
bool has7 = ranges::find(numbers, 7) != numbers.end();

// C++20: Range views — lazy, composable pipelines (from <ranges>)
auto evens = numbers | views::filter([](int n) { return n % 2 == 0; })
                     | views::transform([](int n) { return n * 2; });
for (int n : evens) cout << n << " ";  // Elements computed on demand, no temp vector

// C++20: std::span — a non-owning view over any contiguous sequence
auto printAll = [](span<const int> s) {   // Binds to vector, array, C-array...
    for (int n : s) cout << n << " ";
};
printAll(numbers);

// C++20: std::format — type-safe, positional formatting (from <format>)
cout << format("{} holds {} elements\n", "numbers", numbers.size());

// C++23: ranges::to — materialize a lazy view back into a container
auto doubled = numbers | views::transform([](int n) { return n * 2; })
                       | ranges::to<vector>();

Challenge Exercise: Text Analysis Engine

🎯 Quick Quiz

Summary

📚 Additional Resources

• cppreference.com
• cppreference — Containers library
• cppreference — Algorithms library

🚀 What's Next?

You now have the STL's full toolkit — containers, algorithms, and iterators — at your command. In Lesson 17: File I/O and Exceptions, you'll put those skills to work reading and writing data to files, and learn how to handle errors robustly with C++'s exception-handling mechanisms — often storing the data you read straight into the containers you just mastered.