STL Containers and Algorithms

50 min

The Standard Template Library (STL) is a powerful collection of template classes and functions that provide common data structures and algorithms. STL is divided into three main components: containers (data structures), algorithms (operations on data), and iterators (abstractions for accessing container elements). Understanding STL is essential for modern C++ programming, as it eliminates the need to implement many common data structures and algorithms from scratch.

STL containers are template classes that store and organize data. Sequence containers (vector, deque, list, forward_list, array) store elements in linear order. Associative containers (set, map, multiset, multimap) store elements in sorted order for fast lookup. Unordered containers (unordered_set, unordered_map) use hashing for average O(1) access. Each container has different performance characteristics, making container choice crucial for optimal performance.

STL algorithms are template functions that operate on ranges of elements through iterators. Algorithms include operations like sorting (sort), searching (find, binary_search), transforming (transform), and accumulating (accumulate). Algorithms are generic and work with any container that provides appropriate iterators, promoting code reuse and consistency. Most algorithms are in the <algorithm> header and work with iterator ranges [first, last).

Iterators provide a uniform interface for accessing container elements, abstracting away container-specific details. Iterators come in different categories: input, output, forward, bidirectional, and random access, each with different capabilities. Random access iterators (like vector iterators) support arithmetic operations, while forward iterators only support increment. Understanding iterator categories helps you choose appropriate algorithms and containers.

Lambda expressions (C++11) enable inline function objects, making algorithms more expressive and eliminating the need for separate function objects or functions. Lambdas can capture variables from their enclosing scope by value or reference, enabling powerful, concise code. Lambdas are particularly useful with STL algorithms like for_each, transform, and remove_if, where custom behavior is needed.

Modern C++ practices with STL include using range-based for loops (C++11), auto type deduction, and algorithm improvements. C++20 adds ranges library that provides a more functional programming style. Understanding STL containers, algorithms, and iterators enables you to write efficient, maintainable C++ code that leverages the standard library effectively.

Key Concepts

STL provides containers, algorithms, and iterators.
Containers include sequence, associative, and unordered types.
Algorithms operate on iterator ranges, not containers directly.
Iterators provide uniform access to container elements.
Lambda expressions enable inline function objects for algorithms.

Learning Objectives

Master

Using STL containers (vector, map, set) effectively
Applying STL algorithms to process data
Understanding iterator categories and usage
Combining lambdas with STL algorithms

Develop

Understanding container performance characteristics
Choosing appropriate containers for different use cases
Writing efficient, STL-based C++ code

Tips

Prefer vector for random access, list for frequent insertions/deletions.
Use map for key-value pairs, set for unique sorted elements.
Combine algorithms: std::sort then std::unique to remove duplicates.
Use auto with iterators: auto it = container.begin();.

Common Pitfalls

Not understanding container performance, choosing wrong container.
Invalidating iterators (e.g., after vector insertion), causing crashes.
Not using algorithms, writing manual loops when algorithms exist.
Not understanding iterator categories, using wrong iterator type.

Summary

STL provides powerful containers, algorithms, and iterators.
Container choice affects performance significantly.
Algorithms work through iterators, promoting code reuse.
Lambdas make algorithms more expressive and concise.

Exercise

Demonstrate STL containers and algorithms with lambda expressions.

#include <iostream>
#include <vector>
#include <map>
#include <algorithm>
#include <string>

int main() {
    // Vector container
    std::vector<int> numbers = {3, 1, 4, 1, 5, 9, 2, 6};
    
    std::cout << "Original vector: ";
    for (int num : numbers) {
        std::cout << num << " ";
    }
    std::cout << std::endl;
    
    // Sort algorithm
    std::sort(numbers.begin(), numbers.end());
    std::cout << "Sorted vector: ";
    for (int num : numbers) {
        std::cout << num << " ";
    }
    std::cout << std::endl;
    
    // Lambda expression with find_if
    auto it = std::find_if(numbers.begin(), numbers.end(), 
                          [](int n) { return n > 5; });
    if (it != numbers.end()) {
        std::cout << "First number > 5: " << *it << std::endl;
    }
    
    // Map container
    std::map<std::string, int> ages;
    ages["Alice"] = 25;
    ages["Bob"] = 30;
    ages["Charlie"] = 35;
    
    std::cout << "\nAges:" << std::endl;
    for (const auto& pair : ages) {
        std::cout << pair.first << ": " << pair.second << std::endl;
    }
    
    return 0;
}

Exercise Tips

Try different containers: vector vs list vs deque for performance comparison.
Use algorithms: std::sort, std::find_if, std::transform with containers.
Experiment with lambda captures: [&] by reference, [=] by value.
Combine containers: std::map<std::string, std::vector<int>> for complex data.

STL Containers and Algorithms