STL Containers, Iterators, Algorithms and Complexity

1. The Standard Library Model

The C++ Standard Library combines reusable containers, iterators, algorithms, function objects and utilities. A container owns elements. An iterator identifies a position. An algorithm works over iterator ranges. This separation lets one sorting algorithm work with many compatible sequence types.

Container choice affects memory layout, lookup cost, insertion cost, reference stability and ordering. Select a container from the operations the program performs, not from habit.

2. Half-Open Ranges

Algorithms conventionally receive a range written [first, last). first identifies the first element and last identifies the position just after the final element.

std::vector<int> values{4, 1, 3};
std::sort(values.begin(), values.end());

The position returned by end is a sentinel and must not be dereferenced. An empty range has first equal to last. Half-open ranges compose cleanly: [a, b) followed by [b, c) covers [a, c) without overlap.

3. Iterator Categories

Iterator categories describe supported movement and access:

• input iterators support single-pass reading;
• output iterators support single-pass writing;
• forward iterators support multipass forward traversal;
• bidirectional iterators also move backward;
• random-access iterators support constant-time jumps and differences;
• contiguous iterators additionally represent adjacent objects in memory.

An algorithm states the minimum category it needs. std::sort requires random access, so it works with vector and deque iterators but not list iterators. std::list provides its own sort member suited to linked nodes.

4. std::vector

vector is a dynamically sized contiguous sequence. It offers constant-time indexing, efficient iteration and compatibility with APIs that consume a contiguous array through data().

std::vector<int> values;
values.push_back(10);
values.emplace_back(20);

Its size is the number of constructed elements. Its capacity is the amount of storage currently available before reallocation is required.

reserve increases capacity when needed without changing size. resize changes the number of elements, constructing or destroying elements accordingly.

Appending is amortized constant time: most appends are constant, while occasional growth allocates a larger block and moves or copies existing elements. Insertion or erasure near the beginning shifts later elements and is linear.

5. Vector Invalidation

Reallocation changes the storage address, invalidating all pointers, references and iterators to elements. An insertion without reallocation invalidates positions at and after the insertion point. Erasure invalidates the erased position and positions after it.

Do not retain an element address across an operation that may grow the vector unless capacity has been controlled and the exact invalidation rule permits it. Indices may be safer than iterators in some designs, but insertion and erasure can change which element an index denotes.

6. array, deque and list

std::array<T, N> is a fixed-size contiguous container whose size is part of its type. It supports standard iterators without dynamic allocation for its own storage.

std::deque is a dynamically sized sequence designed for efficient insertion and removal at both ends. Its storage is segmented rather than one contiguous block, so it does not expose all elements as one C-style array.

std::list is a doubly linked sequence. Insertion and erasure at a known position are constant time and do not move other elements. Finding that position is linear, indexing is unavailable and each node carries links and allocation overhead. Poor cache locality often makes vector faster even for some workloads with insertions.

std::forward_list is singly linked and supports only forward traversal with a smaller node structure.

7. Sequence Selection

Use vector as the default sequence when contiguous storage and indexed or sequential access fit. Use deque when both ends change frequently. Use list only when stable iterators and frequent splicing or known-position insertion justify node costs. Use array for fixed compile-time size.

Big-O notation alone is insufficient. Allocation frequency, cache behavior, element size and actual operation counts can dominate. Measure important workloads after choosing a structurally suitable container.

8. Ordered Associative Containers

std::set stores unique keys in sorted order. std::multiset permits equivalent keys. std::map stores unique key-value pairs and std::multimap permits equivalent keys.

These containers are commonly implemented as balanced trees. Lookup, insertion and erasure are logarithmic in the number of elements. Iteration follows key order.

The comparator defines a strict weak ordering. Two keys are equivalent when neither compares before the other. They need not be equal under operator==.

std::map<std::string, int> counts;
++counts["apple"];

map's subscript performs access-or-insert. If the key is absent, it inserts a value-initialized mapped value. Use find or contains in newer standards for a pure presence check; C++17 code uses find.

9. Unordered Associative Containers

unordered_set and unordered_map organize elements into hash buckets. Under suitable hashing and load assumptions, lookup, insertion and erasure are average constant time. Worst-case lookup is linear when many keys occupy the same bucket.

A custom key needs a hash function and an equality relation. Equal keys must always produce equal hash values. Unequal keys may collide.

Rehashing changes bucket organization and invalidates iterators, although references and pointers to elements have stronger stability under specified operations. reserve can prepare buckets for an expected element count and reduce rehashing.

Use an ordered container when sorted traversal, logarithmic worst-case behavior or range queries matter. Use an unordered container when average direct lookup is central and order is irrelevant.

10. Container Adapters

Adapters expose a restricted interface over an underlying container.

std::stack provides last-in, first-out behavior through push, top and pop. std::queue provides first-in, first-out behavior through push, front, back and pop. std::priority_queue exposes the element with highest priority according to its ordering and supports push, top and pop.

pop removes an element but does not return it. Read top or front first, then pop. Do not access an empty adapter.

11. Iteration

A range-based for loop is concise:

for (const auto& value : values) {
    std::cout << value << '\n';
}

Use const auto& to observe without copying, auto& to modify and auto when a copy is desired. Iterator loops are needed when position, erasure or multiple ranges matter:

for (auto it = values.begin(); it != values.end(); ++it) {
    *it *= 2;
}

Const iterators prevent element modification through the iterator. Reverse iterators traverse from the end toward the beginning.

12. Iterator Invalidation During Erasure

Erasing while iterating requires using the operation's returned next iterator:

for (auto it = values.begin(); it != values.end();) {
    if (*it < 0) {
        it = values.erase(it);
    } else {
        ++it;
    }
}

Incrementing an invalidated iterator is undefined behavior. Invalidation rules differ among containers, so consult the operation's contract rather than assuming node-container rules apply to vector.

13. Core Algorithms

The algorithm header includes operations such as find, count, sort, reverse, transform, copy, remove_if and binary_search.

auto found = std::find(values.begin(), values.end(), target);

std::transform(values.begin(), values.end(),
               output.begin(),
               [](int x) { return x * x; });

Algorithms work through iterators and usually do not own storage. The destination range for copy or transform must already have enough space or an insertion iterator such as back_inserter must be used.

14. Lambdas

A lambda defines an unnamed callable:

int limit = 10;
auto count = std::count_if(
    values.begin(), values.end(),
    [limit](int value) { return value > limit; });

The capture list controls access to surrounding variables. [limit] copies one value, [&limit] captures it by reference, [=] uses value capture by default and [&] uses reference capture by default.

Reference captures must not outlive their source objects. Capture only what the operation needs and use const behavior unless mutation is intentional.

15. Sorting and Comparators

std::sort provides O(n log n) comparison complexity for random-access ranges and does not preserve relative order of equivalent elements. std::stable_sort preserves it.

std::sort(records.begin(), records.end(),
          [](const Record& a, const Record& b) {
              return a.score < b.score;
          });

The comparator must define a strict weak ordering. comp(x, x) must be false and ordering must be transitive. Using <= violates this requirement and can produce undefined algorithm behavior.

After sorting, binary_search tests presence. lower_bound finds the first position not ordered before a value and upper_bound finds the first position ordered after it. These algorithms require a range ordered by a compatible comparator.

16. The Remove-Erase Pattern

Algorithms named remove do not shrink a general container. They rearrange retained elements toward the front and return a new logical end:

auto newEnd = std::remove_if(
    values.begin(), values.end(),
    [](int x) { return x < 0; });
values.erase(newEnd, values.end());

This remove-erase pattern physically erases the trailing elements from vector. Container member functions can offer more direct erasure for associative containers.

17. Accumulation and Numeric Algorithms

The numeric header provides accumulate:

long long total = std::accumulate(
    values.begin(), values.end(), 0LL);

The initial value supplies both the starting value and an important part of result-type deduction. Starting with 0 would accumulate as int even when a wider result is intended.

Other numeric algorithms generate sequences, compute inner products and derive partial or adjacent results. Ensure the operation's arithmetic and overflow properties match the selected type.

18. Complexity Vocabulary

Constant O(1) means the operation's work does not grow with element count under the stated model. Logarithmic O(log n) grows slowly, commonly through a balanced tree or binary search. Linear O(n) examines or shifts a proportion of the elements. O(n log n) is typical for comparison sorting. Quadratic O(n²) often results from nested full-range processing.

Amortized complexity averages expensive events across a sequence of operations. Vector append is amortized O(1), although an individual reallocation is O(n).

Complexity describes growth and requires its preconditions. Hash lookup is average O(1), not guaranteed constant. Binary search is logarithmic in comparisons but a forward iterator may still require linear movement.

19. Ownership and Element Types

Containers own their element objects. A container of raw pointers owns only pointer values unless the program defines an external ownership rule. Use unique_ptr for exclusive owned polymorphic objects and shared_ptr only for genuine shared lifetime.

Copying a container copies its elements. Moving normally transfers internal resources efficiently, subject to allocator and element rules. References and views into elements remain governed by the container's invalidation behavior.

For large objects, emplace can construct an element from arguments at its destination, but it does not guarantee that no move or allocation occurs during container growth. Prefer clear construction over using emplace mechanically.

20. Selecting and Combining Facilities

State the required behavior first: ordered traversal, unique keys, fast lookup, stable references, random access or insertion at an end. Choose the container whose guarantees match. Then use library algorithms rather than hand-written loops when the algorithm expresses the intent directly.

Check preconditions: range validity, destination capacity, required iterator category, comparator ordering and container invalidation. Combine complexity with memory behavior and measurement. The Standard Library is effective because ownership, traversal and operations are separate but governed by precise contracts.