STL Containers and Algorithms

The Standard Template Library splits two jobs that beginners usually fuse. Containers own elements and decide where they live in memory. Algorithms operate on ranges of elements and know nothing about the container behind them.

That split is the design's whole payoff. One std::sort orders a vector, a deque, or a raw array. The sorting logic never changes. Only the storage differs.

An iterator is the bridge between the halves. It is a value you can advance, read through, and compare, with a documented complexity guarantee. The guarantee lets each algorithm demand exactly the movement power it needs.

Sequential containers default to vector

Sequential containers hold elements in programmer-controlled order. Four cover nearly every need:

std::vector wins the default because contiguity matches hardware. Iteration sweeps lines the prefetcher anticipates. Indexing is arithmetic. Bulk copies use wide memory operations directly.

Its one cost is geometric reallocation on growth, typically doubling capacity. Every element moves to the new buffer. Calling reserve() with a known size skips that work entirely.

std::list offers stable iterators across splices: rearranging never invalidates references to untouched nodes. Every traversal still chases pointers, so it suits splice-heavy algorithms, not general storage.

Ordered and unordered containers solve different lookups

Associative containers find elements by key. Two structures split the job:

The ordered family balances a binary search tree on every update. Every operation stays logarithmic. Iteration visits keys sorted, and range queries start at lower_bound nearly for free.

The unordered family hashes keys into buckets. Average lookup is constant with no order at all. A weak hash or adversarial keys collapse buckets into chains and restore linear cost.

Choose by the question, not by folklore. Need ranges or sorted output: ordered. Need raw lookup speed on ordinary keys: unordered. Microbenchmarks that ignore adversarial input mislead here.

Adapters narrow the interface on purpose

Adapters wrap a container and expose a smaller interface. std::stack offers push and pop over a deque by default. std::queue offers FIFO over the same. std::priority_queue offers push, pop, and top over a vector-backed max-heap.

The restriction is the feature. A function taking a stack cannot accidentally index the storage. The type states the access pattern, and the compiler enforces it.

Adapter costs follow the underlying container. Stack and queue operations cost O(1). Priority queue push and pop cost O(log n) for heap maintenance. Reading the top costs O(1) because the extreme always sits at the root.

One task in three languages: sort, find, and sum

The same small job below runs in each language's standard style. Sort five numbers. Find the value 8. Add everything up. Watch how each version states preconditions.

#include <algorithm>  // sort, find
#include <numeric>    // accumulate
#include <vector>
// Sort five numbers, locate 8, and sum everything with STL algorithms.
// Every algorithm takes an iterator range: begin() to end().
int demo() {
    // Contiguous storage: the iterator is effectively a pointer.
    std::vector<int> v = {5, 2, 8, 1, 9};
    // Introsort the whole range: O(n log n), needs random access.
    std::sort(v.begin(), v.end()); // v is now {1, 2, 5, 8, 9}
    // Linear scan for 8: O(n), returns an iterator to the match.
    auto it = std::find(v.begin(), v.end(), 8);
    bool found = (it != v.end()); // true: compare against end(), not null
    // Fold the range into one sum: O(n), starting from 0.
    int sum = std::accumulate(v.begin(), v.end(), 0); // 25
    // Binary search needs sorted input: O(log n) once sorted.
    bool has = std::binary_search(v.begin(), v.end(), 8); // true
    return sum + (found && has ? 0 : -1); // 25: both searches agreed
}

All three sort first, then search, then sum. All three respect the same precondition: binary search runs only on sorted data. Unsorted input returns garbage without complaint in every language.

Three preconditions recur across the library. binary_search requires sorted ranges. sort requires random-access iterators, which is why lists ship their own member sort. unique compacts duplicates to the front rather than erasing them; the container shrinks only after an explicit erase.

Complexities you can rely on across containers

The standard documents complexity as a contract. Swapping containers preserves algorithm code whenever the guarantee still holds.

One subtlety breaks swaps. Code that relies on contiguity, such as taking &v[0] and doing pointer arithmetic, fails on deque. Code that relies on sorted iteration fails on hash containers. Swap on guarantees, not on benchmarks.

Where the STL shape helps and what to read next

The split pays off at scale. Pipelines compose transform, copy_if, and accumulate without naming containers. Changing a vector to a deque touches declarations, not logic. Tests cover algorithms once and reuse them everywhere.

It also teaches restraint. Reaching for a hand-written loop invites boundary bugs the library already fixed. Reading the documented preconditions beats debugging a corrupted range.

Continue with searching and sorting for the strategy behind the calls. Read hash tables and trees and heaps for the structures behind the containers.