More Algorithms

You now know sort, count and count_if, and you can give an algorithm your own rule with a lambda. This lesson adds a few more algorithms that you will use often, mostly for searching.

find

find looks for a value in a range. Like sort, it comes from <algorithm>. It returns an iterator to the first element that matches:

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int main() {
    vector<int> waits = {40, 10, 25, 10};

    auto it = find(waits.begin(), waits.end(), 25);
    cout << *it << "\n";
    cout << "index: " << it - waits.begin() << "\n";
    return 0;
}

Output:

25
index: 2

For a vector, it - waits.begin() gives the index of the element: how many steps it is from the start.

What if the value is not there? Then find returns end(). Always compare with end() before you read *it:

vector<int> waits = {40, 10, 25, 10};

auto it = find(waits.begin(), waits.end(), 99);
if (it == waits.end()) {
    cout << "99 is not there" << "\n";
}

Output:

99 is not there

accumulate

accumulate adds up all the values in a range. It lives in a different header, <numeric>. Its third argument is the starting value of the total:

#include <iostream>
#include <vector>
#include <numeric>
using namespace std;

int main() {
    vector<int> waits = {40, 10, 25, 10};
    cout << accumulate(waits.begin(), waits.end(), 0)
         << "\n";
    return 0;
}

Output:

85

Be careful with the starting value. Its type is the type of the running total. Here the prices are doubles, but the start is 0, an int:

vector<double> prices = {1.5, 2.25, 3.5};
cout << accumulate(prices.begin(), prices.end(), 0)
     << "\n";
cout << accumulate(prices.begin(), prices.end(), 0.0)
     << "\n";

Output:

6
7.25

The first answer is 6, not 7.25. Because the total was an int, each step dropped the decimals: 0 + 1.5 became 1, then 1 + 2.25 became 3, then 3 + 3.5 became 6. There was no error and no warning. With 0.0 as the start, the total is a double and the answer is right.

binary_search

find checks the elements one by one. For a big vector, that can be slow. If the vector is sorted, binary_search is much faster. It looks at the middle element and throws away the half where the value cannot be. Then it does the same with the half that is left. It returns true (1) or false (0):

vector<int> waits = {40, 10, 25, 10, 5};
cout << binary_search(waits.begin(), waits.end(), 40)
     << "\n";

sort(waits.begin(), waits.end());
cout << binary_search(waits.begin(), waits.end(), 40)
     << "\n";

Output:

0
1

40 is in the vector both times. But before the sort, binary_search said 0. It expects sorted data and does not check, so on unsorted data its answer can be wrong. Sort first.

find_if and any_of

These two take a lambda, like count_if. find_if returns an iterator to the first element for which the lambda returns true. any_of only tells you whether there is at least one such element:

vector<int> waits = {40, 10, 25, 10};

auto it = find_if(waits.begin(), waits.end(),
                  [](int w) { return w < 20; });
cout << *it << "\n";

cout << any_of(waits.begin(), waits.end(),
               [](int w) { return w > 50; })
     << "\n";

Output:

10
0

The first wait under 20 is 10. No wait is over 50, so any_of returns 0. Like find, find_if returns end() when nothing matches.

In the exercise, add up a list of numbers with accumulate, and use find to print the index of a number, or "Not found".