STL Algorithms — Use common <algorithm> functions (sort, find, count) (intro) - C Plus Plus

SECTION 1

Historical Context & Motivation

Before the Standard Template Library (STL) existed, C++ programmers routinely wrote their own sorting routines, search loops, and counting logic for every new project. Each implementation was tightly coupled to a specific data structure — a sort written for a raw array could not easily be reused on a linked list. This duplication was not merely tedious; it was a fertile source of bugs. Alexander Stepanov, a mathematician and computer scientist, envisioned a library where algorithms and data structures could be combined orthogonally through the abstraction of iterators. His collaboration with Meng Lee at Hewlett-Packard produced the STL, which was adopted into the C++ Standard in 1998 and fundamentally reshaped how C++ programmers think about algorithmic work.

1979 • Stepanov's Generic Programming Vision

Alexander Stepanov begins formalizing the idea that algorithms should be decoupled from data structures through abstract interfaces, drawing on ideas from abstract algebra.

1994 • STL Presented to the C++ Standards Committee

Stepanov and Meng Lee present the STL to the ISO C++ committee. Andrew Koenig champions the proposal, and the committee votes to integrate it into the draft standard.

1998 • C++98 Standard Published

The first ISO C++ Standard (C++98) ships with the <algorithm> header containing over 60 generic algorithms, including sort, find, and count.

2011 • C++11 Modernizes the STL

Lambda expressions, move semantics, and range-based for loops make STL algorithms dramatically more convenient and expressive to use.

2020 • C++20 Introduces Ranges

The Ranges library (std::ranges) provides composable, pipeline-style algorithm invocation, building directly on the iterator-based architecture Stepanov established decades earlier.

The central question the STL algorithms answer is deceptively simple: how can we write an algorithm once and have it work correctly across vectors, arrays, deques, and any other sequence that exposes iterators? The <algorithm> header is the STL's answer, and sort, find, and count are among its most frequently used inhabitants.

SECTION 2

Core Principles & Definitions

The STL's algorithm library rests on a small set of powerful design principles that every C++ programmer should internalize before reaching for #include <algorithm>. Understanding these principles makes it clear why the function signatures look the way they do and why the library is so composable.

Iterator-Based Interfaces

Every STL algorithm operates on a half-open range [first, last) defined by two iterators. The algorithm never knows the container type — only the iterator category matters.

Value Semantics & Predicates

Algorithms like sort compare elements using operator< by default, but accept custom comparators or predicates as optional callable arguments — function pointers, functors, or lambdas.

No Container Modification

Algorithms never insert or erase elements. They rearrange, copy, or inspect values through iterators. Container-level mutations (like erasing removed elements) must be done separately — the erase-remove idiom is a classic example.

Complexity Guarantees

The C++ Standard mandates worst-case or average-case complexity bounds for every algorithm. std::sort guarantees O(n log n) comparisons; std::find and std::count are O(n).

Header Inclusion

All three algorithms reside in <algorithm> within the std namespace. You must #include <algorithm> before invoking them.

✦

KEY TAKEAWAY

Think of STL algorithms as universal power tools and iterators as standardized adapters. A drill (algorithm) does not care whether it is attached to a wooden board or a steel plate — it only needs the correct adapter bit (iterator). Similarly, std::sort does not care whether data lives in a vector or a raw array; it only requires random-access iterators. This decoupling is the architectural genius of the STL.

SECTION 3

Visual Explanation — The Iterator-Algorithm Architecture

The three pillars of the STL: containers store data, iterators provide positional access, and algorithms perform operations. The arrows show that algorithms never touch containers directly — iterators mediate every interaction.

In the diagram above, notice that each container on the left exposes iterators (center column) and that every algorithm on the right consumes iterators — never containers. This indirection is what makes the STL so extensible: if you write a new container that provides the right iterator category, every existing algorithm automatically works with it. Conversely, if you write a new algorithm that accepts iterators, it works with every existing container. The combinatorial explosion of M containers × N algorithms is handled by a thin iterator layer rather than M × N specialized implementations.

SECTION 4

How sort, find, and count Work Under the Hood

std::sort — Signature & Semantics

The std::sort function template rearranges elements in the range [first, last) into non-decreasing order by default. It requires random-access iterators, which means it works on std::vector, std::deque, std::array, and raw arrays, but not on std::list (which provides only bidirectional iterators — use list::sort() member instead). Most standard library implementations use Introsort — a hybrid of quicksort, heapsort, and insertion sort — to guarantee O(n log n) worst-case comparisons.

SORT SIGNATURES

void sort(RandomIt first, RandomIt last); void sort(RandomIt first, RandomIt last, Compare comp);

The first overload uses operator< for comparison. The second accepts a custom comparator comp — any callable returning bool that defines a strict weak ordering.

std::find — Signature & Semantics

The std::find function performs a linear search through the range [first, last), returning an iterator to the first element equal to the given value, or last if no match is found. Because it only requires input iterators, it works with every standard container. Equality is tested using operator==. The related std::find_if variant accepts a unary predicate instead of a value.

FIND SIGNATURE

InputIt find(InputIt first, InputIt last, const T& value);

Returns an iterator to the first element satisfying *it == value, or last if none found. Complexity: at most n comparisons.

std::count — Signature & Semantics

The std::count function traverses the entire range and returns the number of elements equal to a given value. Like find, it requires only input iterators and uses operator==. Its sibling std::count_if counts elements satisfying a predicate. The return type is typename iterator_traits<InputIt>::difference_type, typically ptrdiff_t.

COUNT SIGNATURE

difference_type count(InputIt first, InputIt last, const T& value);

Always traverses the full range — Θ(n) comparisons, no early exit.

SECTION 5

Detailed Breakdown — sort, find, count in Action

A step-by-step trace of sort, find, and count applied to the same vector. Notice how find returns an iterator (pointing to index 5), while count returns an integer (3).

Algorithm	Iterator Requirement	Return Type	Complexity	Mutating?
`std::sort`	RandomAccess	`void`	O(n log n)	Yes (reorders elements)
`std::find`	Input	`InputIt`	O(n)	No (read-only)
`std::count`	Input	`difference_type`	Θ(n)	No (read-only)

Comparison of sort, find, and count signatures and performance characteristics

ℹ

Important Distinction

Note the difference between O(n) and Θ(n) in the table. std::find is O(n) because it can terminate early upon finding the first match — best case is Ω(1). In contrast, std::count is Θ(n) because it must always traverse the entire range to produce an accurate count.

SECTION 6

Worked Example — Analyzing Student Scores

Suppose we have a std::vector<int> storing exam scores: {88, 72, 95, 72, 60, 88, 100, 72, 85}. We want to: (1) sort the scores in ascending order, (2) check whether a score of 95 exists, and (3) count how many students scored exactly 72.

Using sort, find, and count on Exam Scores

1
Step 1 — Include the header and set up data

Begin by including <algorithm> and <vector>. Declare the vector: std::vector<int> scores = {88, 72, 95, 72, 60, 88, 100, 72, 85};
2
Step 2 — Sort the scores

Call std::sort(scores.begin(), scores.end()); — this rearranges the elements in-place. The vector is now: {60, 72, 72, 72, 85, 88, 88, 95, 100}. The sort uses the default operator< for ascending order.

Sorted: {60, 72, 72, 72, 85, 88, 88, 95, 100}
3
Step 3 — Find whether 95 exists

Call auto it = std::find(scores.begin(), scores.end(), 95); — the returned iterator points to the element at index 7 in the sorted vector. We verify it was found by checking it != scores.end(), which evaluates to true. We can also compute the zero-based index via std::distance(scores.begin(), it), yielding 7.

Found: 95 at index 7
4
Step 4 — Count occurrences of 72

Call auto n = std::count(scores.begin(), scores.end(), 72); — the function scans all 9 elements, comparing each to 72, and returns 3. The variable n has type ptrdiff_t (the iterator's difference type).

Count of 72: 3
5
Step 5 — Bonus: sort descending with a custom comparator

To sort in descending order, pass a lambda: std::sort(scores.begin(), scores.end(), [](int a, int b){ return a > b; }); — alternatively, use the standard functor std::greater<int>() from <functional>. The result is {100, 95, 88, 88, 85, 72, 72, 72, 60}.

Descending: {100, 95, 88, 88, 85, 72, 72, 72, 60}

SECTION 7

Strengths, Limitations & Alternatives

Aspect	Strengths	Limitations / Caveats
std::sort	Highly optimized (Introsort), O(n log n) guaranteed, accepts custom comparators, works on any random-access sequence.	Not stable — equal elements may be reordered. Use `std::stable_sort` if relative order matters. Cannot be used with `std::list` or `std::forward_list`.
std::find	Works on any container with input iterators, simple interface, early termination on match.	Always linear — O(n). For sorted data, prefer `std::binary_search` or `std::lower_bound` for O(log n). For associative containers, use their member `.find()` methods.
std::count	Simple, universally applicable, pairs well with `count_if` for predicate-based counting.	Always Θ(n) — no early exit. For sorted ranges, `std::equal_range` + distance is O(log n). For multisets/maps, use `.count()` member.

Strengths and limitations of sort, find, and count

🔍

WHEN TO REACH FOR SOMETHING ELSE

The three algorithms covered here are general-purpose workhorses, but the STL offers specialized alternatives when constraints allow. Think of it like choosing between a Swiss Army knife and a dedicated tool: std::find is the Swiss Army knife of searching (works anywhere, linear time), while std::lower_bound is a precision instrument that requires a sorted range but delivers logarithmic performance. As you design real systems, always ask: "Is my data sorted? Do I have a container with built-in search?" — and pick the right tool.

SECTION 8

Connection to Advanced STL & Modern C++

The three algorithms introduced here form the gateway to a much richer ecosystem. Understanding their iterator-based design prepares you for the entire <algorithm> suite — over 100 algorithms in C++20 — as well as the Ranges library and parallel algorithms introduced in C++17/C++20.

Introductory Concept	Advanced Extension	Key Difference
`std::sort(first, last)`	`std::ranges::sort(container)`	Ranges version accepts a container directly (no explicit begin/end), supports projections, and provides better error messages via concepts.
`std::find(first, last, val)`	`std::ranges::find(container, val)`	Same linear search, but constrained by concepts. Pipeable with views for composable data processing.
Sequential execution	`std::sort(std::execution::par, ...)`	Execution policies (C++17) enable parallel, vectorized, or unsequenced execution of algorithms with a single extra argument.
`std::count_if` with lambda	`views::filter \| ranges::distance`	Ranges views enable lazy, composable pipelines — filtering and counting become part of a declarative chain rather than separate algorithm calls.

From introductory algorithms to advanced C++ features

As you progress through your coursework, you will encounter algorithms like std::transform, std::accumulate, std::partition, and std::unique — each following the same iterator-pair convention you have just learned. The mental model is transferable: once you understand how sort, find, and count interact with iterators, every new algorithm in the header will feel familiar.

SECTION 9

Practice Problems

Question 1: CONCEPTUAL

Explain why std::sort cannot be called on a std::list<int>, even though both std::find and std::count work perfectly on it. What iterator category does each algorithm require, and what does std::list provide?

Show answer

std::sort requires random-access iterators because efficient sorting algorithms (like Introsort) rely on constant-time element access at arbitrary positions and the ability to compute distances and perform iterator arithmetic (e.g., it + n). std::list only provides bidirectional iterators, which support increment (++) and decrement (--) but not random jumps. In contrast, std::find and std::count only need input iterators — they traverse the sequence linearly from begin to end without ever jumping to arbitrary positions. Since bidirectional iterators are a refinement of input iterators, they satisfy find and count's requirements. Lists offer their own member function list::sort() which uses a merge sort adapted for linked-list node manipulation.

Question 2: BASIC CALCULATION

Given std::vector<int> v = {4, 7, 2, 7, 9, 7, 1};, write the exact call to std::count to determine how many times the value 7 appears, and state the return value.

Show answer

The call is: auto n = std::count(v.begin(), v.end(), 7); The function traverses all 7 elements, comparing each to 7 using operator==. Elements at indices 1, 3, and 5 match, so the return value is 3. The type of n is std::vector<int>::difference_type, which is typically ptrdiff_t (a signed integer type). Note that count always examines every element — it cannot short-circuit because it must produce a complete tally.

Question 3: INTERMEDIATE

Write a complete C++ code snippet that: (a) creates a std::vector<std::string> containing {"banana", "apple", "cherry", "apple", "date"}, (b) sorts it alphabetically, (c) uses std::find to locate "cherry" and prints its index, and (d) uses std::count to print how many times "apple" appears.

Show answer

After sorting, the vector becomes {"apple", "apple", "banana", "cherry", "date"}. The code: std::vector<std::string> v = {"banana", "apple", "cherry", "apple", "date"}; std::sort(v.begin(), v.end()); auto it = std::find(v.begin(), v.end(), "cherry"); if (it != v.end()) std::cout << "cherry at index: " << std::distance(v.begin(), it) << std::endl; // prints 3. auto n = std::count(v.begin(), v.end(), "apple"); std::cout << "apple count: " << n << std::endl; // prints 2. The default sort on strings uses lexicographic comparison via std::string's operator<. The find call uses operator== on strings, which performs content comparison. std::distance computes the offset from begin() to the found iterator.

Question 4: APPLIED

You are building a grading system. Given a vector of exam scores, you need to: sort them to determine the median, check whether any student scored a perfect 100, and count how many students scored below 60 (failing). Write the algorithm calls, using std::sort, std::find, and std::count_if. Explain why count_if is needed rather than count for the failing-score query.

Show answer

First, std::sort(scores.begin(), scores.end()); sorts ascending. The median is scores[scores.size()/2] for odd-length vectors (or the average of the two middle elements for even-length). Second, auto it = std::find(scores.begin(), scores.end(), 100); checks for a perfect score; if it != scores.end(), at least one student scored 100. Third, auto failing = std::count_if(scores.begin(), scores.end(), [](int s){ return s < 60; }); counts students below 60. We need count_if rather than count because we are testing a predicate (score < 60) rather than matching a single exact value. std::count only checks equality against one value, while std::count_if accepts any unary predicate — making it the right tool for range-based conditions.

Question 5: CRITICAL THINKING

A classmate argues: "Since std::sort is O(n log n) and std::find is O(n), I should sort my data first and then use std::binary_search every time I need to search." Under what conditions is this strategy beneficial, and under what conditions is it worse than simply calling std::find repeatedly? Analyze the total asymptotic complexity for m searches on n elements in both cases.

Show answer

Using std::find m times on unsorted data costs O(m × n). The sort-then-binary-search approach costs O(n log n) for the sort plus O(m × log n) for m binary searches, totaling O(n log n + m log n). For large m (many searches), sort-then-binary-search wins because m × log n grows much slower than m × n. Specifically, the crossover occurs roughly when m exceeds O(1) — even a handful of searches can justify sorting. However, the sort-first strategy is worse if: (1) you perform only one or two searches, since the O(n log n) sort dominates O(n) find; (2) the data must remain in its original order (sort mutates); or (3) elements are inserted dynamically between searches, requiring re-sorting. In practice, if the data is static and you anticipate multiple queries, sorting once and using binary_search or lower_bound is the superior engineering choice. For a single lookup, std::find is simpler and faster.

SUMMARY

Lesson Summary

Summary

The <algorithm> header provides a rich collection of generic functions that operate on iterator-defined ranges, decoupling algorithms from container types. std::sort rearranges elements in O(n log n) using Introsort and requires random-access iterators; it accepts an optional comparator for custom orderings. std::find performs a linear search returning an iterator to the first match or last if not found, while std::count traverses the entire range to return the number of matching elements.

All three algorithms follow the half-open range convention [first, last) and rely on operator< or operator== by default, with predicate-accepting variants (find_if, count_if) for custom logic. The complexity guarantees mandated by the Standard make it possible to reason about performance without inspecting implementation details. Mastering these three foundational algorithms equips you with the mental model — iterators as the universal interface — needed to leverage the full power of the STL.