Algorithms

An algorithm is a loop someone else wrote: it takes a pair of iterators and, when it needs a decision, a callable. A hand-written loop that searches a vector and a call to std::find do the same thing, and the second says what it does in its name.

The algorithms live in <algorithm> and work on any range, which is why lesson 049 came first. This lesson covers the four shapes that cover most uses: search, count, transform and remove.

Searching and counting

std::find returns an iterator to the first match or end() when there is none. Comparing the result with end() is the standard test, and the distance from begin gives the index.

std::count returns the number of matches. The program looks for 20 in a vector, prints its position and then counts the 10s.

Both are linear and both work on any input range. When the range is sorted, lesson 051 replaces them with a binary search.

An algorithm never changes the size of a container it only walks. That is why the remove family needs the erase call afterwards, and why an algorithm that writes into another range needs the output to have room already.

#include <algorithm> #include <iostream> #include <vector> int main() { std::vector<int> values{10, 20, 30, 10}; auto it = std::find(values.begin(), values.end(), 20); if (it != values.end()) { std::cout << "found at " << std::distance(values.begin(), it) << '\n'; } std::cout << "tens: " << std::count(values.begin(), values.end(), 10) << '\n'; }

g++ -std=c++23 -Wall -Wextra find.cpp -o find
./find

found at 1
tens: 2

Transforming a range

std::transform applies a function to every element and writes the results through another iterator. The output may be the same range or a different container, and the algorithm does not allocate anything itself.

The program doubles every value into a new vector, which was sized first so the output iterator has room. The original is unchanged and the copy holds the doubled values.

The function is a lambda in this example; lesson 052 covers lambdas properly, and any callable works here, including a function pointer or a function object from lesson 053.

#include <algorithm> #include <iostream> #include <vector> int main() { std::vector<int> values{1, 2, 3, 4}; std::vector<int> doubled(values.size()); std::transform(values.begin(), values.end(), doubled.begin(), [](int value) { return value * 2; }); for (int value : doubled) { std::cout << value << ' '; } std::cout << '\n'; }

g++ -std=c++23 -Wall -Wextra transform.cpp -o transform
./transform

2 4 6 8

Questions about a range

std::any_of, std::all_of and std::none_of answer a question with a predicate. find_if does the same search as find, with a condition instead of a value.

The program asks whether any value is negative, whether all are below 100, and finds the first even number. The answers are bools, and the search stops at the first element that decides the result.

A predicate takes one element and returns something convertible to bool. Keeping it small and side-effect free makes the algorithm's behaviour easy to reason about.

The three questions are deliberately named: any_of, all_of and none_of read as English, and a reader does not have to check whether an empty range makes the loop true or false. For an empty range any_of is false and all_of is true, the identity values of the operators.

#include <algorithm> #include <iostream> #include <vector> int main() { std::vector<int> values{3, 8, 12, 7}; std::cout << std::any_of(values.begin(), values.end(), [](int v) { return v < 0; }) << ' '; std::cout << std::all_of(values.begin(), values.end(), [](int v) { return v < 100; }) << '\n'; auto even = std::find_if(values.begin(), values.end(), [](int v) { return v % 2 == 0; }); std::cout << *even << '\n'; }

g++ -std=c++23 -Wall -Wextra predicates.cpp -o predicates
./predicates

0 1
8

remove_if and erase

std::remove_if does not remove anything: it moves the elements to keep to the front and returns the new logical end. The elements after that point are still in the vector, which is why the erase call follows.

The program removes the numbers below 10 from a vector of six and prints what is left. The size afterwards is the number of kept elements, and the remove_if call alone would have left the vector the same size.

The erase-remove idiom is two lines and is the standard way to delete from a container whose elements are contiguous. A list has its own remove_if that erases in place.

#include <algorithm> #include <iostream> #include <vector> int main() { std::vector<int> values{4, 15, 6, 21, 8, 30}; values.erase(std::remove_if(values.begin(), values.end(), [](int v) { return v < 10; }), values.end()); for (int value : values) { std::cout << value << ' '; } std::cout << '\n'; }

g++ -std=c++23 -Wall -Wextra remove.cpp -o remove
./remove

15 21 30

A predicate that is not callable

The last argument of find_if is a callable. Passing a number is a type error, and the compiler lists the overload it tried and the argument it could not use.

The program passes 42 where a predicate belongs. The message begins with the include trace of <algorithm>, names the algorithm and the call, and ends with the line that matters: the expression cannot be used as a function. Read the last error first.

A lambda, a function pointer and a function object all work; a value does not. The same error appears when a lambda's parameter type does not match the element type.

#include <algorithm> #include <vector> int main() { std::vector<int> values{1, 2, 3}; auto it = std::find_if(values.begin(), values.end(), 42); return it == values.end(); }

g++ -std=c++23 -Wall -Wextra not_callable.cpp -o not_callable

In file included from /usr/include/c++/15.2.0/bits/stl_algobase.h:71,
from /usr/include/c++/15.2.0/algorithm:62,
from not_callable.cpp:1:
/usr/include/c++/15.2.0/bits/predefined_ops.h: In instantiation of 'constexpr bool __gnu_cxx::__ops::_Iter_pred<_Predicate>::operator()(_Iterator) [with _Iterator = __gnu_cxx::__normal_iterator<int*, std::vector<int> >; _Predicate = int]':
/usr/include/c++/15.2.0/bits/stl_algobase.h:2095:42: required from 'constexpr _Iterator std::__find_if(_Iterator, _Iterator, _Predicate) [with _Iterator = __gnu_cxx::__normal_iterator<int*, vector<int> >; _Predicate = __gnu_cxx::__ops::_Iter_pred<int>]'
2095 | while (__first != __last && !__pred(__first))
| ~~~~~~^~~~~~~~~
/usr/include/c++/15.2.0/bits/stl_algo.h:3921:28: required from 'constexpr _IIter std::find_if(_IIter, _IIter, _Predicate) [with _IIter = __gnu_cxx::__normal_iterator<int*, vector<int> >; _Predicate = int]'
3921 | return std::__find_if(__first, __last,
| ~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~
3922 | __gnu_cxx::__ops::__pred_iter(__pred));
| ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
not_callable.cpp:7:27: required from here
7 | auto it = std::find_if(values.begin(), values.end(), 42);
| ~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
/usr/include/c++/15.2.0/bits/predefined_ops.h:318:30: error: expression cannot be used as a function
318 | { return bool(_M_pred(*__it)); }
| ~~~~~~~^~~~~~~

Exercises

  1. Count how many strings in a vector start with a capital letter, using count_if.
  2. Copy the even numbers of one vector into another with copy_if and a back_inserter.
  3. Use replace to change every 0 in a vector to 1 and print the result.

Questions

A new set of questions in a new order every time. Choose one answer for each, then check.

  1. What does an algorithm take as its input?

    Answer

    A pair of iterators and, when needed, a callable

    The iterator pair names the range, and the callable supplies the decision.

  2. What does std::find return when the value is absent?

    Answer

    The end iterator

    The result is compared with end(), which is the not-found value.

  3. What does std::transform do?

    Answer

    It writes a function of each element to the output range

    The algorithm applies the callable to each element and stores the result.

  4. Why does remove_if need erase afterwards?

    Answer

    remove_if moves the kept elements and returns the new logical end

    The algorithm cannot change the container's size, so erase cuts the tail it marked.

  5. What does this program print? #include <algorithm> #include <iostream> #include <vector> int main() { std::vector<int> values{7, 10, 20, 3}; auto found = std::find(values.begin(), values.end(), 10); std::cout << "found at " << (found - values.begin()) << '\n'; std::cout << "tens: " << std::count_if(values.begin(), values.end(), [](int v) { return v % 10 == 0; }); }

    Answer

    found at 1 / tens: 2

    10 is the second element, and two values are multiples of ten.

  6. What does this program print? #include <algorithm> #include <iostream> #include <vector> int main() { std::vector<int> values{1, 2, 3, 4}; std::transform(values.begin(), values.end(), values.begin(), [](int v) { return v * 2; }); for (int value : values) std::cout << value << ' '; }

    Answer

    2 4 6 8

    The transform writes twice each element back into the same range.

  7. What does this program print? #include <algorithm> #include <iostream> #include <vector> int main() { std::vector<int> values{3, 8, 1, 12}; std::cout << std::any_of(values.begin(), values.end(), [](int v) { return v > 10; }) << ' '; std::cout << std::all_of(values.begin(), values.end(), [](int v) { return v > 0; }) << '\n'; std::cout << std::count(values.begin(), values.end(), 8); }

    Answer

    1 1 / 1

    The 12 is above ten, every value is positive, and the value 8 occurs once.

  8. What does this program print? #include <algorithm> #include <iostream> #include <vector> int main() { std::vector<int> values{15, 21, 8, 30}; values.erase(std::remove_if(values.begin(), values.end(), [](int v) { return v < 10; }), values.end()); for (int value : values) std::cout << value << ' '; }

    Answer

    15 21 30

    The predicate removes the 8, and erase cuts the moved tail.

  9. What does the compiler report for this call? #include <algorithm> #include <vector> int main() { std::vector<int> values{1, 2, 3}; std::count_if(values.begin(), values.end(), 3); }

    Answer

    expression cannot be used as a function

    The third argument must be a predicate, and an int is not callable.

  10. What is the advantage of std::find over a hand-written loop?

    Answer

    The name says what the loop does and the code is shorter

    The algorithm is a named, tested loop, which is easier to read and to review.

The code on this page was built with g++ 15.2.0 and run on Alpine Linux 3.24.3 (x86_64) in a Docker container. The programs whose section shows a compiler error were compiled until that error and were not run.

Article author: Arthur Isaev