Week 11: The Standard Template Library (STL)

Explore C++'s powerful library for data structures and algorithms.

Explore Chapter 11

Chapter 11: Introduction to the Standard Template Library

Overview of the STL: Containers, Iterators, Algorithms.

The Standard Template Library (STL) is a collection of C++ template classes and functions that provide powerful and efficient implementations of common data structures and algorithms. It's a cornerstone of modern C++ programming.

The STL can be broadly divided into three main components:

Containers: Objects that store collections of other objects (data). They manage the storage space for their elements and provide member functions to access them. Examples include `vector`, `list`, `map`, `set`.
Iterators: Objects that act like generalized pointers, allowing you to traverse the elements within a container sequentially without exposing the container's underlying representation.
Algorithms: Functions that perform common operations on sequences of objects, usually defined by ranges of iterators. Examples include `sort`, `find`, `copy`, `count`.

Using the STL promotes code reusability, efficiency (as implementations are often highly optimized), and robustness.

STL Containers: Storing Your Data.

STL containers are template classes used to manage collections of objects.

Sequence Containers

Maintain the order of elements as inserted.

`std::vector` (from ``): A dynamic array that can grow or shrink in size. Provides fast random access (`[]` operator) and efficient addition/removal at the end (`push_back`, `pop_back`).
```
#include <vector>
#include <iostream>

std::vector<int> vec = {10, 20, 30};
vec.push_back(40); // Add element to the end
std::cout << vec[1]; // Access element (output: 20)
```
`std::list` (from ``): A doubly-linked list. Efficient insertion/deletion anywhere in the list, but slower random access compared to `vector`.
`std::deque` (from ``): Double-ended queue. Efficient insertion/deletion at both the beginning and the end.

Associative Containers

Store elements in a sorted order (based on keys), allowing for fast searching.

`std::set` (from ``): Stores unique elements in sorted order.

#include <set>
#include <iostream>

std::set<int> unique_nums = {5, 2, 8, 2}; // Stores 2, 5, 8
unique_nums.insert(1);

`std::map` (from ``): Stores key-value pairs, sorted by key. Keys must be unique. Provides fast lookup based on the key.

#include <map>
#include <string>
#include <iostream>

std::map<std::string, int> ages;
ages["Alice"] = 30;
ages["Bob"] = 25;
std::cout << ages["Alice"]; // Output: 30

(There are also unordered associative containers like `unordered_set` and `unordered_map` which use hash tables for potentially faster average-case lookup but don't store elements in sorted order).

Iterators: Navigating Containers.

Iterators are objects that act like pointers to elements within an STL container. They provide a uniform way to access container elements sequentially, regardless of the container's internal structure.

Common iterator operations:

Getting Iterators: Containers provide member functions like `begin()` (points to the first element) and `end()` (points to the position *past* the last element).
Dereferencing: Use the `*` operator to get the value the iterator points to.
Incrementing: Use the `++` operator to move the iterator to the next element.
Comparison: Use `==` and `!=` to compare iterators (e.g., to check if you've reached the end).

#include <vector>
#include <iostream>

int main() {
    std::vector<int> data = {5, 10, 15};

    // Declare an iterator for a vector of integers
    std::vector<int>::iterator it;

    std::cout << "Using iterators: ";
    // Loop from the beginning to the end
    for (it = data.begin(); it != data.end(); ++it) {
        std::cout << *it << " "; // Dereference to get the value
    }
    std::cout << std::endl; // Output: 5 10 15

    // Modern C++ often uses range-based for loops, which use iterators internally:
    std::cout << "Using range-based for: ";
    for (int val : data) {
         std::cout << val << " ";
    }
     std::cout << std::endl; // Output: 5 10 15

    return 0;
}

Iterators are fundamental because STL algorithms operate on ranges defined by iterators, not directly on containers.

STL Algorithms: Operating on Sequences.

The `` header provides a large collection of functions (algorithms) that perform operations on ranges of elements, typically specified by pairs of iterators (like `begin()` and `end()`).

These algorithms are generic and work with any container type that provides the necessary iterators.

Common Examples

#include <vector>
#include <algorithm> // Include the algorithms header
#include <iostream>
#include <numeric> // For std::accumulate

int main() {
    std::vector<int> nums = {3, 1, 4, 1, 5, 9};

    // Sort the vector
    std::sort(nums.begin(), nums.end());
    // nums is now {1, 1, 3, 4, 5, 9}

    // Find an element
    auto it_find = std::find(nums.begin(), nums.end(), 5);
    if (it_find != nums.end()) {
        std::cout << "Found 5!" << std::endl;
    }

    // Count occurrences of an element
    int count_ones = std::count(nums.begin(), nums.end(), 1);
    std::cout << "Count of 1s: " << count_ones << std::endl; // Output: 2

    // Calculate sum (requires )
    int sum = std::accumulate(nums.begin(), nums.end(), 0);
    std::cout << "Sum: " << sum << std::endl; // Output: 23

     // Copy elements to another container (e.g., cout)
     std::cout << "Sorted nums: ";
     std::copy(nums.begin(), nums.end(), std::ostream_iterator<int>(std::cout, " "));
     std::cout << std::endl;


    return 0;
}

There are many algorithms available for searching, sorting, modifying sequences, performing numeric operations, and more. Using STL algorithms is generally preferred over writing manual loops for these tasks, as they are often more efficient and less error-prone.