Data structures and algorithms

A data structure organizes values; an algorithm describes steps to solve a problem. Choosing them well can change a program's performance dramatically. First identify what operations are frequent, then choose a structure that supports those operations clearly.

Common structures and their trade-offs

• std::vector: contiguous storage, fast indexed access, and efficient append at the end on average. Inserting near the front shifts later elements.
• std::deque: efficient operations at both ends, with different locality and iterator rules than a vector.
• std::list: stable iterators and local insertion/removal, but no constant-time indexing and often poor cache locality. Use it only when those properties matter.
• std::set and std::map: ordered unique keys, typically logarithmic lookup and insertion.
• std::unordered_set and std::unordered_map: hash-based lookup, average constant-time operations, no stable ordering, and possible worst-case degradation.
• std::queue and std::stack: adapters for first-in-first-out and last-in-first-out access.

Reason about complexity

Big-O notation describes how work grows with input size, ignoring constant factors and lower-order terms. Linear search is O(n); binary search on sorted random-access data is O(log n); sorting is typically O(n log n). Complexity is a useful model, not a measurement of actual elapsed time.

#include <algorithm>
#include <vector>

std::vector<int> values{6, 2, 9, 2};
std::sort(values.begin(), values.end());
const bool present =
    std::binary_search(values.begin(), values.end(), 6);

Binary search requires sorted input and a compatible ordering. Prefer standard algorithms such as std::sort, std::lower_bound, and std::accumulate when their contracts match your task.

Start with the operations your program needs

Imagine a program that stores a queue of jobs. If it only adds jobs at the back and removes them from the front, a queue adapter describes the intended behavior better than a vector and a collection of hand-written index updates. If the program repeatedly asks for the smallest pending job, a priority queue may be a better fit. Matching the data structure to the operations reduces both implementation work and opportunities for mistakes.

Write down the important operations and how often they occur. Does the program need random access by index? Does it insert or remove near the middle? Must it preserve order? Does it need to find a key quickly? Does it allow duplicates? The answers narrow the choices and make performance discussions concrete.

Understand the common complexity classes

O(1) describes work that stays roughly constant as the input grows. O(log n) grows slowly, as in binary search on sorted random-access data. O(n) is linear scanning. O(n log n) is common for comparison sorting. A pair of nested loops over all pairs may be O(n²). These classes describe growth rates, not exact times or guarantees that one implementation is always faster for small inputs.

Also consider memory complexity. A faster algorithm may require an additional copy or auxiliary table. In a memory-constrained program, extra storage can be more important than a reduction in comparisons. State whether your estimate counts the input itself and whether the algorithm modifies it in place.

Algorithms require preconditions

Binary search is only correct when the range is sorted according to the same ordering used by the search. If the input is not sorted, a successful-looking result can be wrong. Many standard algorithms also have requirements about iterator categories, value comparison, or whether the range may be modified. Read those contracts and make the preconditions visible in the calling code.

A useful algorithm explanation includes the input conditions, the result produced, and important edge cases. For a search, ask what happens on an empty range, when there are duplicates, and when the target is absent. For sorting, ask whether stability matters and whether equal elements should retain their previous order.

Measure realistic workloads

Before optimizing, create a repeatable workload that resembles real input: similar size, distribution, and usage. Build using the intended configuration and run the test multiple times if measurements vary. Avoid measuring file loading, console output, or unrelated setup when the question is specifically about a container operation.

Benchmarking tiny inputs can mostly measure startup and timer overhead. Very large inputs can trigger different cache and allocation behavior. Record both the data size and environment so results have context. If a data structure change improves one operation but slows another, compare the overall workload rather than reporting only the favorable case.

Correctness before optimization

State the algorithm's preconditions and postconditions. Test empty and duplicate-heavy input. Measure a representative workload before tuning: asymptotic complexity, memory use, allocation cost, cache behavior, and constant factors all influence performance.

Practice

1. Compare linear search and binary search, including binary search's sorted-input requirement.
2. Count word frequencies with std::unordered_map.
3. Choose a container for a workload that frequently removes the smallest value.
4. Estimate the number of operations in a nested loop over an input of size n.
5. Describe the input precondition for std::binary_search and demonstrate what fails when it is violated.
6. Compare storing unique usernames in a vector, ordered set, and unordered set based on lookup and output requirements.
7. Measure a container operation at several input sizes and compare the growth trend, not just one timing.

Key idea: choose data structures based on required operations and use complexity analysis plus measurement to evaluate the result.

Correctness proofs and loop invariants

An algorithm is more than code that seems to work on examples. Specify its input domain, output relation, and termination condition. A loop invariant captures what remains true at each iteration; a termination argument shows that a well-founded measure decreases. Together, they can establish a partial-correctness argument and eventual completion. This method is practical for binary search, partitioning, parsing, and iterative dynamic programming.

For binary search, define the range of candidate positions precisely and maintain the invariant that any valid answer lies within that range. The update must shrink the range while preserving the invariant. An incorrect midpoint or boundary update can cause an infinite loop or skip the correct answer. Test empty and one-element inputs, but use the invariant to reason about all sizes.

Amortized analysis and data-structure guarantees

Worst-case analysis considers the most expensive operation for a given input size; average-case analysis depends on a probability model; amortized analysis bounds a sequence of operations even when an occasional operation is expensive. Vector append is a classic example: a reallocation may cost linear time, but geometric growth gives amortized constant-time append over a sequence, subject to the implementation's growth strategy and the standard's complexity requirements.

Hash-table lookup is average constant time under suitable hashing and load behavior, not a universal worst-case guarantee. Adversarial keys or poor hash functions can degrade performance. For untrusted inputs, consider denial-of-service risks and containers or hashing policies with appropriate bounds.

Lower bounds and choosing an algorithmic model

Comparison sorting has a lower bound of order n log n comparisons in the general comparison model, but specialized assumptions can enable different algorithms. Counting sort can be linear when keys come from a suitably small integer range, at the cost of extra memory. Radix methods exploit digit structure. The lower bound applies to a model of computation, not every possible representation or domain.

When comparing algorithms, state the model: comparison count, memory accesses, allocations, parallel work, or worst-case latency. Asymptotic analysis can omit costs that dominate on real hardware, while measurements can obscure scaling if the inputs are too small. Use both reasoning and controlled measurement.

Algorithm engineering and reproducible benchmarks

Benchmark valid implementations on representative data and include warm-up, repeated runs, and appropriate timing tools. Prevent the compiler from eliminating work that has no observable result. Separate input generation and I/O from the measured operation when they are not part of the target workload. Report compiler, flags, hardware, data distribution, and variance.

When a benchmark suggests an improvement, test correctness independently and measure the complete application. A micro-optimization can shift cost elsewhere or make cache behavior worse for realistic data. Preserve a clear baseline so future changes can be compared honestly.

Advanced exercise

1. Prove a binary-search implementation correct using a stated invariant and termination measure.
2. Compare worst-case, average-case, and amortized bounds for a hash table and vector operations.
3. Choose a non-comparison sort for a constrained key domain and state the extra assumptions and memory cost.
4. Publish a small benchmark report with source, data generation, build flags, environment, and repeated results.