8 Key Standard Library Algorithms

The next chapter of the course introduces over 50 algorithms from the standard library. We can use these to solve a huge range of problems we’re likely to encounter when we’re working on our projects.

Before we go in deep, it’s worth highlighting some of the particularly useful algorithms. Here, we introduce eight algorithms that are very commonly needed.

To reinforce our knowledge, we will also weave in techniques from previous lessons, including views, projections, iterators, and subranges. Remember, these and similar techniques can be applied to any algorithm in the standard library, not just the ones we’re using in this lesson.

1. The for_each() Algorithm

The std::ranges::for_each() algorithm accepts a range as its first argument and a function as its second. The function is then invoked for every element in the range, receiving that element as an argument.

The following example uses for_each() to log every value in a collection:

1#include <vector>
2#include <iostream>
3#include <algorithm>
4
5int main(){
6  std::vector Numbers{1, 2, 3, 4, 5};
7
8  std::ranges::for_each(Numbers, [](int x){
9    std::cout << x << ", ";
10  });
11}

11, 2, 3, 4, 5,

In many cases, the for_each() algorithm can replace other forms of iteration, such as a range-based for loop.

This is especially true when the function we want to invoke already exists, allowing our for_each() call to be both succinct and descriptive:

1#include <vector>
2#include <iostream>
3#include <algorithm>
4
Log Function|Show
5void Log(int Number) {/*...*/};
9
10int main(){
11  std::vector Numbers{1, 2, 3, 4, 5};
12
13  std::ranges::for_each(Numbers, Log);
14}

11, 2, 3, 4, 5,

In these examples, we copy the values into the function we pass to for_each(). But, we can avoid this by passing them as a const reference, or a non-const reference if we want to modify the values in place.

Below, we double all of the values in our collection:

1#include <vector>
2#include <iostream>
3#include <algorithm>
4
Log Function|Show
5void Log(int Number) {/*...*/};
9
10int main(){
11  std::vector Numbers{1, 2, 3, 4, 5};
12
13  std::ranges::for_each(Numbers, [](int& x){
14    x *= 2;
15  });
16
17  std::ranges::for_each(Numbers, Log);
18}

12, 4, 6, 8, 10,

As a reminder, for_each() and most of the other standard library algorithms we cover in this lesson and the next chapter can interact with projection functions, views, iterators, and subranges. This gives us a lot more flexibility - we can combine these techniques as required to solve our specific use cases.

Projection Functions

A projection function receives each element of our collection as an argument, and can then return a different value. It is this value - the projection - that will then be used within the algorithm.

The following example uses a projection function to project each value in our collection to double its value. It is then these projections that are sent to our Log() function:

1#include <algorithm>
2#include <iostream>
3#include <vector>
4
Log Function|Show
5void Log(int Number) {/*...*/};
9
10int Double(int Number){ return Number * 2; }
11
12int main(){
13  std::vector Numbers{1, 2, 3, 4, 5};
14  std::ranges::for_each(Numbers, Log, Double);
15}

12, 4, 6, 8, 10,

It’s worth remembering that this is not doubling the values in our Numbers function. The Log() function is called with projections of the values in our collection. These projections are based on the original values but are different objects. The values in our original Numbers collection are unchanged by the previous code.

Additionally, the value returned by the projection function need not be the same type as the argument it receives. Below, our projection function receives a custom Character object, and returns a std::string based on that Character:

1#include <algorithm>
2#include <iostream>
3#include <vector>
4
Log Function|Show
5void Log(std::string Name) {/*...*/};
9
Character Class|Show
10class Character {/*...*/};
16
17std::string GetName(Character& Character){
18  return Character.Name;
19}
20
21int main(){
22  using namespace std::string_literals;
23  std::vector<Character> Characters{
24    "Anna"s, "Roderick"s, "Bob"s};
25
26  std::ranges::for_each(Characters, Log,
27                        GetName);
28}

1Anna, Roderick, Bob,

Views

Our algorithms can work on views. This gives us the option to change our data at the collection level before handing it to our algorithm. The following example logs our objects in reverse order using the std::views::reverse view:

1#include <algorithm>
2#include <ranges>
3#include <iostream>
4#include <vector>
5
Log Function|Show
6void Log(int Number) {/*...*/};
10
11int main(){
12  std::vector Numbers{1, 2, 3, 4, 5};
13
14  std::ranges::for_each(
15    std::views::reverse(Numbers), Log);
16}

15, 4, 3, 2, 1,

We can also use a view to restrict the algorithm to run only on a subset of our data. In this example, we use the std::views::filter view to only have the algorithm act on the objects in our collection that are odd:

1#include <algorithm>
2#include <iostream>
3#include <vector>
4#include <ranges>
5
Log Function|Show
6void Log(int Number) {/*...*/};
10
11bool isOdd(int Num){ return Num % 2 == 1; }
12
13int main(){
14  std::vector Numbers{1, 2, 3, 4, 5};
15
16  std::ranges::for_each(
17    std::views::filter(Numbers, isOdd), Log);
18}

11, 3, 5,

Views can be composed together using the | operator, giving us even more options. Below, we run our algorithm on only the odd numbers that are within the initial 3 objects in our collection:

1#include <algorithm>
2#include <iostream>
3#include <vector>
4#include <ranges>
5
Log Function|Show
6void Log(int Number) {/*...*/};
10
11bool isOdd(int Num){ return Num % 2 == 1; }
12
13int main(){
14  std::vector Numbers{1, 2, 3, 4, 5};
15
16  std::ranges::for_each(
17    std::views::take(Numbers, 3) |
18    std::views::filter(isOdd) |
19    std::views::reverse,
20    Log);
21}

13, 1,

Iterator-Sentinel Pairs

All of the algorithms we cover in this lesson, and the next chapter, allow us to define our ranges using iterator-sentinel pairs. Below, we use this to pass only a subset of our collection to the for_each() algorithm:

1#include <algorithm>
2#include <iostream>
3#include <vector>
4
Log Function|Show
5void Log(int Number) {/*...*/};
9
10int main(){
11  std::vector Numbers{1, 2, 3, 4, 5};
12
13  std::ranges::for_each(Numbers.begin() + 1,
14                        Numbers.end() - 1, Log);
15}

12, 3, 4,

Subranges

We can combine an iterator pair into a subrange using the std::ranges::subrange utility. Below, we create a subrange comprising the middle three elements of our collection:

1#include <algorithm>
2#include <vector>
3
4int main(){
5  std::vector Numbers{1, 2, 3, 4, 5};
6  auto Subrange{
7    std::ranges::subrange(Numbers.begin() + 1,
8                          Numbers.end() - 1)};
9}

A subrange is a view and can be used like any other view, and composed with other views in the usual ways. Below, we compose our subrange with std::views::reverse, and pass the result of that expression to the for_each() algorithm alongside our Log() function.

This causes the middle three elements of our collection to be logged in reverse order:

1#include <algorithm>
2#include <iostream>
3#include <vector>
4#include <ranges>
5
Log Function|Show
6void Log(int Number) {/*...*/};
10
11int main(){
12  std::vector Numbers{1, 2, 3, 4, 5};
13
14  std::ranges::for_each(
15    std::ranges::subrange(Numbers.begin() + 1,
16                          Numbers.end() - 1) |
17    std::views::reverse,
18    Log);
19}

14, 3, 2,

We won’t always call these techniques out when covering future algorithms, but they always apply. We can use views, iterators, and projections as needed to get our desired behavior.

2. The transform() Algorithm

The std::ranges::transform() function populates a range by passing values from some other range into a function. The return value of each successive function call is then used to populate the target range.

The most basic usage of the transform() function accepts three arguments:

1. The input range
2. An iterator pointing to where the outputs should be placed. We need to ensure there is enough memory allocated at this location to accommodate our results.
3. The transformer - a function that implements the transformation

In this example, our Output vector is populated with double the values of our Input vector:

1#include <algorithm>
2#include <iostream>
3#include <vector>
4
Log Function|Show
5void Log(int Number) {/*...*/};
9
10int main(){
11  std::vector Input{1, 2, 3, 4, 5};
12  std::vector<int> Output;
13
14  // Ensure there is enough memory allocated
15  // to hold the output of the algorithm
16  Output.resize(Input.size());
17
18  std::ranges::transform(Input, Output.begin(),
19                         [](int x){
20                           return x * 2;
21                         });
22
23  std::ranges::for_each(Output, Log);
24}

12, 4, 6, 8, 10,

The output allocator can be the same as the beginning of the input range, allowing us to transform our objects in place.

1#include <algorithm>
2#include <iostream>
3#include <vector>
4
Log Function|Show
5void Log(int Number) {/*...*/};
9
10int main(){
11  std::vector Input{1, 2, 3, 4, 5};
12
13  std::ranges::transform(Input, Input.begin(),
14                         [](int x){
15                           return x * 2;
16                         });
17
18  std::ranges::for_each(Input, Log);
19}

12, 4, 6, 8, 10,

Algorithm Return Values and std::ranges::in_out_result

The transform() algorithm, and many of the other algorithms we’ll encounter in this lesson and in the next chapter, have a return value. This return value tends to be useful for follow-up operations.

Algorithms that accept one input range and one output range typically return a std::ranges::in_out_result. This is often aliased to other names based on the algorithm we’re using. For example, the previous transform() examples alias this return type as std::ranges::unary_transform_result.

However, the underlying type is the same across various algorithms. std::ranges::in_out_result is a struct with two fields:

• in - An iterator pointing to where the input range ended. If the end of our range is denoted by an iterator, in will be equal to that iterator. If the end of our range is denoted by any other type of sentinel, in will be the iterator that triggered that sentinel.
• out - An iterator that is past the last element inserted into the output range

These are usually accessed by structured binding. We show some examples of how they can be used for follow-up operations below:

1#include <algorithm>
2#include <iostream>
3#include <vector>
4
Log Function|Show
5void Log(int Number) {/*...*/};
9
10int main(){
11  std::vector Input{1, 2, 3, 4, 5};
12  std::vector<int> Output;
13
14  Output.resize(8);
15
16  auto [in, out] = std::ranges::transform(
17    Input, Output.begin(),
18    [](int x){ return x * 2; });
19
20  std::cout << "Output: ";
21  std::ranges::for_each(Output, Log);
22
23  std::cout << "\nObjects Transformed: " <<
24    std::distance(Output.begin(), out);
25
26  std::cout << "\nLast Object: " << *(out - 1);
27
28  Output.erase(out, Output.end());
29  std::cout << "\nTrimmed Output: ";
30  std::ranges::for_each(Output, Log);
31}

1Output: 2, 4, 6, 8, 10, 0, 0, 0,
2Objects Transformed: 5
3Last Object: 10
4Trimmed Output: 2, 4, 6, 8, 10,

Binary Transform

The transform() algorithm is also overloaded to accept two input ranges. Our transformer function is then invoked with the objects in the same position of both inputs. The return values of those function calls are then used to populate our output.

Below, we populate our output by adding the numbers from two input ranges.

1#include <algorithm>
2#include <iostream>
3#include <vector>
4
Log Function|Show
5void Log(int Number) {/*...*/};
9
10int main(){
11  std::vector Input1{1, 2, 3, 4, 5};
12  std::vector Input2{2, 3, 4, 5, 6};
13  std::vector<int> Output;
14  Output.resize(Input1.size());
15
16  std::ranges::transform(
17    Input1, Input2, Output.begin(),
18    [](int x, int y){ return x + y; });
19
20  std::ranges::for_each(Output, Log);
21}

For example, the first object in Input1 is 1, the first object in Input2 is 2, and our transformer function adds the two arguments together. As such, the first object in Output will be 3.

This process continues until we have combined all of our inputs:

13, 5, 7, 9, 11,

Standard Library Operators

Within the <functional> header, the standard library includes templated function objects for most standard operators.

We can use these to replace lambdas that are similar to what we had in the previous example. We could alternatively have written it like this:

1std::ranges::transform(Input1, Input2,
2                       Output.begin(),
3                       std::plus{}
4);

std::ranges::in_in_out_result

This variant of the transform function also has a return value. However, in this case, given the algorithm has two inputs and one output, its return type is a std::in_in_out result.

Algorithms that return this type typically alias it. In this case, it’s aliased to a std::ranges::binary_transform_result. However, the underlying value is consistent across all algorithms that use it.

It is a struct with three fields:

• in1 - An iterator pointing to the end of the first input range - equivalent to Input1.end() in our previous example
• in2 - An iterator pointing to the end of the second input range - equivalent to Input2.end() in our previous example
• out - An iterator that is past the last element inserted into the output range

As before, these values tend to be accessed by structured binding:

1#include <algorithm>
2#include <iostream>
3#include <vector>
4
5int main(){
6  std::vector Input1{1, 2, 3, 4, 5};
7  std::vector Input2{2, 3, 4, 5, 6};
8  std::vector<int> Output;
9  Output.resize(10);
10
11  auto [in1, in2, out]{
12    std::ranges::transform(Input1, Input2,
13                           Output.begin(),
14                           std::plus{})};
15
16  std::cout << "Output Size: " << Output.size();
17  Output.erase(out, Output.end()); 
18  std::cout << "\nNew Size: " << Output.size();
19}

1Output Size: 10
2New Size: 5

3. The equal() Algorithm

The std::ranges::equal() algorithm returns true if the values in two ranges are equal, and in the same order:

1#include <algorithm>
2#include <iostream>
3#include <vector>
4
5int main(){
6  std::vector Input1{1, 2, 3};
7  std::vector Input2{1, 2, 3};
8
9  if (std::ranges::equal(Input1, Input2)) {
10    std::cout << "Ranges are equal";
11  }
12}

1Ranges are equal

The equal() algorithm, and most other algorithms that perform comparisons on our objects, allow us to customize the nature of those comparisons.

By default, the equal() algorithm compares our object using the == operator. If that operator returns true, the algorithm considers our objects to be equal.

However, we can customize the comparison by passing an additional argument to our algorithm. That function will receive two of our objects, and should return true if the algorithm should consider the objects equal.

Below, we use std::ranges::equal with a custom comparer to determine if the absolute value of our objects are equal:

1#include <algorithm>
2#include <iostream>
3#include <vector>
4
5int main(){
6  std::vector Input1{1, 2, 3};
7  std::vector Input2{-1, -2, -3};
8
9  auto AbsEqual{
10    [](int x, int y){
11      return std::abs(x) == std::abs(y);
12    }};
13
14  if (std::ranges::equal(Input1, Input2,
15                         AbsEqual)) {
16    std::cout << "Ranges are equal";
17  }
18}

1Ranges are equal

In this case, we can implement the same behavior using a projection function.

In the following example, the third argument to equal() is {}, as we want to use the default comparison function. We then pass two projection functions, as we have two inputs. The first projection function will apply to objects in the first input, whilst the second function will apply to objects in the second input.

In this case, we use the same projection function for each input range:

1#include <algorithm>
2#include <iostream>
3#include <vector>
4
5int main(){
6  std::vector Input1{1, 2, 3};
7  std::vector Input2{-1, -2, -3};
8
9  auto Abs{[](int x){ return std::abs(x); }};
10
11  if (std::ranges::equal(Input1, Input2, {},
12                         Abs, Abs)) {
13    std::cout << "Ranges are equal";
14  }
15}

1Ranges are equal

Our requirements are not always met simply by projection functions. Without a custom comparison function, our projected values are still going to be compared by the == operator, which is not always what we want.

Below, rather than using the == operator, our comparison function returns true if the objects are approximately equal:

1#include <algorithm>
2#include <iostream>
3#include <vector>
4
5int main(){
6  std::vector Input1{1.01f, 1.99f, 3.02f};
7  std::vector Input2{1.00f, 2.01f, 2.98f};
8
9  auto isApproximatelyEqual{
10    [](float x, float y){
11      return std::abs(x - y) < 0.1;
12    }};
13
14  if (std::ranges::equal(Input1, Input2,
15                         isApproximatelyEqual)) {
16    std::cout << "Ranges are approximately equal";
17  }
18}

1Ranges are approximately equal

Permutations

The equals() algorithm returns true if our ranges contain the same values, in the same order. But what if we didn’t care about the order?

If two collections contain the same elements in any order, they’re said to be permutations. The standard library includes an algorithm to test for this - std::ranges::permutation, which is used in the same way as std::ranges::equal:

1#include <algorithm>
2#include <iostream>
3#include <vector>
4
5int main(){
6  std::vector Input1{1, 2, 3};
7  std::vector Input2{3, 1, 2};
8
9  if (!std::ranges::equal(Input1, Input2)) {
10    std::cout << "It's not equal";
11  }
12
13  if (std::ranges::is_permutation(
14    Input1, Input2)) {
15    std::cout << " but it's a permutation";
16  }
17}

1It's not equal but it's a permutation

Permutations do not need to have a different order. Two equal objects are also permutations, so if equal() would return true, so too would is_permutation(). We cover collection comparison algorithms in more detail in the next chapter.

4. The fill() Algorithm

The std::ranges::fill() algorithm is one of the simplest we’ll come across. It accepts a range, as well as an object.

It will then fill the range with copies of that object. Below, we create a std::vector that can hold 5 integers, and then we fill those slots with copies of the number 10:

1#include <algorithm>
2#include <iostream>
3#include <vector>
4
Log Function|Show
5void Log(int Number) {/*...*/};
9
10int main(){
11  std::vector<int> Numbers;
12  Numbers.resize(5);
13  std::ranges::fill(Numbers, 10);
14  std::ranges::for_each(Numbers, Log);
15}

110, 10, 10, 10, 10,

5. The generate() Algorithm

The std::ranges::generate() function populates a range by calling a function for each position in the range. The function’s return value is then placed into that position. The following example populates a range with incrementing integers, starting from 1:

1#include <algorithm>
2#include <iostream>
3#include <array>
4
5struct NumberGenerator {
6  int n{1};
7  int operator()(){ return n++; }
8};
9
10int main(){
11  NumberGenerator Generator;
12  std::array<int, 10> Numbers;
13
14  std::ranges::generate(Numbers, Generator);
15
16  for (int i : Numbers) {
17    std::cout << i << ", ";
18  }
19}

11, 2, 3, 4, 5, 6, 7, 8, 9, 10,

This example created a type that overrides the () operator, allowing us to create objects we can "call", sometimes called function objects or functors. We covered this concept in more detail here:

Function Objects (Functors)

This lesson introduces function objects, or functors. This concept allows us to create objects that can be used as functions, including state management and parameter handling.

In this example, we populate our range with a series of random numbers, from 1 to 10:

1#include <algorithm>
2#include <iostream>
3#include <array>
4#include <random>
5
6struct RandomNumberGenerator {
7  int operator()(){ return Dist(Engine); }
8
9private:
10  static inline std::uniform_int_distribution
11    Dist{1, 10};
12  static inline std::random_device Device;
13  static inline std::mt19937 Engine{Device()};
14};
15
16int main(){
17  RandomNumberGenerator RNG;
18  std::array<int, 10> Numbers;
19
20  std::ranges::generate(Numbers, RNG);
21
22  for (int i : Numbers) {
23    std::cout << i << ", ";
24  }
25}

13, 6, 3, 9, 4, 2, 10, 6, 10, 2,

This example uses the standard library’s random number utilities, which we introduced here:

Random Number Generation

This lesson covers the basics of using randomness, with practical applications

The use of static and inline in the RandomNumberGenerator struct is something we cover later in this course.

6. The iota() Algorithm

The 9th letter of the Greek alphabet, $\iota$, is pronounced "iota" and, in programming contexts, is sometimes used to refer to a sequence of incrementing integers, eg $1, 2, 3, 4, 5$

The C++ standard library has a few variants of this idea. Our earlier example where we used std::ranges::generate to construct a sequence can instead be replaced by std::iota. This takes three arguments:

• An iterator pointing to where we want the range to start
• An iterator pointing to where we want the range to end
• An integer representing what we want the first number to be

This example populates an array with the numbers 1-10

1#include <array>
2#include <iostream>
3#include <numeric>
4
5int main(){
6  std::array<int, 10> Numbers;
7
8  std::iota(Numbers.begin(), Numbers.end(), 1);
9
10  for (int i : Numbers) {
11    std::cout << i << ", ";
12  }
13}

11, 2, 3, 4, 5, 6, 7, 8, 9, 10,

Remember, iota is also available in a view form using std::views::iota, so defining a container for this purpose is often unnecessary:

1#include <iostream>
2#include <ranges>
3#include <vector>
4
5int main(){
6  using std::views::iota, std::views::zip;
7  std::vector Strings{"Mon", "Tue", "Wed"};
8
9  for (const auto& Tuple :
10       zip(iota(1), Strings)) {
11    std::cout << std::get<0>(Tuple) << ": ";
12    std::cout << std::get<1>(Tuple) << '\\n';
13  }
14}

11: Mon
22: Tue
33: Wed

7. The merge() Algorithm

The std::ranges::merge algorithm accepts two sorted inputs and an output location. The output location will be populated by with the sorted combination of our two inputs:

1#include <algorithm>
2#include <iostream>
3#include <vector>
4
Log Function|Show
5void Log(int Number) {/*...*/};
9
10int main(){
11  std::vector Numbers1{1, 3, 5};
12  std::vector Numbers2{2, 4};
13  std::vector<int> Output;
14  Output.resize(
15    Numbers1.size() + Numbers2.size());
16
17  std::ranges::merge(Numbers1, Numbers2,
18                     Output.begin());
19
20  std::ranges::for_each(Output, Log);
21}

11, 2, 3, 4, 5,

If our range is not sorted, the behavior of merge() is undefined, likely resulting in a bug. We can sort collections using the sort() algorithms, introduced in our introductory lesson:

Iterator and Range-Based Algorithms

An introduction to iterator and range-based algorithms, using examples from the standard library

Custom Comparer

The merge() algorithm and most other standard library algorithms that work on sorted data expect our data to be sorted in ascending order, based on the < operator. In other words, if A < B then A is expected to come before B in our collection.

We can change this by passing a custom comparison function. This function will receive two arguments from our ranges and should return true if the first argument comes before the second argument.

Below, we use this to state our objects are sorted in descending order:

1#include <algorithm>
2#include <iostream>
3#include <vector>
4
Log Function|Show
5void Log(int Number) {/*...*/};
9
10int main(){
11  std::vector Numbers1{5, 3, 1};
12  std::vector Numbers2{4, 2};
13  std::vector<int> Output;
14  Output.resize(
15    Numbers1.size() + Numbers2.size());
16
17  auto Descending{
18    [](int a, int b){ return a > b; }};
19
20  std::ranges::merge(Numbers1, Numbers2,
21                     Output.begin(),
22                     Descending);
23
24  std::ranges::for_each(Output, Log);
25}

15, 4, 3, 2, 1,

In this case, our simple lambda could be replaced with the std::greater template class, which simply runs the > operator:

1std::ranges::merge(Numbers1, Numbers2,
2                     Output.begin(),
3                     std::greater{});

In the following example, we use a custom comparer to merge collections of a type that doesn’t even support comparison operators. Instead, we have sorted them based on a class variable:

1#include <algorithm>
2#include <iostream>
3#include <vector>
4
Character Class|Show
5class Character {/*...*/};
12
Log Function|Show
13void Log(const Character& C) {/*...*/};
17
18int main(){
19  using namespace std::string_literals;
20  std::vector<Character> A{
21    "Anna"s, "Bob"s, "Roderick"s};
22  std::vector<Character> B{"Arnold"s, "Bruce"s};
23  std::vector<Character> Output;
24  Output.resize(A.size() + B.size());
25
26  auto AlphabeticalByName{
27    [](const Character& A, const Character& B){
28      return A.Name < B.Name;
29    }};
30
31  std::ranges::merge(A, B, Output.begin(),
32                     AlphabeticalByName);
33
34  std::ranges::for_each(Output, Log);
35}

1Anna, Arnold, Bob, Bruce, Roderick,

std::ranges::is_sorted

We can check if a range is sorted using the std::ranges::is_sorted algorithm:

1#include <algorithm>
2#include <iostream>
3#include <vector>
4
5int main(){
6  std::vector Numbers{1, 2, 3};
7
8  if (std::ranges::is_sorted(Numbers)) {
9    std::cout << "That range is sorted";
10  }
11}

1That range is sorted

This also accepts a comparison function, which lets us specify how we want the sort order to be tested:

1#include <algorithm>
2#include <iostream>
3#include <vector>
4
5int main(){
6  std::vector Numbers{3, 2, 1};
7
8  if (std::ranges::is_sorted(
9    Numbers, std::greater{})) {
10    std::cout <<
11      "That range is sorted in descending order";
12  }
13}

1That range is sorted in descending order

std::ranges::set_union

The output of the merge() algorithm includes duplicates - for example, if both inputs include the number 3, the output will include both copies.

The std::ranges::set_union algorithm only includes a single copy, if that is the behaviour we need:

1#include <algorithm>
2#include <iostream>
3#include <vector>
4
Log Function|Show
5void Log(int Number) {/*...*/};
9
10int main(){
11  std::vector A{1, 3, 5};
12  std::vector B{1, 2, 3, 4};
13
14  // Merge
15  std::vector<int> Merged;
16  Merged.resize(A.size() + B.size());
17  std::ranges::merge(A, B, Merged.begin());
18  std::cout << "Merge Result: ";
19  std::ranges::for_each(Merged, Log);
20
21  // Union
22  std::vector<int> Union;
23  Union.resize(A.size() + B.size());
24  auto [in1, int2, out] =
25    std::ranges::set_union(A, B, Union.begin());
26  Union.erase(out, Union.end());
27  std::cout << "\nUnion Result: ";
28  std::ranges::for_each(Union, Log);
29}

1Merge Result: 1, 1, 2, 3, 3, 4, 5,
2Union Result: 1, 2, 3, 4, 5,

We cover std::ranges::set_union and other set algorithms in detail in the next chapter.

8. The sample() Algorithm

The std::ranges::sample() algorithm copies a random sample of objects from one range into another.

1#include <algorithm>
2#include <iostream>
3#include <vector>
4#include <random>
5
Log Function|Show
6void Log(int Number) {/*...*/};
10
11int main(){
12  std::vector Numbers{1, 2, 3, 4, 5};
13  std::vector<int> Output;
14  Output.resize(3);
15
16  auto RNG{
17    std::mt19937{std::random_device{}()}};
18
19  std::ranges::sample(Numbers, Output.begin(),
20                      Output.size(), RNG);
21
22  std::ranges::for_each(Output, Log);
23}

12, 3, 5,

Sampling is done "without replacement" - that is, once an object has been sampled from our input set, it cannot be chosen again. The effect of this is that each object in our input can only appear in our sampled output once. It also means the maximum size of our sample set is the same as the maximum size of our input.

std::ranges::shuffle

Objects in our sample will appear in the same relative order they were in the input.

If we want to randomize the order, we can shuffle the output. This is available as a separate algorithm.

std::ranges::shuffle accepts two arguments - the range we want to shuffle, and a random number generator to use. Below, we take a sample of our objects, and then shuffle that sample:

1#include <algorithm>
2#include <iostream>
3#include <vector>
4#include <random>
5
Log Function|Show
6void Log(int Number) {/*...*/};
10
11int main(){
12  std::vector Numbers{1, 2, 3, 4, 5};
13  std::vector<int> Output;
14  Output.resize(3);
15
16  auto RNG{
17    std::mt19937{std::random_device{}()}};
18
19  std::ranges::sample(Numbers, Output.begin(),
20                      Output.size(), RNG);
21  std::ranges::shuffle(Output, RNG);
22
23  std::ranges::for_each(Output, Log);
24}

11, 4, 3,

Summary

This lesson has introduced eight key algorithms from the C++ Standard Library, demonstrating their utility in a variety of programming scenarios. Through examples, we've seen how these algorithms can simplify code, improve readability, and enhance performance. We covered:

• std::ranges::for_each for iterating over collections.
• How std::ranges::transform can be used for modifying collections or combining two ranges based on a function.
• The use of std::ranges::equal for comparing two ranges, with the ability to customize comparison logic.
• Utilizing std::ranges::fill to populate a range with a single value.
• Generating sequences or random values in a range using std::ranges::generate.
• Creating numeric sequences with std::iota and its utility in programming.
• Merging two sorted ranges into a single sorted range using std::ranges::merge and customizing the sorting criteria.
• Sampling a subset of elements from a range randomly with std::ranges::sample and shuffling elements with std::ranges::shuffle.

Next Lesson

Parallel Algorithm Execution

Multithreading in C++ standard library algorithms using execution policies

ContinueView Course