Components of 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. The STL is organized into three major components:

1. Containers: Store collections of objects
2. Algorithms: Process and manipulate data stored in containers
3. Iterators: Connect algorithms with containers

1. Containers

Containers are objects that store collections of other objects (elements). The STL provides several container classes, which can be broadly categorized into three types:

Sequence Containers

Sequence containers store elements in a linear sequence and provide operations to access elements by their position.

• Vector: Dynamic array that can grow or shrink in size
• List: Doubly-linked list that supports efficient insertions and deletions anywhere in the sequence
• Deque: Double-ended queue that supports efficient insertions and deletions at both the beginning and the end
• Forward List (C++11): Singly-linked list that supports efficient insertions and deletions at any point
• Array (C++11): Static array with fixed size determined at compile time

Associative Containers

Associative containers implement sorted data structures that provide fast lookup (O(log n) complexity).

• Set: Collection of unique keys, sorted by keys
• Multiset: Collection of keys, sorted by keys (allows duplicate keys)
• Map: Collection of key-value pairs, sorted by keys, with unique keys
• Multimap: Collection of key-value pairs, sorted by keys (allows duplicate keys)

Unordered Associative Containers (C++11)

Unordered associative containers implement unsorted data structures that provide fast lookup (O(1) average case complexity).

• Unordered Set: Collection of unique keys, hashed by keys
• Unordered Multiset: Collection of keys, hashed by keys (allows duplicate keys)
• Unordered Map: Collection of key-value pairs, hashed by keys, with unique keys
• Unordered Multimap: Collection of key-value pairs, hashed by keys (allows duplicate keys)

Container Adaptors

Container adaptors are interfaces built on top of other containers with restricted functionality.

• Stack: LIFO (Last-In-First-Out) data structure
• Queue: FIFO (First-In-First-Out) data structure
• Priority Queue: Queue where elements have priorities and are retrieved in order of their priority

Container Comparison Table

2. Algorithms

STL algorithms are independent of containers and operate on sequences of elements defined by iterators. They implement many common operations on data structures.

Types of Algorithms

Non-modifying Sequence Operations

• Search algorithms: find, find_if, count, count_if, search
• Comparison algorithms: equal, mismatch, lexicographical_compare
• Property check algorithms: all_of, any_of, none_of (C++11)

Modifying Sequence Operations

• Copy algorithms: copy, copy_if, copy_n, copy_backward
• Move algorithms: move, move_backward (C++11)
• Transform algorithms: transform
• Generate algorithms: generate, generate_n
• Remove algorithms: remove, remove_if, remove_copy, remove_copy_if
• Replace algorithms: replace, replace_if, replace_copy, replace_copy_if
• Fill algorithms: fill, fill_n
• Reverse algorithms: reverse, reverse_copy
• Rotation algorithms: rotate, rotate_copy
• Swap algorithms: swap, swap_ranges, iter_swap
• Shuffle algorithms: shuffle (C++11), random_shuffle (deprecated in C++17)

Sorting and Related Operations

• Sorting algorithms: sort, partial_sort, stable_sort
• Binary search algorithms: lower_bound, upper_bound, binary_search, equal_range
• Merge algorithms: merge, inplace_merge
• Set operation algorithms: set_union, set_intersection, set_difference, set_symmetric_difference
• Heap algorithms: make_heap, push_heap, pop_heap, sort_heap
• Min/max algorithms: min, max, minmax, min_element, max_element, minmax_element
• Lexicographical comparison algorithms: lexicographical_compare
• Permutation algorithms: next_permutation, prev_permutation, is_permutation

Numeric Operations

• Accumulate algorithms: accumulate, inner_product
• Prefix sum algorithms: partial_sum, inclusive_scan, exclusive_scan
• Adjacent difference algorithms: adjacent_difference
• Reduce algorithms: reduce (C++17)
• Transform-reduce algorithms: transform_reduce (C++17)

Example of Using Algorithms

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

int main() {
    vector<int> v = {5, 2, 8, 1, 9, 3, 7, 4, 6};
    
    // Sort the vector
    sort(v.begin(), v.end());
    cout << "Sorted vector: ";
    for (int n : v) {
        cout << n << " ";
    }
    cout << endl;
    
    // Find an element
    auto it = find(v.begin(), v.end(), 7);
    if (it != v.end()) {
        cout << "Found 7 at position: " << (it - v.begin()) << endl;
    }
    
    // Count elements that satisfy a condition
    int count = count_if(v.begin(), v.end(), [](int n) { return n % 2 == 0; });
    cout << "Number of even elements: " << count << endl;
    
    // Transform elements
    vector<int> squared(v.size());
    transform(v.begin(), v.end(), squared.begin(), [](int n) { return n * n; });
    
    cout << "Squared values: ";
    for (int n : squared) {
        cout << n << " ";
    }
    cout << endl;
    
    return 0;
}

3. Iterators

Iterators are objects that behave like pointers and are used to access elements in containers. They provide a common interface for accessing elements across different container types.

Types of Iterators

STL iterators are categorized based on their capabilities, from least to most powerful:

1. Input Iterators: Can only be dereferenced to read the value they point to, and can only be incremented (one-pass, read-only)
2. Output Iterators: Can only be dereferenced to write a value, and can only be incremented (one-pass, write-only)
3. Forward Iterators: Can be dereferenced for both reading and writing, and can be incremented (multi-pass, read-write)
4. Bidirectional Iterators: Like forward iterators, but can also be decremented
5. Random Access Iterators: Like bidirectional iterators, but can also be moved arbitrarily (including addition, subtraction, etc.)

Iterator Compatibility with Containers

Iterator Operations

The operations supported by an iterator depend on its category:

• All iterators: it++, *it (dereference)
• Input iterators: it == it2, it != it2 (comparison)
• Forward iterators: All of the above plus multi-pass guarantee
• Bidirectional iterators: All of the above plus it--
• Random access iterators: All of the above plus it + n, it - n, it[n], it < it2, it <= it2, it > it2, it >= it2

Example of Using Iterators

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

int main() {
    // Using iterators with vector (random access)
    vector<int> vec = {10, 20, 30, 40, 50};
    
    cout << "Vector elements using iterators: ";
    for (vector<int>::iterator it = vec.begin(); it != vec.end(); ++it) {
        cout << *it << " ";
    }
    cout << endl;
    
    // Random access with vector iterators
    vector<int>::iterator vecIt = vec.begin();
    cout << "vecIt + 2: " << *(vecIt + 2) << endl;
    cout << "vecIt[3]: " << vecIt[3] << endl;
    
    // Using iterators with list (bidirectional)
    list<int> lst = {10, 20, 30, 40, 50};
    
    cout << "List elements using iterators: ";
    for (list<int>::iterator it = lst.begin(); it != lst.end(); ++it) {
        cout << *it << " ";
    }
    cout << endl;
    
    // Bidirectional operations with list iterators
    list<int>::iterator lstIt = lst.begin();
    ++lstIt;  // Move forward
    cout << "After ++lstIt: " << *lstIt << endl;
    --lstIt;  // Move backward
    cout << "After --lstIt: " << *lstIt << endl;
    
    // The following would NOT compile for list iterators
    // cout << "lstIt + 2: " << *(lstIt + 2) << endl;  // Error: no random access
    // cout << "lstIt[3]: " << lstIt[3] << endl;       // Error: no random access
    
    return 0;
}

4. Function Objects (Functors)

Function objects or functors are objects that can be called like functions. They are instances of classes that overload the function call operator operator(). STL provides several predefined function objects and also allows you to create your own.

Predefined Function Objects

STL provides a set of function objects in the <functional> header:

• Arithmetic operations: plus, minus, multiplies, divides, modulus, negate
• Comparison operations: equal_to, not_equal_to, greater, less, greater_equal, less_equal
• Logical operations: logical_and, logical_or, logical_not

Example of Using Function Objects

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

int main() {
    vector<int> v = {5, 2, 8, 1, 9};
    
    // Sort in ascending order using less (default)
    sort(v.begin(), v.end(), less<int>());
    
    cout << "Sorted in ascending order: ";
    for (int n : v) {
        cout << n << " ";
    }
    cout << endl;
    
    // Sort in descending order using greater
    sort(v.begin(), v.end(), greater<int>());
    
    cout << "Sorted in descending order: ";
    for (int n : v) {
        cout << n << " ";
    }
    cout << endl;
    
    // Custom function object
    class IsMultipleOf {
    private:
        int divisor;
    public:
        IsMultipleOf(int d) : divisor(d) {}
        
        bool operator()(int value) const {
            return value % divisor == 0;
        }
    };
    
    vector<int> numbers = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10};
    
    // Count multiples of 3
    int count = count_if(numbers.begin(), numbers.end(), IsMultipleOf(3));
    cout << "Number of multiples of 3: " << count << endl;
    
    return 0;
}

5. Adaptors

Adaptors are components that transform one interface to another. STL provides both container adaptors and iterator adaptors.

Container Adaptors

As mentioned earlier, container adaptors provide a restricted interface to the underlying container:

• Stack: Provides a LIFO (Last-In-First-Out) interface
• Queue: Provides a FIFO (First-In-First-Out) interface
• Priority Queue: Provides a priority queue interface where elements are ordered by priority

Iterator Adaptors

Iterator adaptors modify the behavior of iterators:

• Reverse Iterators: Iterate backwards through a container
• Insert Iterators: Insert elements into a container rather than overwriting them
• Move Iterators: Transfer ownership of elements rather than copying them

Example of Using Adaptors

#include <iostream>
#include <vector>
#include <stack>
#include <queue>
#include <iterator>
using namespace std;

int main() {
    // Container adaptor: Stack
    stack<int> s;
    s.push(10);
    s.push(20);
    s.push(30);
    
    cout << "Stack (LIFO): ";
    while (!s.empty()) {
        cout << s.top() << " ";
        s.pop();
    }
    cout << endl;
    
    // Container adaptor: Queue
    queue<int> q;
    q.push(10);
    q.push(20);
    q.push(30);
    
    cout << "Queue (FIFO): ";
    while (!q.empty()) {
        cout << q.front() << " ";
        q.pop();
    }
    cout << endl;
    
    // Container adaptor: Priority Queue
    priority_queue<int> pq;
    pq.push(10);
    pq.push(30);
    pq.push(20);
    
    cout << "Priority Queue (largest first): ";
    while (!pq.empty()) {
        cout << pq.top() << " ";
        pq.pop();
    }
    cout << endl;
    
    // Iterator adaptor: Reverse Iterator
    vector<int> v = {10, 20, 30, 40, 50};
    
    cout << "Vector using reverse iterators: ";
    for (vector<int>::reverse_iterator rit = v.rbegin(); rit != v.rend(); ++rit) {
        cout << *rit << " ";
    }
    cout << endl;
    
    // Iterator adaptor: Insert Iterator
    vector<int> source = {1, 2, 3};
    vector<int> dest = {4, 5, 6};
    
    cout << "Before copy: ";
    for (int n : dest) {
        cout << n << " ";
    }
    cout << endl;
    
    // Copy source to the beginning of dest using back_inserter
    copy(source.begin(), source.end(), back_inserter(dest));
    
    cout << "After copy with back_inserter: ";
    for (int n : dest) {
        cout << n << " ";
    }
    cout << endl;
    
    return 0;
}

6. Allocators

Allocators are objects that handle memory allocation and deallocation for containers. They provide an abstraction layer between containers and the underlying memory model.

The default allocator is std::allocator, but you can create custom allocators to:

• Use a different memory model
• Track memory usage
• Implement pooled allocation
• Enforce alignment requirements

Example of Using a Custom Allocator

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

// A simple custom allocator that tracks allocations
template <typename T>
class TrackingAllocator {
private:
    static size_t allocatedBytes;
    
public:
    typedef T value_type;
    
    TrackingAllocator() noexcept {}
    
    template <class U>
    TrackingAllocator(const TrackingAllocator<U>&) noexcept {}
    
    T* allocate(size_t n) {
        size_t bytes = n * sizeof(T);
        allocatedBytes += bytes;
        cout << "Allocating " << bytes << " bytes" << endl;
        return static_cast<T*>(::operator new(bytes));
    }
    
    void deallocate(T* p, size_t n) noexcept {
        size_t bytes = n * sizeof(T);
        allocatedBytes -= bytes;
        cout << "Deallocating " << bytes << " bytes" << endl;
        ::operator delete(p);
    }
    
    static size_t getAllocatedBytes() {
        return allocatedBytes;
    }
};

template <typename T>
size_t TrackingAllocator<T>::allocatedBytes = 0;

template <class T, class U>
bool operator==(const TrackingAllocator<T>&, const TrackingAllocator<U>&) { return true; }

template <class T, class U>
bool operator!=(const TrackingAllocator<T>&, const TrackingAllocator<U>&) { return false; }

int main() {
    // Create a vector with the tracking allocator
    vector<int, TrackingAllocator<int>> v;
    
    cout << "Before pushing elements: " 
         << TrackingAllocator<int>::getAllocatedBytes() << " bytes allocated" << endl;
    
    // Add some elements
    for (int i = 0; i < 10; i++) {
        v.push_back(i);
        cout << "After pushing element " << i << ": " 
             << TrackingAllocator<int>::getAllocatedBytes() << " bytes allocated" << endl;
    }
    
    // Clear the vector
    v.clear();
    v.shrink_to_fit();
    
    cout << "After clearing and shrinking: " 
         << TrackingAllocator<int>::getAllocatedBytes() << " bytes allocated" << endl;
    
    return 0;
}

Summary

The STL is organized into several key components that work together:

1. Containers: Store collections of elements (vector, list, map, set, etc.)
2. Algorithms: Process and manipulate data (sort, find, transform, etc.)
3. Iterators: Connect algorithms with containers and provide a uniform interface
4. Function Objects: Encapsulate functions as objects for use with algorithms
5. Adaptors: Transform one interface to another (stack, queue, reverse_iterator, etc.)
6. Allocators: Handle memory allocation and deallocation for containers

These components are designed to work together seamlessly, allowing you to write generic, efficient, and reusable code. The power of the STL comes from this modularity and the ability to mix and match these components as needed for your specific application.

When using the STL, it’s important to understand the strengths and weaknesses of each container type, the algorithmic complexity of various operations, and how iterators bridge the gap between containers and algorithms. With this understanding, you can make informed decisions about which STL components to use for your specific needs.