Progress8 of 20 topics

40% complete

C++ Standard Template Library (STL)

The Standard Template Library (STL) is a powerful set of C++ template classes to provide general-purpose classes and functions with templates that implement many popular and commonly used algorithms and data structures like vectors, lists, queues, and stacks.

What You'll Learn

STL containers for storing collections of objects
STL algorithms for processing data
STL iterators for traversing containers
STL function objects (functors) for customizing algorithms
STL adaptors for modifying interfaces

Introduction to the STL

The Standard Template Library (STL) is organized into three primary components:

Containers: Objects that store collections of other objects
Algorithms: Functions for processing sequences of elements
Iterators: Objects that connect algorithms to containers

The STL provides a set of common classes for easy and efficient implementation of common data structures and algorithms. It is built on template classes, allowing it to work with any data type while maintaining type safety and performance.

STL Containers

Containers are objects that store collections of other objects (elements). The STL provides several types of containers:

Sequence Containers

These containers store elements in a linear sequence:

cpp

1#include <iostream>
2#include <vector>
3#include <list>
4#include <deque>
5using namespace std;
6
7int main() {
8    // Vector - Dynamic array
9    vector<int> vec = {1, 2, 3, 4, 5};
10    vec.push_back(6);  // Add element at the end
11    
12    cout << "Vector elements: ";
13    for (int num : vec) {
14        cout << num << " ";  // Output: 1 2 3 4 5 6
15    }
16    cout << endl;
17    
18    // List - Doubly linked list
19    list<string> lst = {"Apple", "Banana", "Cherry"};
20    lst.push_front("Avocado");  // Add at the beginning
21    lst.push_back("Date");     // Add at the end
22    
23    cout << "List elements: ";
24    for (const string& fruit : lst) {
25        cout << fruit << " ";  // Output: Avocado Apple Banana Cherry Date
26    }
27    cout << endl;
28    
29    // Deque - Double-ended queue
30    deque<float> dq = {1.1, 2.2, 3.3};
31    dq.push_front(0.0);  // Add at the beginning
32    dq.push_back(4.4);   // Add at the end
33    
34    cout << "Deque elements: ";
35    for (float val : dq) {
36        cout << val << " ";  // Output: 0 1.1 2.2 3.3 4.4
37    }
38    cout << endl;
39    
40    return 0;
41}

Associative Containers

These containers implement sorted data structures:

cpp

1#include <iostream>
2#include <set>
3#include <map>
4using namespace std;
5
6int main() {
7    // Set - Collection of unique keys, sorted by keys
8    set<int> numSet = {5, 2, 8, 5, 1, 3};  // Duplicate 5 will be ignored
9    numSet.insert(7);
10    
11    cout << "Set elements: ";
12    for (int num : numSet) {
13        cout << num << " ";  // Output: 1 2 3 5 7 8 (sorted)
14    }
15    cout << endl;
16    
17    // Map - Collection of key-value pairs, sorted by keys
18    map<string, int> ages;
19    ages["Alice"] = 30;
20    ages["Bob"] = 25;
21    ages["Charlie"] = 35;
22    
23    cout << "Map elements: " << endl;
24    for (const auto& pair : ages) {
25        cout << pair.first << ": " << pair.second << endl;
26    }
27    // Output:
28    // Alice: 30
29    // Bob: 25
30    // Charlie: 35
31    
32    return 0;
33}

Unordered Associative Containers

These containers implement unsorted (hash table) data structures:

cpp

1#include <iostream>
2#include <unordered_set>
3#include <unordered_map>
4using namespace std;
5
6int main() {
7    // Unordered Set - Collection of unique keys, hashed by keys
8    unordered_set<int> hashSet = {5, 2, 8, 5, 1, 3};  // Duplicate 5 will be ignored
9    hashSet.insert(7);
10    
11    cout << "Unordered Set elements: ";
12    for (int num : hashSet) {
13        cout << num << " ";  // Output: elements in no particular order
14    }
15    cout << endl;
16    
17    // Unordered Map - Collection of key-value pairs, hashed by keys
18    unordered_map<string, int> hashMap;
19    hashMap["Alice"] = 30;
20    hashMap["Bob"] = 25;
21    hashMap["Charlie"] = 35;
22    
23    cout << "Unordered Map elements: " << endl;
24    for (const auto& pair : hashMap) {
25        cout << pair.first << ": " << pair.second << endl;
26    }
27    // Output: elements in no particular order
28    
29    return 0;
30}

Container Adaptors

These are interfaces built on top of other containers:

cpp

1#include <iostream>
2#include <stack>
3#include <queue>
4#include <priority_queue>
5using namespace std;
6
7int main() {
8    // Stack - LIFO (Last-In-First-Out)
9    stack<int> s;
10    s.push(1);
11    s.push(2);
12    s.push(3);
13    
14    cout << "Stack elements (popping): ";
15    while (!s.empty()) {
16        cout << s.top() << " ";  // Output: 3 2 1
17        s.pop();
18    }
19    cout << endl;
20    
21    // Queue - FIFO (First-In-First-Out)
22    queue<int> q;
23    q.push(1);
24    q.push(2);
25    q.push(3);
26    
27    cout << "Queue elements (popping): ";
28    while (!q.empty()) {
29        cout << q.front() << " ";  // Output: 1 2 3
30        q.pop();
31    }
32    cout << endl;
33    
34    // Priority Queue - Highest priority element is always at the front
35    priority_queue<int> pq;  // Max heap by default
36    pq.push(3);
37    pq.push(1);
38    pq.push(5);
39    pq.push(2);
40    
41    cout << "Priority Queue elements (popping): ";
42    while (!pq.empty()) {
43        cout << pq.top() << " ";  // Output: 5 3 2 1
44        pq.pop();
45    }
46    cout << endl;
47    
48    return 0;
49}

STL Iterators

Iterators are objects that behave like pointers, used to access elements in containers. They provide a common interface for algorithms to work with different containers.

cpp

1#include <iostream>
2#include <vector>
3#include <list>
4#include <algorithm>  // For find()
5using namespace std;
6
7int main() {
8    vector<int> vec = {10, 20, 30, 40, 50};
9    
10    // Different ways to iterate through a container
11    
12    // 1. Using iterator objects
13    cout << "Using iterators: ";
14    for (vector<int>::iterator it = vec.begin(); it != vec.end(); ++it) {
15        cout << *it << " ";
16    }
17    cout << endl;
18    
19    // 2. Using auto for iterators (C++11)
20    cout << "Using auto iterators: ";
21    for (auto it = vec.begin(); it != vec.end(); ++it) {
22        cout << *it << " ";
23    }
24    cout << endl;
25    
26    // 3. Using range-based for loop (C++11)
27    cout << "Using range-based for loop: ";
28    for (int val : vec) {
29        cout << val << " ";
30    }
31    cout << endl;
32    
33    // Finding an element using algorithm and iterators
34    auto it = find(vec.begin(), vec.end(), 30);
35    if (it != vec.end()) {
36        cout << "Found " << *it << " at position: " 
37             << distance(vec.begin(), it) << endl;
38    } else {
39        cout << "Element not found" << endl;
40    }
41    
42    return 0;
43}

Iterator Categories

The STL defines several categories of iterators with different capabilities:

Input iterators: Can read, cannot write, single pass (e.g., istream_iterator)
Output iterators: Can write, cannot read, single pass (e.g., ostream_iterator)
Forward iterators: Can read/write, multiple passes, only forward direction
Bidirectional iterators: Can read/write, multiple passes, forward and backward (e.g., list, set)
Random access iterators: Can read/write, multiple passes, direct access to any element (e.g., vector, deque)

STL Algorithms

The STL provides a rich set of algorithms for common operations on sequences of elements.

Non-modifying Sequence Operations

cpp

1#include <iostream>
2#include <vector>
3#include <algorithm>
4using namespace std;
5
6int main() {
7    vector<int> vec = {5, 2, 8, 1, 9, 3, 7, 4, 6};
8    
9    // count and count_if
10    int count_val = count(vec.begin(), vec.end(), 3);
11    int count_even = count_if(vec.begin(), vec.end(), [](int x) { return x % 2 == 0; });
12    
13    cout << "Count of 3: " << count_val << endl;         // 1
14    cout << "Count of even numbers: " << count_even << endl;  // 4
15    
16    // find and find_if
17    auto it = find(vec.begin(), vec.end(), 8);
18    if (it != vec.end()) {
19        cout << "Found 8 at position: " << distance(vec.begin(), it) << endl;
20    }
21    
22    auto it2 = find_if(vec.begin(), vec.end(), [](int x) { return x > 7; });
23    if (it2 != vec.end()) {
24        cout << "First element > 7 is: " << *it2 << endl;  // 8 or 9, depending on order
25    }
26    
27    // all_of, any_of, none_of (C++11)
28    bool all = all_of(vec.begin(), vec.end(), [](int x) { return x > 0; });
29    bool any = any_of(vec.begin(), vec.end(), [](int x) { return x > 8; });
30    bool none = none_of(vec.begin(), vec.end(), [](int x) { return x < 0; });
31    
32    cout << "All positive: " << boolalpha << all << endl;      // true
33    cout << "Any > 8: " << any << endl;                        // true
34    cout << "None negative: " << none << endl;                 // true
35    
36    return 0;
37}

Modifying Sequence Operations

cpp

1#include <iostream>
2#include <vector>
3#include <algorithm>
4using namespace std;
5
6int main() {
7    vector<int> vec = {5, 2, 8, 1, 9, 3, 7, 4, 6};
8    
9    // sort
10    sort(vec.begin(), vec.end());
11    cout << "Sorted vector: ";
12    for (int num : vec) {
13        cout << num << " ";  // 1 2 3 4 5 6 7 8 9
14    }
15    cout << endl;
16    
17    // reverse
18    reverse(vec.begin(), vec.end());
19    cout << "Reversed vector: ";
20    for (int num : vec) {
21        cout << num << " ";  // 9 8 7 6 5 4 3 2 1
22    }
23    cout << endl;
24    
25    // transform
26    vector<int> result(vec.size());
27    transform(vec.begin(), vec.end(), result.begin(), 
28              [](int x) { return x * 2; });
29    
30    cout << "Transformed vector (doubled): ";
31    for (int num : result) {
32        cout << num << " ";  // 18 16 14 12 10 8 6 4 2
33    }
34    cout << endl;
35    
36    // remove and erase (erase-remove idiom)
37    vector<int> nums = {1, 2, 3, 4, 5, 2, 6, 2, 7};
38    nums.erase(remove(nums.begin(), nums.end(), 2), nums.end());
39    
40    cout << "Vector after removing 2: ";
41    for (int num : nums) {
42        cout << num << " ";  // 1 3 4 5 6 7
43    }
44    cout << endl;
45    
46    return 0;
47}

Sorting and Related Operations

cpp

1#include <iostream>
2#include <vector>
3#include <algorithm>
4using namespace std;
5
6int main() {
7    vector<int> vec = {5, 2, 8, 1, 9, 3, 7, 4, 6};
8    
9    // Custom sort (descending order)
10    sort(vec.begin(), vec.end(), greater<int>());
11    cout << "Sorted in descending order: ";
12    for (int num : vec) {
13        cout << num << " ";  // 9 8 7 6 5 4 3 2 1
14    }
15    cout << endl;
16    
17    // partial_sort
18    vector<int> nums = {5, 2, 8, 1, 9, 3, 7, 4, 6};
19    partial_sort(nums.begin(), nums.begin() + 4, nums.end());
20    
21    cout << "Partially sorted (first 4): ";
22    for (int num : nums) {
23        cout << num << " ";  // 1 2 3 4 [remaining in any order]
24    }
25    cout << endl;
26    
27    // nth_element
28    vector<int> data = {5, 2, 8, 1, 9, 3, 7, 4, 6};
29    nth_element(data.begin(), data.begin() + 4, data.end());
30    
31    cout << "After nth_element (n=4): ";
32    for (int num : data) {
33        cout << num << " ";
34    }
35    cout << endl;
36    cout << "The 5th element (index 4) is: " << data[4] << endl;
37    cout << "Elements before it are <= " << data[4] << endl;
38    cout << "Elements after it are >= " << data[4] << endl;
39    
40    return 0;
41}

Function Objects (Functors)

Function objects, or functors, are objects that can be called as if they were functions. They are used extensively in STL algorithms.

cpp

1#include <iostream>
2#include <vector>
3#include <algorithm>
4#include <functional>  // For function objects like less, greater
5using namespace std;
6
7// Custom function object
8class Multiplier {
9private:
10    int factor;
11    
12public:
13    Multiplier(int f) : factor(f) {}
14    
15    int operator()(int x) const {
16        return x * factor;
17    }
18};
19
20int main() {
21    vector<int> vec = {5, 2, 8, 1, 9};
22    
23    // Using built-in function objects
24    sort(vec.begin(), vec.end(), less<int>());    // Ascending
25    
26    cout << "Sorted with less<int>(): ";
27    for (int num : vec) {
28        cout << num << " ";  // 1 2 5 8 9
29    }
30    cout << endl;
31    
32    sort(vec.begin(), vec.end(), greater<int>()); // Descending
33    
34    cout << "Sorted with greater<int>(): ";
35    for (int num : vec) {
36        cout << num << " ";  // 9 8 5 2 1
37    }
38    cout << endl;
39    
40    // Using custom function object
41    Multiplier multiplyBy3(3);
42    vector<int> result(vec.size());
43    
44    transform(vec.begin(), vec.end(), result.begin(), multiplyBy3);
45    
46    cout << "After multiplying by 3: ";
47    for (int num : result) {
48        cout << num << " ";  // 27 24 15 6 3
49    }
50    cout << endl;
51    
52    // Using lambda as function object (C++11)
53    transform(vec.begin(), vec.end(), result.begin(),
54              [](int x) { return x + 10; });
55    
56    cout << "After adding 10: ";
57    for (int num : result) {
58        cout << num << " ";  // 19 18 15 12 11
59    }
60    cout << endl;
61    
62    return 0;
63}

Best Practices for Using STL

STL Best Practices

Prefer STL algorithms over hand-written loops for better readability and performance
Use the most appropriate container for your needs (e.g., vector for sequential access, map for key-value lookup)
Understand the complexity guarantees of different operations
Use const iterators (cbegin(), cend()) when you don't need to modify elements
Leverage C++11 range-based for loops for cleaner iteration
Be careful with algorithms that invalidate iterators

Common STL Pitfalls

Common Mistakes

Using invalidated iterators after container modifications
Forgetting to use the erase-remove idiom (container.erase(remove(...), container.end()))
Not checking for end() when using find or other search algorithms
Assuming sorted order for unordered containers
Inefficient use of containers (e.g., frequent insertions in the middle of a vector)
Not leveraging algorithm specializations for different iterator types

Summary

The Standard Template Library is a powerful part of C++ that provides:

Container classes for storing collections of data
Iterators for traversing containers
Algorithms for processing sequences
Function objects for customizing algorithm behavior

By using the STL, you can write more concise, efficient, and maintainable code, leveraging battle-tested implementations instead of reinventing the wheel. The STL is a key part of modern C++ development and is used in virtually all professional C++ codebases.

Practice Exercise

Create a program that reads a list of integers, stores them in a vector, removes all duplicates, sorts them in descending order, and then calculates their sum and average. Use appropriate STL containers, algorithms, and iterators.

Getting Started

Basic Concepts

Object-Oriented Programming

Advanced Concepts