STL Overview — Containers, Iterators, Algorithm Complexity

In this tutorial, you will learn about STL Overview. We cover key concepts, practical examples, and best practices to help you master this topic.

The C++ Standard Template Library (STL) is a generic library of data structures (containers), iteration mechanisms (iterators), and operations (algorithms) designed with zero-overhead abstraction and guaranteed algorithmic complexity.

What You'll Learn

You will understand the STL architecture (containers, iterators, algorithms, adaptors, functors), choose the right container based on complexity requirements, use iterators to bridge containers and algorithms, analyze algorithmic complexity (Big-O), understand Iterator invalidation rules, and follow modern C++ best practices with the STL.

Why It Matters

The STL is one of the most successful libraries in programming history. It provides production-ready implementations of fundamental data structures and algorithms. Learning the STL means you rarely write sorting, searching, or data structure code from scratch. Understanding its design philosophy — generic programming with iterators as the glue — changes how you think about code organization.

Learning Path

graph LR
    A["28: Memory Order"] --> B["29: STL Overview"]
    B --> C["30: Vector"]
    C --> D["31: Deque, List, Forward List"]
    D --> E["32: Set & Multiset"]
    style A fill:#4a90d9,stroke:#2c5f8a,color:#fff
    style B fill:#4a90d9,stroke:#2c5f8a,color:#fff
    style C fill:#4a90d9,stroke:#2c5f8a,color:#fff
    style D fill:#4a90d9,stroke:#2c5f8a,color:#fff
    style E fill:#4a90d9,stroke:#2c5f8a,color:#fff

The STL Architecture

The STL consists of five components:

1. Containers: data structures that store collections (vector, list, map, set)
2. Iterators: generalized pointers for traversing containers
3. Algorithms: operations on ranges defined by iterators (sort, find, transform)
4. Adaptors: wrappers that adapt an interface (stack, queue, priority_queue)
5. Functors: function objects used by algorithms (less, greater, custom)

Container Categories

Sequence Containers

Associative Containers

Unordered Associative Containers (C++11)

Iterator Categories

#include <iostream>
#include <vector>
#include <list>
#include <forward_list>
#include <iterator>

int main() {
    // Input iterator: read, forward-only, single-pass (std::istream_iterator)
    // Output iterator: write, forward-only, single-pass (std::ostream_iterator)
    
    // Forward iterator: read/write, forward-only, multi-pass (forward_list)
    std::forward_list<int> fl = {1, 2, 3};
    auto fwd = fl.begin();
    ++fwd;  // OK
    // --fwd;  // Error: no decrement
    
    // Bidirectional iterator: forward + backward (list, set, map)
    std::list<int> lst = {1, 2, 3};
    auto bi = lst.begin();
    ++bi;
    --bi;  // OK
    
    // Random access iterator: full pointer arithmetic (vector, deque, array)
    std::vector<int> vec = {1, 2, 3, 4, 5};
    auto ra = vec.begin();
    ra += 3;  // OK
    std::cout << *ra << "\n";  // 4
    std::cout << (ra[1]) << "\n";  // 5
}

Using Iterators with Algorithms

#include <iostream>
#include <vector>
#include <algorithm>
#include <numeric>

int main() {
    std::vector<int> numbers = {5, 3, 1, 4, 2, 6, 0};
    
    // Sort using iterators
    std::sort(numbers.begin(), numbers.end());
    
    // Find using iterators
    auto it = std::find(numbers.begin(), numbers.end(), 4);
    if (it != numbers.end()) {
        std::cout << "Found: " << *it << "\n";
    }
    
    // Accumulate using iterators
    int sum = std::accumulate(numbers.begin(), numbers.end(), 0);
    std::cout << "Sum: " << sum << "\n";
    
    // Transform using iterators
    std::vector<int> squared(numbers.size());
    std::transform(numbers.begin(), numbers.end(), squared.begin(),
                   [](int x) { return x * x; });
    
    for (int x : squared) std::cout << x << " ";
    std::cout << "\n";
}

Iterator Invalidation

#include <iostream>
#include <vector>

int main() {
    // vector: all iterators invalidated on reallocation
    // Insert/erase in middle: subsequent iterators invalidated
    std::vector<int> v = {1, 2, 3, 4, 5};
    auto it = v.begin() + 2;
    v.insert(it, 99);  // it is now invalid (may have been reallocated)
    
    // list: insertion/erasure does not invalidate other iterators
    // deque: insertion at front/back does not invalidate (mostly)
    // map/set: insertion/erasure does not invalidate other iterators
    // unordered: insertion may invalidate (on rehash)
    
    // Safe pattern: use return value
    std::vector<int> vec = {1, 2, 3, 4, 5};
    auto pos = std::find(vec.begin(), vec.end(), 3);
    if (pos != vec.end()) {
        pos = vec.erase(pos);  // pos now points to 4
    }
    std::cout << *pos << "\n";
}

Container Choice Decision Tree

Need random access?
  Yes -> Need sorted O(log n)? -> map/set/unordered_map/unordered_set
         Need fast back operations? -> vector
         Need fast front AND back? -> deque
  
  No -> Need sorted? -> set/multiset
         Need fast insert/erase in middle? -> list/forward_list
         Need FIFO? -> queue
         Need LIFO? -> stack
         Need priority? -> priority_queue

Common Mistakes

Mistake 1: Using the Wrong Container

// Frequent insertions in the middle
std::vector<int> v;
v.insert(v.begin(), 10);  // O(n), use list or deque

Mistake 2: Using Invalidated Iterators

std::vector<int> v = {1,2,3};
for (auto it = v.begin(); it != v.end(); ++it) {
    if (*it == 2) v.erase(it);  // it is invalidated!
}

Use the return value: it = v.erase(it);

Mistake 3: Assuming Contiguous Storage for Non-Vector Containers

Only vector, array, and basic_string guarantee contiguous storage.

Mistake 4: Calling end() in Every Loop Iteration

for (auto it = v.begin(); it != v.end(); ++it) // v.end() called each iteration

Precompute the end: for (auto it = v.begin(), end = v.end(); it != end; ++it)

Mistake 5: Not Reserving Capacity

std::vector<int> v;
for (int i = 0; i < 10000; ++i) v.push_back(i);  // multiple reallocations

Call v.reserve(10000) before the loop.

Mistake 6: Using list When vector is Faster

std::list seems like the right choice for insertions, but vector with occasional insertions is often faster due to cache locality.

Practice Questions

1. What are the five components of the STL?
2. When would you choose vector over deque?
3. What is iterator invalidation and why does it matter?
4. Name the five iterator categories in order of capability.
5. Why is std::list often slower than std::vector despite O(1) insertion?

Challenge

Write a function template that accepts any container and prints its elements separated by commas. Use SFINAE or concepts (C++20) to ensure the container is actually iterable.

FAQ

Mini Project

Write a benchmark that compares std::vector, std::list, and std::deque for inserting 100,000 elements at the front:

#include <iostream>
#include <vector>
#include <list>
#include <deque>
#include <chrono>

template <typename Container>
double benchmark(size_t count) {
    auto start = std::chrono::high_resolution_clock::now();
    Container c;
    for (size_t i = 0; i < count; ++i) {
        c.insert(c.begin(), static_cast<int>(i));
    }
    auto end = std::chrono::high_resolution_clock::now();
    return std::chrono::duration<double, std::milli>(end - start).count();
}

int main() {
    constexpr size_t COUNT = 100000;
    
    std::cout << "vector: " << benchmark<std::vector<int>>(COUNT) << " ms\n";
    std::cout << "deque: " << benchmark<std::deque<int>>(COUNT) << " ms\n";
    std::cout << "list: " << benchmark<std::list<int>>(COUNT) << " ms\n";
}

What's Next

The STL architecture connects containers to algorithms via iterators. The next lesson covers std::vector in depth: dynamic array semantics, capacity management, emplacement, and growth strategies.