This is an interview with Conor Hoekstra about C++ algorithms and ranges.
Conor presented my favorite talk at CppCon 2019 called Algorithm Intuition. I asked him to talk about algorithms on this podcast and he agreed. This just proves again why CppCon is the best place to be when you want to improve your C++ skills. The presenters were all going beyond just getting up on stage and answering a few questions. They’re real people who are willing to talk and mingle and generally help out in many ways.
If you’d like to improve your coding skills, then browse the recommended books and resources at the Resources page. You can find all my favorite books and resources at this page to help you create better software designs. Most of the ideas discussed in this episode will only come in C++20 and there are no books that I know of yet that focus on C++20. You can learn about the existing STL algorithms which will help you be prepared when C++20 is generally available.
Listen to the episode for more details or read the summary below.
Summary
Have you given talks on algorithms at other conferences besides CppCon?
Conor gave versions of Algorithm Intuition at meetups in the Bay Area and in San Fransisco and then at conferences at CppCon 2019 and C++ Now in 2019.
What’s coming in C++ involving algorithms?
Conor is on the Canadian national body for ISO and he’s working on ranges in C++20 including 12 range adapters such as transform and reverse. There will be more range adapters being added in the future from the range-v3 library.
Conor works with other languages beyond C++ and there are range adapters included in these other languages. So it’s important to get the naming correct in C++ so people will know what to expect. We should follow precedence if possible that’s already been established.
Conor hopes to influence C++23, C++26, and C++29. Yes, C++29 comes up in committee meetings. This is because certain additions are optimistically targeting C++26 but might not arrive until C++29. ISO is definitely working towards a long term future.
What are the major changes coming in C++ algorithms?
There are two different things coming with ranges.
- The changes are more than updated algorithms that take data structures instead of iterator pairs. The new range based algorithms let you pass collections directly instead of begin() and end().
- The second part is a new piping syntax that lets you send the output from one algorithm into the next algorithm. This comes currently with adapters and potentially in the future with actions.
There will be more range adapters coming that will work with both of these changes.
What is piping syntax?
Most Linux systems let you pipe the output from one command and send it to another command. This lets you compose commands by chaining them together. The same syntax is used for algorithms. The pipe is the vertical bar symbol on your keyboard. For US based keyboards, this is right above the enter key.
As an example consider the need to calculate the number of unique words in a list. Ignoring for a moment the std::unique algorithm, how could this be done by composing other algorithms together?
First sort the list, then group the result, then take the head, and finally count the result.
For example, if you start with the collection a b c a b c a b c, then sorting will give you a a a b b b c c c. Going into the group algorithm will split the collection into a list of separate lists a a a, followed by b b b and then c c c. And then taking the head of each sublist gives you a collection with just a, b, and c. You can then count the items in the last result to get the answer.
This is difficult to do today without using std::unique. With the new range-v3, it’s easy to take the initial list, pipe it to sort, pipe it to group, pipe it to transform_head, and then pipe it to length.
If you need to learn just a handful of C++ algorithms, what would they be?
There’s one algorithm that’s most under appreciated. And that’s the algorithm std::accumulate. Ben Deane gave a talk previously at CppCon 2016 called “std::accumulate: Exploring an Algorithmic Empire”.
In this talk, Ben showed that almost all the standard algorithms can be implemented using std::accumulate. In other languages, this might be known as a fold or a reduce operation. This takes a list of items and reduces it down to a single item.
For example, std::max_element and std::min_element are both reducing algorithms. The default operation for std::accumulate is std::plus. But if you replace this default operator with std::max or std::min, then you get the same result as std::max_element and std::min_element.
What final recommendations do you have?
Conor recommends learning a new programming language each year. You don’t need to become an expert. A little knowledge will help you to write better C++ code.