Searching with Standard Algorithms

Say you have a set of values and want to test whether a specific value is contained in that set. Writing a hand coded test for this is easy; however, this pattern is used so frequently that the standard library ships with ready made algorithms to handle it. The algorithms work with any sequence that provides a pair of iterators, allowing the same call to search through a std::vector, a std::array, or various other containers.

Take an ordinary std::vector and a loop that searches for 30.

#include <iostream>
#include <vector>

int main()
{
    std::vector v{ 10, 20, 30, 40, 50 };

    auto it{ v.begin() };

    // Repeat the block while this condition remains true
    while (it != v.end() && *it != 30)
        ++it;

    if (it != v.end())
        std::cout << "found " << *it << '\n';
    else
        std::cout << "not found\n";

    return 0;
}

The loop increments it until the end is reached or the number 30 is found. Then the program tests whether it is equal to v.end(), and since it is not, it knows that the number was present and that *it is the required value. It outputs "found 30". The logic is sound, but the same loop would need to be recreated for every search.

Exactly the same work is done by the algorithm std::find. It takes as arguments two iterators defining the range to investigate and the value to search.

#include <algorithm>
#include <iostream>
#include <vector>

int main()
{
    std::vector v{ 10, 20, 30, 40, 50 };

    // Find the requested value and return its iterator
    auto it{ std::find(v.begin(), v.end(), 30) };

    if (it != v.end())
        std::cout << "found " << *it << '\n';
    else
        std::cout << "not found\n";

    return 0;
}

The std::find begins at the iterator returned by v.begin() and moves forward until it finds an element equal to 30 or reaches the past the end iterator returned by v.end(). The value returned by find is an iterator that points to the first matching element or v.end() if the search didn't return any result. Since the iterator returned is compared against v.end(), the rest of the program remains the same as in the handwritten version. The call itself is shorter and more explicit: the person reading the code understands that the search takes place right away.

The returned iterator will be end when the target isn't in the range, so dereferencing the returned iterator would result in undefined behavior. We can see an example of the right pattern here.

#include <algorithm>
#include <iostream>
#include <vector>

int main()
{
    std::vector v{ 10, 20, 40, 50 };

    // Let the initializer determine this variable type
    auto it{ std::find(v.begin(), v.end(), 30) };

    if (it != v.end())
        std::cout << "found " << *it << '\n';
    else
        std::cout << "30 is not present\n";

    return 0;
}

The value 30 never gets printed, it is equal to v.end() and it prints the message that reports not found. The comparison against end() is therefore not optional, it is the only way to find out if the search is successful.

Sometimes equality isn't enough. Maybe you want the first even number, or the first string longer than a certain length. For those cases, there is std::find_if in the library, which takes a predicate in place of a value. The predicate is any callable that takes one element and returns a Boolean.

#include <algorithm>
#include <iostream>
#include <vector>

int main()
{
    std::vector v{ 11, 22, 33, 44, 55 };

    // Find the first element satisfying this predicate
    auto it{ std::find_if(v.begin(), v.end(),
                          [](int n) { return n % 2 == 0; }) };

    if (it != v.end())
        std::cout << "first even is " << *it << '\n';
    else
        std::cout << "no even numbers\n";

    return 0;
}

The lambda returns true for the first even number it sees, which is 22. So std::find_if returns an iterator referring to that element. If we had encountered only odd numbers, it would again have been equal to v.end(). The algorithm terminates on the first success, so the later even numbers are never considered.

A similar algorithm is std::count. Instead of pointing to the first appearance of a value, it returns how many times a value appears. It returns an integer.

#include <algorithm>
#include <iostream>
#include <vector>

int main()
{
    std::vector v{ 5, 10, 5, 15, 5, 20 };

    // Count elements equal to this value
    auto n{ std::count(v.begin(), v.end(), 5) };

    std::cout << "5 appears " << n << " times\n";

    return 0;
}

std::count goes through the whole range, counting how many times the value 5 appears. The total count is 3, so the program prints this. We can be confident that this is the correct number as all values are checked by the algorithm, no matter how many times the value appears.

All of these algorithms consider the pair of iterators as a half open range: the first iterator is part of the range, the second is not. Providing as arguments two iterators where the second one does not belong to the same sequence, or has been invalidated by a reallocation, has undefined effects. These algorithms do not modify the container.

They only read the content of the elements pointed to by the iterators.

If the container is subsequently modified, the iterator obtained previously may be invalidated.

Many other searching algorithms share the same iterator pair interface. After understanding the general pattern introduced by std::find, the predicate version std::find_if and the counter version std::count are a natural extension. They all turn a self made loop into a single well named call for any container that can give suitable iterators.

#include <iostream>
#include <vector>

int main()
{
    std::vector v{ 10, 20, 30, 40, 50 };

    auto it{ v.begin() };

    // Repeat the block while this condition remains true
    while (it != v.end() && *it != 30)
        ++it;

    if (it != v.end())
        std::cout << "found " << *it << '\n';
    else
        std::cout << "not found\n";

    return 0;
}

#include <algorithm>
#include <iostream>
#include <vector>

int main()
{
    std::vector v{ 10, 20, 30, 40, 50 };

    auto it{ std::find(v.begin(), v.end(), 30) };

    if (it != v.end())
        std::cout << "found " << *it << '\n';
    else
        std::cout << "not found\n";

    return 0;
}

found 30