Module 10: STL (Standard Template Library)

Chapter 10 • Intermediate

70 min

STL (Standard Template Library)

The Standard Template Library (STL) is a powerful collection of template classes and functions that provide common data structures and algorithms. It's one of C++'s greatest strengths.

What is STL?

STL consists of:

Containers: Data structures (vector, list, map, etc.)
Algorithms: Functions that operate on containers (sort, find, etc.)
Iterators: Objects that traverse containers
Function Objects: Objects that can be called like functions

Benefits:

Efficiency: Highly optimized implementations
Reusability: Pre-built, tested components
Type Safety: Templates ensure type safety
Standardization: Part of C++ standard

Containers

Sequence Containers

Store elements in linear order:

1. vector

Dynamic array that grows automatically:

cpp.js

#include <vector>
using namespace std;

vector<int> v;              // Empty vector
vector<int> v2(5);          // 5 elements (default initialized)
vector<int> v3(5, 10);      // 5 elements, all 10
vector<int> v4{1, 2, 3, 4}; // Initializer list

v.push_back(10);            // Add element
v.pop_back();               // Remove last element
v.size();                    // Number of elements
v.empty();                   // Check if empty
v[0];                        // Access element
v.at(0);                     // Safe access (throws exception)

2. list

Doubly linked list:

cpp.js

#include <list>
using namespace std;

list<int> l;
l.push_back(10);
l.push_front(5);
l.pop_back();
l.pop_front();

3. deque

Double-ended queue:

cpp.js

#include <deque>
using namespace std;

deque<int> dq;
dq.push_back(10);
dq.push_front(5);

Associative Containers

Store elements in sorted order:

4. set

Unique elements, sorted:

cpp.js

#include <set>
using namespace std;

set<int> s;
s.insert(10);
s.insert(5);
s.insert(10);  // Ignored (duplicate)
s.find(10);    // Returns iterator
s.count(10);    // 0 or 1

5. map

Key-value pairs, sorted by key:

cpp.js

#include <map>
using namespace std;

map<string, int> m;
m["Alice"] = 25;
m["Bob"] = 30;
m.insert({"Charlie", 28});
m["Alice"];                  // Access value
m.find("Bob");              // Returns iterator
m.count("Alice");           // 0 or 1

6. multiset / multimap

Allow duplicate keys:

cpp.js

multiset<int> ms;
ms.insert(10);
ms.insert(10);  // Allowed

Unordered Containers (C++11)

Hash-based containers (faster lookup):

7. unordered_set / unordered_map

cpp.js

#include <unordered_set>
#include <unordered_map>
using namespace std;

unordered_set<int> us;
unordered_map<string, int> um;

Iterators

Iterators provide a way to traverse containers:

Iterator Types

begin(): Points to first element
end(): Points past last element
rbegin(): Reverse begin
rend(): Reverse end

Iterator Categories

Input Iterator: Read-only, forward
Output Iterator: Write-only, forward
Forward Iterator: Read/write, forward
Bidirectional Iterator: Forward and backward
Random Access Iterator: Jump to any position

Using Iterators

cpp.js

vector<int> v{1, 2, 3, 4, 5};

// Traditional loop
for (auto it = v.begin(); it != v.end(); ++it) {
    cout << *it << " ";
}

// Range-based for (C++11) - preferred
for (int num : v) {
    cout << num << " ";
}

// With auto
for (auto num : v) {
    cout << num << " ";
}

Algorithms

STL provides many algorithms in <algorithm>:

Sorting

cpp.js

#include <algorithm>
using namespace std;

vector<int> v{3, 1, 4, 1, 5};
sort(v.begin(), v.end());           // Ascending
sort(v.begin(), v.end(), greater<int>());  // Descending

Searching

cpp.js

vector<int> v{1, 2, 3, 4, 5};
auto it = find(v.begin(), v.end(), 3);
if (it != v.end()) {
    cout << "Found at position: " << distance(v.begin(), it) << endl;
}

// Binary search (requires sorted container)
bool found = binary_search(v.begin(), v.end(), 3);

Modifying Algorithms

cpp.js

vector<int> v{1, 2, 3, 4, 5};
reverse(v.begin(), v.end());
fill(v.begin(), v.end(), 0);
transform(v.begin(), v.end(), v.begin(), [](int x) { return x * 2; });

Counting

cpp.js

vector<int> v{1, 2, 2, 3, 2, 4};
int count = count(v.begin(), v.end(), 2);
int evenCount = count_if(v.begin(), v.end(), [](int x) { return x % 2 == 0; });

Common STL Operations

Vector Operations

cpp.js

vector<int> v;

// Adding elements
v.push_back(10);
v.insert(v.begin(), 5);
v.insert(v.begin() + 2, 7);

// Removing elements
v.pop_back();
v.erase(v.begin());
v.erase(v.begin(), v.begin() + 2);
v.clear();

// Accessing
v[0];           // No bounds checking
v.at(0);        // Bounds checking
v.front();      // First element
v.back();       // Last element

// Size
v.size();
v.empty();
v.capacity();   // Allocated space
v.reserve(100); // Reserve space

Map Operations

cpp.js

map<string, int> m;

// Inserting
m["Alice"] = 25;
m.insert({"Bob", 30});
m.insert(pair<string, int>("Charlie", 28));

// Accessing
int age = m["Alice"];  // Creates if doesn't exist
int age2 = m.at("Bob"); // Throws if doesn't exist

// Checking
if (m.find("Alice") != m.end()) {
    // Found
}

// Iterating
for (auto& pair : m) {
    cout << pair.first << ": " << pair.second << endl;
}

Function Objects (Functors)

Objects that can be called like functions:

cpp.js

class Add {
public:
    int operator()(int a, int b) {
        return a + b;
    }
};

Add add;
int result = add(5, 3);  // 8

Built-in Functors

cpp.js

#include <functional>
using namespace std;

plus<int> add;
minus<int> sub;
multiplies<int> mul;
divides<int> div;
modulus<int> mod;

greater<int> gt;
less<int> lt;
equal_to<int> eq;

Lambda Functions (C++11)

Anonymous function objects:

cpp.js

vector<int> v{1, 2, 3, 4, 5};

// Simple lambda
for_each(v.begin(), v.end(), [](int x) {
    cout << x << " ";
});

// Lambda with capture
int multiplier = 2;
transform(v.begin(), v.end(), v.begin(), [multiplier](int x) {
    return x * multiplier;
});

// Lambda with reference capture
int sum = 0;
for_each(v.begin(), v.end(), [&sum](int x) {
    sum += x;
});

Best Practices

✅ Prefer STL containers over raw arrays
✅ Use range-based for loops (C++11)
✅ Use algorithms instead of writing loops
✅ Choose right container for your needs
✅ Use const iterators when not modifying
✅ Reserve space for vectors when size known
✅ Use emplace_back (C++11) instead of push_back when possible
✅ Understand iterator invalidation rules

Container Selection Guide

Need	Container
Dynamic array	`vector`
Insert at front/back	`deque`
Frequent insertions	`list`
Sorted unique elements	`set`
Key-value pairs	`map`
Fast lookup	`unordered_map`
Priority queue	`priority_queue`

Common Mistakes

❌ Using [] on map for non-existent key (creates it)
❌ Iterator invalidation after container modification
❌ Not checking iterator before dereferencing
❌ Using wrong container for the use case
❌ Not using algorithms when available
❌ Forgetting to include necessary headers

Next Steps

You've now mastered the fundamentals of C++! Continue learning:

Templates: Generic programming
Smart Pointers: Modern memory management
Concurrency: Multithreading
File I/O: Reading and writing files
Exception Handling: Error management

Summary

STL provides:

Efficient, tested containers
Powerful algorithms
Type-safe templates
Standardized interfaces

Master STL, and you'll write efficient, maintainable C++ code!

Hands-on Examples

Vector Operations

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

int main() {
    // Vector declaration and initialization
    vector<int> v1;
    vector<int> v2(5, 10);  // 5 elements, all 10
    vector<int> v3{1, 2, 3, 4, 5};  // Initializer list
    
    // Adding elements
    v1.push_back(10);
    v1.push_back(20);
    v1.push_back(30);
    
    // Accessing elements
    cout << "v1[0]: " << v1[0] << endl;
    cout << "v1.at(1): " << v1.at(1) << endl;
    cout << "v1.front(): " << v1.front() << endl;
    cout << "v1.back(): " << v1.back() << endl;
    
    // Size
    cout << "Size: " << v1.size() << endl;
    cout << "Empty: " << (v1.empty() ? "Yes" : "No") << endl;
    
    // Iterating
    cout << "\nElements: ";
    for (int num : v1) {
        cout << num << " ";
    }
    cout << endl;
    
    // Using iterators
    cout << "Using iterators: ";
    for (auto it = v1.begin(); it != v1.end(); ++it) {
        cout << *it << " ";
    }
    cout << endl;
    
    // Modifying
    v1.insert(v1.begin() + 1, 15);
    v1.erase(v1.begin());
    
    cout << "\nAfter modifications: ";
    for (int num : v1) {
        cout << num << " ";
    }
    cout << endl;
    
    return 0;
}

Vector is a dynamic array that grows automatically. Use push_back to add elements, [] or at() to access. Iterators provide a way to traverse. insert() and erase() modify elements. Prefer range-based for loops for iteration.

Module 9: Inheritance and Polymorphism

Module 11: Templates (Generic Programming)