C++ STL Introduction

The C++ Standard Template Library (STL) is a collection of ready-made, highly optimized generic components: containers that store data, iterators that traverse that data, and algorithms that operate on it. Instead of hand-writing a dynamic array, a linked list, or a sorting routine every time you need one, the STL gives you battle-tested, template-based building blocks that work with almost any data type. Nearly every serious C++ program relies on the STL, so understanding it is essential to writing modern, idiomatic C++.

Overview / How the STL Works

The STL is built from four cooperating pieces:

• Containers — class templates that store collections of objects, such as std::vector, std::map, std::set, and std::list. Because they are templates, the same vector code works for int, std::string, or a custom class, with the actual type substituted at compile time (no runtime overhead).
• Iterators — objects that behave like generalized pointers. They let algorithms walk through a container’s elements (begin() to end()) without needing to know whether the underlying structure is a contiguous array or a linked set of nodes.
• Algorithms — free functions such as std::sort, std::find, and std::accumulate that operate purely through iterator ranges. Because algorithms never touch a container directly, one sort function works on a vector, a deque, or a plain C array.
• Function objects (functors) and lambdas — callable objects passed to algorithms to customize behavior, such as a custom comparison for sorting.

This separation is the key design idea: containers don’t know about algorithms, and algorithms don’t know about containers — iterators are the glue between them. This is sometimes called the STL’s “generic programming” model, and it is implemented entirely through C++ templates, which are expanded and type-checked at compile time. That means there is no virtual-function overhead just to use a vector or call sort: the compiler generates specialized machine code for each concrete type you use.

Under the hood, a container like std::vector manages memory on your behalf. It allocates a contiguous block on the heap, tracks a size (how many elements are actually stored) and a capacity (how much space is currently allocated). When you push_back past the current capacity, the vector allocates a new, larger block (typically doubling in size), moves or copies the existing elements over, and frees the old block. This amortized-growth strategy is why appending to a vector is, on average, a constant-time operation even though occasional reallocations are linear-time. Associative containers like std::map and std::set, by contrast, are usually implemented as self-balancing binary search trees (typically red-black trees), which is why their elements are always kept in sorted key order and lookups cost O(log n).

Syntax

Every STL container follows the same general declaration pattern:

container_name<element_type> variable_name;
container_name<key_type, value_type> variable_name; // for maps

Container	Header	Description
vector	vector	Dynamic array; fast random access and append at the end
list	list	Doubly linked list; fast insert/erase anywhere, no random access
deque	deque	Double-ended queue; fast insert/erase at both ends
set / multiset	set	Sorted, unique (or non-unique) keys, tree-based
map / multimap	map	Sorted key-value pairs, tree-based
unordered_map	unordered_map	Hash-table based key-value pairs, average O(1) lookup
stack, queue	stack, queue	Container adapters restricting access to LIFO/FIFO order

Algorithms follow a similar pattern — they take a range described by two iterators, plus optional extra arguments:

algorithm_name(container.begin(), container.end(), /* extra args */);

• container.begin() — an iterator pointing to the first element.
• container.end() — an iterator pointing one past the last element (never dereferenced).
• Extra arguments vary by algorithm: a value to search for, a comparator function, an output iterator, and so on.

Examples

Example 1: std::vector basics

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

int main() {
    std::vector<int> scores;
    scores.push_back(85);
    scores.push_back(92);
    scores.push_back(78);
    scores.push_back(90);

    std::cout << "Number of scores: " << scores.size() << std::endl;

    for (int score : scores) {
        std::cout << score << " ";
    }
    std::cout << std::endl;

    int total = std::accumulate(scores.begin(), scores.end(), 0);
    double average = static_cast<double>(total) / scores.size();

    std::cout << "Average: " << average << std::endl;

    return 0;
}

Output:
Number of scores: 4
85 92 78 90 
Average: 86.25

A std::vector<int> starts empty; each push_back appends a new element, growing the underlying array as needed. The range-based for loop uses iterators internally to visit every element, and std::accumulate (from <numeric>) sums a range in one call instead of a manual loop.

Example 2: std::map for counting

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

int main() {
    std::string text = "the quick brown fox jumps over the lazy dog the fox runs";
    std::map<std::string, int> wordCount;

    std::stringstream ss(text);
    std::string word;
    while (ss >> word) {
        wordCount[word]++;
    }

    for (const auto& pair : wordCount) {
        std::cout << pair.first << ": " << pair.second << std::endl;
    }

    return 0;
}

Output:
brown: 1
dog: 1
fox: 2
jumps: 1
lazy: 1
over: 1
quick: 1
runs: 1
the: 3

This is one of the most useful STL patterns: use a map<std::string, int> as a frequency table. wordCount[word]++ looks up the key; if it doesn’t exist yet, operator[] default-constructs it (an int defaults to 0), then increments it. Because std::map stores keys in sorted order internally, iterating over it always produces output in alphabetical order — no separate sort step needed.

Example 3: Algorithms with std::sort, std::binary_search, and std::set

#include <iostream>
#include <vector>
#include <algorithm>
#include <set>

int main() {
    std::vector<int> numbers = {5, 3, 8, 3, 9, 1, 5, 8, 2};

    std::sort(numbers.begin(), numbers.end());

    std::cout << "Sorted: ";
    for (int n : numbers) {
        std::cout << n << " ";
    }
    std::cout << std::endl;

    bool found = std::binary_search(numbers.begin(), numbers.end(), 8);
    std::cout << "Contains 8? " << (found ? "yes" : "no") << std::endl;

    std::set<int> uniqueNumbers(numbers.begin(), numbers.end());
    std::cout << "Unique count: " << uniqueNumbers.size() << std::endl;

    return 0;
}

Output:
Sorted: 1 2 3 3 5 5 8 8 9 
Contains 8? yes
Unique count: 6

Here, std::sort reorders the vector in place using an efficient introsort (a hybrid of quicksort, heapsort, and insertion sort). Once sorted, std::binary_search can check for a value in O(log n) time. Finally, constructing a std::set<int> directly from the vector’s iterator range automatically discards duplicates, since a set only ever stores unique keys.

How It Works Step by Step

• You declare a container by instantiating its template with a concrete type, e.g. vector<int>; the compiler generates a specialized class for that type.
• The container manages its own memory: vector allocates a contiguous heap block and grows it (usually by doubling) when it runs out of capacity; tree-based containers like map allocate individual nodes and link them together, keeping keys sorted as they’re inserted.
• An iterator is requested from the container (begin()/end()); it knows how to move to the “next” element for that specific container’s internal layout.
• An algorithm receives a pair of iterators and repeatedly dereferences and advances them, remaining completely unaware of whether it’s walking an array or a tree.
• When the container goes out of scope, its destructor automatically releases all owned memory — no manual delete is required, thanks to RAII (Resource Acquisition Is Initialization).

Common Mistakes

Mistake 1: Confusing std::array with std::vector

std::array has a fixed size decided at compile time and offers no way to add elements after creation. Calling push_back on it is a compile error, not a runtime one:

#include <iostream>
#include <array>

int main() {
    std::array<int, 3> numbers = {1, 2, 3};
    numbers.push_back(4); // error: no member named 'push_back' in 'std::array'
    for (int n : numbers) std::cout << n << " ";
    return 0;
}

The fix is to use std::vector when the number of elements can change at runtime:

#include <iostream>
#include <vector>

int main() {
    std::vector<int> numbers = {1, 2, 3};
    numbers.push_back(4);
    for (int n : numbers) std::cout << n << " ";
    std::cout << std::endl;
    return 0;
}

Output:
1 2 3 4 

std::array is a thin wrapper over a fixed-size C-style array and should only be used when the size is truly known and constant.

Mistake 2: Using operator[] to “check” whether a map key exists

std::map::operator[] silently inserts a default-constructed value if the key isn’t already present. Using it just to test existence corrupts the map:

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

int main() {
    std::map<std::string, int> inventory;
    inventory["apples"] = 10;

    if (inventory["bananas"] > 0) {
        std::cout << "We have bananas" << std::endl;
    } else {
        std::cout << "No bananas" << std::endl;
    }

    std::cout << "Map size: " << inventory.size() << std::endl;

    return 0;
}

Output:
No bananas
Map size: 2

Even though “bananas” was never explicitly added, the map now has two entries, because operator[] inserted "bananas" -> 0 the moment it was accessed. The fix is to use count() or find(), which never modify the map:

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

int main() {
    std::map<std::string, int> inventory;
    inventory["apples"] = 10;

    if (inventory.count("bananas") > 0) {
        std::cout << "We have bananas" << std::endl;
    } else {
        std::cout << "No bananas" << std::endl;
    }

    std::cout << "Map size: " << inventory.size() << std::endl;

    return 0;
}

Output:
No bananas
Map size: 1

Best Practices

• Default to std::vector unless you have a specific reason (frequent middle insertion/removal, need for sorted keys, etc.) to use another container.
• Prefer range-based for loops over manual iterator loops when you don’t need the iterator itself — they’re shorter and harder to get wrong.
• Use .at(index) instead of operator[] when you want bounds checking (it throws std::out_of_range on an invalid index, whereas operator[] is undefined behavior).
• Pass containers by const& to functions that only read them, to avoid unnecessary copies.
• Reserve capacity with vector::reserve(n) up front when you know roughly how many elements you’ll insert, to avoid repeated reallocations.
• Reach for an algorithm (std::sort, std::find, std::count, std::accumulate, etc.) before writing a manual loop — they’re well-tested and communicate intent clearly.
• Use unordered_map/unordered_set instead of map/set when you don’t need sorted order and want faster average-case lookups.

Practice Exercises

• Write a program that reads a sentence into a std::vector<std::string> of words (split on spaces) and prints the longest word.
• Build a std::map<char, int> that counts how many times each letter appears in a given string (ignore spaces), then print the counts in alphabetical order.
• Given a std::vector<int> of exam scores, use std::sort and std::max_element/std::min_element to print the sorted list along with the highest and lowest score.

Summary

• The STL provides three cooperating pieces: containers (data storage), iterators (traversal), and algorithms (operations), glued together through templates.
• std::vector is a dynamic, contiguous array that grows by reallocating and copying when its capacity is exceeded.
• std::map and std::set are typically tree-based, keeping elements in sorted key order with O(log n) operations.
• Algorithms like std::sort, std::find, and std::accumulate work through iterator ranges, so the same algorithm works across many container types.
• Common pitfalls include mixing up fixed-size std::array with resizable std::vector, and using map::operator[] for existence checks (use count() or find() instead).
• Favor STL containers and algorithms over hand-rolled data structures and loops — they are safer, well-tested, and usually just as fast or faster.