Search

6.18 — Introduction to standard library algorithms

New programmers typically spend a lot of time writing custom loops to perform relatively simple tasks, such as sorting or counting or searching arrays. These loops can be problematic, both in terms of how easy it is to make an error, and in terms of overall maintainability, as loops can be hard to understand.

Because searching, counting, and sorting are such common operations to do, the C++ standard library comes with a bunch of functions to do these things in just a few lines of code. Additionally, these standard library functions come pre-tested, are efficient, work on a variety of different container types, and many support parallelization (the ability to devote multiple CPU threads to the same task in order to complete it faster).

The functionailty provided in the algorithms library generally fall into one of three categories:

  • Inspectors -- Used to view (but not modify) data in a container. Examples include searching and counting.
  • Mutators -- Used to modify data in a container. Examples include sorting and shuffling.
  • Facilitators -- Used to generate a result based on values of the data members. Examples include objects that multiply values, or objects that determine what order pairs of elements should be sorted in.

These algorithms live in the algorithms library. In this lesson, we’ll explore some of the more common algorithms -- but there are many more, and we encourage you to read through the linked reference to see everything that’s available!

Note: All of these make use of iterators, so if you’re not familiar with basic iterators, please review lesson 6.17 -- Introduction to iterators.

Using std::find to find an element by value

std::find searches for the first occurrence of a value in a container. std::find takes 3 parameters: an iterator to the starting element in the sequence, an iterator to the ending element in the sequence, and a value to search for. It returns an iterator pointing to the element (if it is found) or the end of the container (if the element is not found).

For example:

Sample run when the element is found

Enter a value to search for and replace with: 5 234
13 90 99 234 40 80

Sample run when the element isn’t found

Enter a value to search for and replace with: 0 234
Could not find 0
13 90 99 5 40 80

Using std::find_if to find an element that matches some condition

Sometimes we want to see if there is a value in a container that matches some condition (e.g. a string that contains a specific substring) rather than an exact value. In such cases, std::find_if is perfect. The std::find_if function work similarly to std::find, but instead of passing in a value to search for, we pass in a callable object, such as a function pointer (or a lambda, which we’ll cover later) that checks to see if a match is found. std::find_if will call this function for every element until a matching element is found (or no more elements remain in the container to check).

Here’s an example where we use std::find_if to check if any elements contain the substring “nut”:

Output

Found walnut

If you were to write the above example by hand, you’d need at least two loops (one to loop through the array, and one to match the substring). The standard library functions allow us to do the same thing in just a few lines of code!

Using std::count and std::count_if to count how many occurrences there are

std::count and std::count_if search for all occurrences of an element or an element fulfilling a condition.

In the following example, we’ll count how many elements contain the substring “nut”:

Output

Counted 2 nut(s)

Using std::sort to custom sort

We previously used std::sort to sort an array in ascending order, but std::sort can do more than that. There’s a version of std::sort that takes a function as its third parameter that allows us to sort however we like. The function takes two parameters to compare, and returns true if the first argument should be ordered before the second. By default, std::sort sorts the elements in ascending order.

Let’s use std::sort to sort an array in reverse order using a custom comparison function named greater:

Output

99 90 80 40 13 5

Once again, instead of writing our own custom loop functions, we can sort our array however we like in just a few lines of code!

Tip

Because sorting in descending order is so common, C++ provides a custom type (named std::greater) for that too (which is part of the functional header). In the above example, we can replace:

with:

Note that the std::greater{} needs the curly braces because it is not a callable function. It’s a type, and in order to use it, we need to instantiate an object of that type. The curly braces instantiate an anonymous object of that type (which then gets passed as an argument to std::sort).

Using std::for_each to do something to all elements of a container

std::for_each takes a list as input, applies a custom function to every element. This is useful when we want to perform the same operation to every element in a list.

Here’s an example where we use std::for_each to double all the numbers in an array:

Output

2 4 6 8

This often seems like the most unnecessary algorithm to beginners, because equivalent code with a range-based for-loop is shorter and easier. std::for_each allows the loop-body to be re-used and it can be parallelized, making it better suited for large projects and big data than a range-based for-loop.

Order of execution

Note that most of the algorithms in the algorithms library do not guarantee a particular order of execution. For such algorithms, take care to ensure any functions you pass in do not assume a particular ordering, as the order of invocation may not be the same on every compiler.

The following algorithms do guarantee sequential execution: std::for_each, std::copy, std::copy_backward, std::move, and std::move_backward.

Best practice

Unless otherwise specified, do not assume that standard library algorithms will execute in a particular sequence. std::for_each, std::copy, std::copy_backward, std::move, and std::move_backward have sequential guarantees.

Ranges in C++20

Having to explicitly pass arr.begin() and arr.end() to every algorithm is a bit annoying. But fear not -- C++20 adds ranges, which allow us to simply pass arr. This will make our code even shorter and more readable.

Conclusion

The algorithms library has a ton of useful functionality that can make your code simpler and more robust. We only cover a small subset in this lesson, but because most of these functions work very similarly, once you know how a few work, you can make use of most of them.

Best practice

Favor using functions from the algorithms library over writing your own functionality to do the same thing


6.x -- Chapter P.6 comprehensive quiz
Index
6.17 -- Introduction to iterators

15 comments to 6.18 — Introduction to standard library algorithms

  • salah

    Hi,
    what is wrong witht that?

    it's expected to print a bool, but i got an error saying
    {No operator '=' matches these operands}

    • nascardriver

      You're missing "std::" before `cout`. You capitalized "String" in "std::String". You're missing parentheses around the comparison.
      `<<` is executed first. You're printing `std::string::npos` and then comparing `std::cout != name.find("sa")`.

  • salah

    Hi, I was wondering what is the arguments of our function will be : in this line for instance,

    arr.begin and arr.end return pointers to the first and the spot beyond the last element in the array... And what happens after that ? I mean how the pointers will be converted into int and be passed to the array?

  • In paragraph 5, it refers to the "reference linked above" - what reference?  There are no links above this on the page.

  • paprika

    std::greater should be include type declaration just like (std::greater<int>) in C++ 11.

  • kavin

    Hi, i can't understand how this works?

    what does the returned std::string_view::npos do?

    Also under std::sort , we have 2 parameters in

    How do we determine how many parameters to take ?(because so far we have taken 1 parameter for 1 argument...) I see function names "containsNut/doubleNumber". Which ones are the exact arguments to consider for the resp functions ?

    • nascardriver

      `std::string_view::find` returns the index at which the substring was found. If it doesn't find the substring, it returns the special value `std::string_view::npos` (Similarly, `std::string::find` returns `std::string::npos`).

      `std::sort` uses the function to compare 2 elements to each other. If it took only one argument, it wouldn't be able to compare it to anything. You can look this up on cppreference (We're using the version marked with (3)).

  • Ged

    I wrote a code when the user has to put the input. We cannot input std::string_view. I wrote the function inside the std::find_if just to know it is possible to do it that way as well.

    Question 1 Is the code above a good solution to the problem i wrote?

    Question 2 When we write the whole function inside our algorithm like std::find_if, can we do something with "[]" or does it stand for a one time use nameless function?

    Question 3 When there is a "_if" at the end, that means we need to use a function? If there is no "_if" where it is possible we need to use variable or something similar, but not a function?

    Question 4 Why don't we need to use parenthesis at the end of our function "containsNut"? EXAMPLE auto nuts{ std::count_if(arr.begin(), arr.end(), containsNut) };

    Question 5 When we are using standard library algorithms we use auto for our new variable. Is the data type is super long, is it good practice to be using auto instead of a specific data type?

    • nascardriver

      1
      You can use `std::find_if` for any type of `std::vector`. You don't need a `std::string_view`.
      If you want to copy the `std::vector` for whatever reason, you can do so without `std::copy`:

      The rest of your code looks good :)

      2
      That's a lambda function. Lambdas are covered in chapter 7.

      3
      There are functions without an "_if" postfix that require a function. Those with an "_if" postfix require a function.

      4
      We're not calling `containsNut`, `std::count_if` is calling `containsNut`. We're passing the functions itself, not the return value, to `std::count_if`. Function pointers are also covered in chapter 7.

      5
      If the type is obvious, very long, or doesn't matter, use `auto`. For example in the lambda you're passing to `std::find_if`, it's obvious that the parameter has the type of the vector's elements, so you can use `auto` without sacrificing readability.

  • Matt

    I just had to :)  Glad to see this site is still being updated!

    • nascardriver

      You don't even need to write a function do print lists:

      We're using loops in the lessons, because they're easier for beginners. Maybe we'll add some single-line action in later lessons :)

Leave a Comment

Put all code inside code tags: [code]your code here[/code]