6

STL Algorithms

Much of the power of the STL is in the standardization of container interfaces. If a container has a particular capability, there's a good chance that the interface for that capability is standardized across container types. This standardization makes it possible for a library of algorithms to operate seamlessly across containers and sequences sharing a common interface.

For example, if we want to sum all the elements in a vector of int , we could use a loop:

vector<int> x {1, 2, 3, 4, 5}; long sum {}; for (int i : x) sum += i;

Or we could use an algorithm:

vector<int> x {1, 2, 3, 4, 5}; auto sum = accumulate(x.begin(), x.end(), 0);

This same syntax works with other containers:

deque<int> x {1, 2, 3, 4, 5}; auto sum = accumulate(x.begin(), x.end(), 0);

The algorithm version is easier to read and easier to maintain, and an algorithm is often more efficient than the equivalent loop.

Beginning with C++20, the ranges library provides a set of alternative algorithms that operate with ranges and views . This book will demonstrate those alternatives where appropriate.

Most of the algorithms are in the algorithm header. Some numeric algorithms, notably accumulate() , are in the numeric header, and some memory-related algorithms are in the memory header.

In this chapter, we will cover STL algorithms in the following recipes:

• Copy from one iterator to another
• Join container elements into a string
• Sort containers with std::sort
• Modify containers with std::transform
• Search containers with std::find
• Limit container values with std::clamp
• Sample data sets with std::sample
• Use ranges for more powerful algorithms
• Generate permutations of data sequences
• Merge sorted containers

Copy from one iterator to another

The copy algorithms are generally used to copy from and to containers, but in fact, they work with iterators, which is far more flexible.

How to do it

In this recipe, we will experiment with std::copy and std::copy_n to get a good understanding of how they work:

• Let's start with a function to print a container:

  void printc(auto& c, string_view s = "") {     if (s.size()) print("{}: ", s);     for (auto e : c) print("[{}] ", e);     print("\n"); }

• In main() , we define a vector and print it with printc() :

  int main() {     vector<string> v1 {"alpha", "bravo", "charlie",         "delta", "echo"};     printc(v1, "v1"); }

  We get this output:

  v1: [alpha] [bravo] [charlie] [delta] [echo]

• Now, let's create a second vector with enough space to make a copy of the first vector :

  vector<string> v2(v1.size());

  This creates an empty vector with enough room for all the elements from v1 .

• We copy v1 to v2 using the std::copy() algorithm:

  std::copy(v1.begin(), v1.end(), v2.begin()); printc(v2);

  The std::copy() algorithm takes two iterators for the range of the copy source, and one iterator for the destination. In this case, we give it the begin() and end() iterators of v1 to copy the entire vector . The begin() iterator of v2 serves as the destination for the copy.

  Our output is now:

  v1: [alpha] [bravo] [charlie] [delta] [echo] v2: [alpha] [bravo] [charlie] [delta] [echo]

• The copy() algorithm does not allocate space for the destination. So, v2 must already have the space for the copy. Alternatively, you can use the back_inserter() iterator adapter to insert the elements at the back of the vector :

  vector<string> v2 {}; std::copy(v1.begin(), v1.end(), back_inserter(v2));

• We can also use the ranges::copy() algorithm to copy an entire range . A container object serves as a range so we can use v1 as the source. We still use an iterator for the destination:

  vector<string> v2 {}; ranges::copy(v1, v2.begin());

  This also works with back_inserter() :

  vector<string> v2 {}; ranges::copy(v1, back_inserter(v2));

• You can copy a certain number of elements using copy_n() :

  vector<string> v3 {}; std::copy_n(v1.begin(), 3, back_inserter(v3)); printc(v3, "v3");

  In the second argument, the copy_n() algorithm is a count for the number of elements to copy. The output is:

  v3: [alpha] [bravo] [charlie]

• There's also a copy_if() algorithm that uses a Boolean predicate function to determine which elements to copy:

  vector<string> v4 {}; std::copy_if(v1.begin(), v1.end(), back_inserter(v4),     [](string& s){ return s.size() > 4; }); printc(v4, "v4");

  There's also a ranges version of copy_if() :

  vector<string> v4 {}; ranges::copy_if(v1, back_inserter(v4),     [](string& s){ return s.size() > 4; }); printc(v4, "v4");

  The output includes only strings longer than 4 characters:

  v4: [alpha] [bravo] [charlie] [delta]

  Notice that the value echo , which is not longer than 4 characters, is excluded.

• You can use any of these algorithms to copy to or from any sequence, including a stream iterator:

  ostream_iterator<string> out_it(cout, " "); ranges::copy(v1, out_it) print("\n");

  Output:

  alpha bravo charlie delta echo

How it works

The std::copy() algorithm is very simple. An equivalent function would look like this:

template<typename I_it, typename O_it> O_it copy(I_it begin_it, I_it end_it, O_it dest_it) {     while (begin_it != end_it) {         *dest_it++ = *begin_it++;     }     return dest_it; }

The copy() function uses the destination iterator's assignment operator to copy from the input iterator to the output iterator until it reaches the end of the input range.

There is also a version of this algorithm called std::move() , which moves elements instead of copying them:

std::move(v1.begin(), v1.end(), v2.begin()); printc(v1, "after move: v1"); printc(v2, "after move: v2");

This performs a move instead of copy assignment. After the move operation, the elements in v1 will be empty, and the elements that were in v1 are now in v2 . The output looks like this:

after move1: v1: [] [] [] [] [] after move1: v2: [alpha] [beta] [gamma] [delta] [epsilon]

There is also a ranges version of the move() algorithm that performs the same operation:

ranges::move(v1, v2.begin());

The power of these algorithms lies in their simplicity. By letting the iterators manage the data, these simple, elegant functions allow you to seamlessly copy or move between any of the STL containers that support the required iterators.

Join container elements into a string

Sometimes, there is no algorithm in the library to accomplish a task at hand. We can use iterators, with the same techniques as the algorithms library, to easily write one.

For example, we often need to join elements from a container, with separators, into a string. One common solution is to use a simple for() loop:

for(auto v : c) print(", ");

The problem with this otherwise simple solution is that it leaves a trailing separator:

vector<string> lads {"paul", "john", "george",     "ringo", "billy"}; for (const auto v : lads) print("{}, ", v); print("\n");

Output:

paul, john, george, ringo, billy,

This may be fine in a testing environment, but in any production system, that trailing comma is unacceptable.

The ranges::views library has a join() function, but it doesn't do what we want:

auto lads_view = lads | views::join;

This returns a ranges::view object, which requires a separate step to display or create a string. We can cycle through the view with a for() loop:

for (const auto v : lads_view) print("{}:", v); print("\n");

The output looks like this:

p:a:u:l:j:o:h:n:g:e:o:r:g:e:r:i:n:g:o:b:i:l:l:y:

This is a completely flattened view, with each element of each string separated into its own view element. It may be useful in some contexts, but it's not what we're looking for, and it doesn't solve our problem at all.

Since the algorithms library does not have a function that suits our needs, we'll write one.

How to do it

For this recipe, we will take the elements of a container and join them into a string with separators.

• In our main() function, we declare a vector of strings:

  vector<string> lads{ "john", "paul", "george",   "ringo", "billy" };

• Now, we can write a simple join() function that uses a string object to join elements with a separator:

  namespace bw {     template<typename I>     string join(I it, I end_it, string_view sep = "") {         string ostr {};         if (it != end_it) ostr = format("{}", *it++);         while (it != end_it) {             ostr = format("{}{}{}", ostr, sep, *it++);         }         return ostr;     }      string join(const auto& c, string_view sep = "") {         return join(c.begin(), c.end(), sep);     } }

  I've put this in my own bw namespace to avoid name collisions.

  Notice there's two specializations of the join() function. One takes iterators, and one takes a container. The container version calls the iterator version with the iterators from the container.

  We use the format() function to format the elements of the container. This allows us to use the format library's specializations for various common types, or to create our own specializations to represent our data as strings.

  We call it with println() like this:

  println("{}", bw::join(lads, ", "));

  Output:

  john, paul, george, ringo, billy

How it works

Most of the work in this recipe is done by the iterators:

template<typename I> string join(I it, I end_it, const string_view sep = "") {     string ostr {};     if (it != end_it) ostr = format("{}", *it++);     while (it != end_it) {         ostr = format("{}{}{}", ostr, sep, *it++);     }     return ostr; }

Separators are inserted after the first element, between each of the successive elements, and end before the final element. This means we can either add a separator before each element, skipping the first, or after each element, skipping the last. The logic is simpler if we process the first element separately. We do that in the line just before the while loop:

if (it != end_it) ostr = format("{}", *it++);

Once we have the first element out of the way, we can simply add a separator before each remaining element:

while (it != end_it) {     ostr = format("{}{}{}", ostr, sep, *it++); }

Because we return a string object, it's easy to call this in various contexts:

println("{}", bw::join(lads, ", "));

Output:

john, paul, george, ringo, billy

There's more…

As with any of the library algorithms, this join() function will work with any container that supports forward iterators . For example, here's a list of double constants from the numbers library:

namespace num = std::numbers; list<double> constants {num::pi, num::e, num::sqrt2}; println("{}", bw::join(constants, ", "));

Output:

3.141592653589793, 2.718281828459045, 1.4142135623730951

It will even work with a ranges::view object:

auto lads_view = views::join(lads); println("{}", bw::join(lads_view, ":"));

Output:

j:o:h:n:p:a:u:l:g:e:o:r:g:e:r:i:n:g:o:b:i:l:l:y

This gives us the completely flattened views::join result, joined with separators by our join() function.

Sort containers with std::sort

The problem of how to efficiently sort comparable elements is essentially solved. For most applications, there's no reason to re-invent this wheel. The STL provides an excellent sorting solution via the std::sort() algorithm. While the standard does not specify a sorting algorithm, it does specify a worst-case complexity of O ( n log n ), when applied to a range of n elements.

Just a few decades ago, the quicksort algorithm was considered a good compromise for most uses and was generally faster than other comparable algorithms. Today we have hybrid algorithms that choose between different approaches according to the circumstances, often switching algorithms on the fly. Most current C++ libraries use a hybrid approach with some combination of introsort and insertion sort . std::sort() provides excellent performance under most common circumstances, such as partially ordered data, random data, and larger general-purpose data sets.

How to do it

In this recipe, we'll examine the std::sort() algorithm. The sort() algorithm works with any container with random-access iterators. For simplicity, we will use a vector of int in this recipe:

• We'll start with a function to test if a container is sorted:

  void check_sorted(const auto &c) {     if (!is_sorted(c.begin(), c.end())) print("un");     print("sorted: "); }

  This becomes even simpler with ranges::is_sorted() :

  void check_sorted(const auto &c) {     if (!ranges::is_sorted(c)) print("un");     print("sorted: "); }

  Using the is_sorted() algorithm this prints either "sorted:" or "unsorted:" , according to the result.

• We need a function to print our vector :

  void printc(const auto &c) {     check_sorted(c);     for (auto& e : c) print("{} ", e);     print("\n"); }

  This function calls check_sorted() to display the status of the container before the values.

• Now we can define and print a vector of int in the main() function:

  int main() {     vector<int> v {1, 2, 3, 4, 5, 6, 7, 8, 9, 10};     printc(v);     ... }

  The output looks like this:

  sorted: 1 2 3 4 5 6 7 8 9 10

• In order to test the std::sort() algorithm, we need an unsorted vector . Here's a simple function to randomize our container:

  void randomize(auto& c) {     static std::random_device rd;     static std::default_random_engine rng(rd());     std::shuffle(c.begin(), c.end(), rng); }

  The std::random_device class uses your system's hardware entropy source. Most modern systems have one, otherwise the library will simulate it. This can be a useful tool for testing purposes.

  The std::default_random_engine() function generates random numbers from the entropy source. This is the default engine used by std::shuffle() to randomize the container.

  We can now call randomize() with our container and print the result:

  randomize(v); printc(v);

  Output:

  unsorted: 6 3 4 8 10 1 2 5 9 7

  Of course, your output will be different because it's randomized. In fact, I get a different result every time I run it:

  for(int i {3}; i; --i) {     randomize(v);     printc(v); }

  Output:

  unsorted: 3 1 8 5 10 2 7 9 6 4 unsorted: 7 6 5 1 3 9 10 2 4 8 unsorted: 4 2 3 10 1 9 5 6 8 7

• To sort the vector , we simply call std::sort() :

  std::sort(v.begin(), v.end()); printc(v);

  Or we can use the simpler ranges::sort() :

  std::ranges::sort(v);

  printc(v);Output:

  sorted: 1 2 3 4 5 6 7 8 9 10

  By default, the sort() algorithm uses the < operator to sort the elements in the range specified by the supplied iterators.

• The partial_sort() algorithm will sort part of the container:

  randomize(v); auto middle {v.begin() + (v.size() / 2)}; std::partial_sort(v.begin(), middle, v.end()); printc(v);

  partial_sort() takes three iterators: beginning, middle, and end. It sorts the container such that the elements before the middle are sorted. The elements after the middle are not guaranteed to be in the original order. Here's the output:

  unsorted: 1 2 3 4 5 10 7 6 8 9

  Notice that the first five elements are sorted, and the rest are not.

• The partition() algorithm does not sort anything. It rearranges the container so that certain elements appear at the front of the container:

  randomize(v); printc(v); std::partition(v.begin(), v.end(),     [](int i) { return i > 5; }); printc(v);

  The third argument is a predicate lambda that determines which elements will be moved to the front.

  Output:

  unsorted: 4 6 8 1 9 5 2 7 3 10 unsorted: 10 6 8 7 9 5 2 1 3 4

  Notice that the values greater than 5 are moved to the front of the container.

• The sort() algorithms support an optional comparison function that may be used for non-standard comparisons. For example, given a class called things , with a string called s and an int called i :

  struct things {     string s;     int i;     string str() const {         return format("({}, {})", s, i);     } };

  We can create a vector of things objects:

  vector<things> vthings { {"button", 40}, {"hamburger", 20},     {"blog", 1000}, {"page", 100}, {"science", 60} };

  We'll need a function to print them out:

  void print_things(const auto& c) {     for (auto& v : c) print("{} ", v.str());     print("\n"); }

• Now we can sort and print the vector of things , using std::ranges::sort() :

  std::ranges::sort(vthings,         [](const things &lhs, const things &rhs) {     return lhs.i < rhs.i; }); print_things(vthings);

  Output:

  (hamburger, 20) (button, 40) (science, 60) (page, 100) (blog, 1000)

  Notice the comparison function sorts on the int member, so the result is sorted by i . We could instead sort on the string member:

  std::ranges::sort(vthings,         [](const things &lhs, const things &rhs) {     return lhs.s < rhs.s; }); print_things(vthings);

  Now it's sorted by s and we get this output:

  (blog, 1000) (button, 40) (hamburger, 20) (page, 100) (science, 60)

How it works

The sort() functions work by applying a sorting algorithm to a range of elements indicated by two iterators, for the beginning and end of the range.

By default, these algorithms use the < operator to compare elements. Optionally, they may use a comparison function , often provided as a lambda:

std::sort(vthings.begin(), vthings.end(),         [](const things& lhs, const things& rhs) {     return lhs.i_ < rhs.i_; });

There is also a ranges version which takes a container as a single argument instead of separate iterators:

std::ranges::sort(vthings,         [](const things &lhs, const things &rhs) {     return lhs.i < rhs.i; });

The comparison function takes two arguments and returns a bool . It has a signature equivalent to this:

bool cmp(const Type1& a, constType2&b);

The sort() functions use std::swap() to move elements. This is efficient in both compute cycles and memory usage, as it relieves the need to allocate space for reading and writing the objects being sorted. This is also why the partial_sort() and partition() functions cannot guarantee the order of unsorted elements.

Modify containers with std::transform

The std::transform() algorithm is remarkably powerful and flexible. One of the more commonly deployed algorithms in the library, it applies a function or lambda to each element in a container, storing the results in another container while leaving the original in place.

Given its power, it's deceptively simple to use.

How to do it

In this recipe, we will explore a few applications for the std::transform() function:

• We'll start with a simple function that prints the contents of a container:

  void printc(const auto& c, string_view s = "") {     if (s.size()) print("{}: ", s);     for (const auto& e : c) print("{} ", e);     print("\n"); }

  We'll use this function to view the results of our transformations.

• In the main() function, we declare a couple of vector s:

  int main() {     vector<int> v1 {1, 2, 3, 4, 5, 6, 7, 8, 9, 10};     vector<int> v2 {};     printc(v1, "v1");     ...   }

  The vectorv1 contains ten elements, int values 1 through 10 . The vectorv2 is empty.

  This prints out the contents of v1 :

  v1: 1 2 3 4 5 6 7 8 9 10

• We can use the transform() function to insert the square of each value into v2 :

  println("squares:"); transform(v1.begin(), v1.end(), back_inserter(v2),     [](int x) { return x * x; }); printc(v2, "v2");

  The transform() function takes four arguments. The first two are the begin() and end() iterators for the source range. The third argument is the begin() iterator for the destination range. Because the vectorv2 is empty, we use the back_inserter() algorithm to insert the results in v2 . The fourth argument is the function to apply to the transformation. In this case, we're using a lambda to square the value.

  Output:

  squares: v2: 1 4 9 16 25 36 49 64 81 100

• Of course, we can use transform() with any type. Here's an example that converts a vector of string objects to lowercase. First, we need a function to return the lowercase value of a string:

  string str_lower(string s) {     auto char_lower = [](char c) -> char {         if(c >= 'A'&&c<= 'Z') return c + ('a' - 'A');         else return c;     };     for (auto&c:s)c=char_lower(c);     return s; }

• This uses a lambda for the actual character conversion, rather than the tolower() function from the legacy C Standard Library which requires type casting to work with char -typed values in C++.
• Now we can use the str_lower() function with transform:

  vector<string> vstr1 {"Mercury", "Venus", "Earth", "Mars",     "Jupiter", "Saturn", "Uranus", "Neptune", "Pluto"}; vector<string> vstr2 {}; printc(vstr1, "vstr1"); println("str_lower:"); transform(vstr1.begin(), vstr1.end(), back_inserter(vstr2),     [](string& x) { return str_lower(x); }); printc(vstr2, "vstr2");

  This calls str_lower() for each element in vstr1 and inserts the resulting lowercase string into vstr2 . The result is:

  vstr: Mercury Venus Earth Mars Jupiter Saturn Uranus Neptune Pluto str_lower: vstr: mercury venus earth mars jupiter saturn uranus neptune pluto

  (Yes, Pluto will always be a planet to me.)

• There's also a ranges version of transform :

  println("ranges squares:"); auto view1 = views::transform(v1,     [](int x) { return x * x; }); printc(view1, "view1");

  The ranges version has a more succinct syntax and returns a view object, rather than populating another container.

How it works

The std::transform() function works very much like std::copy() , with the addition of the user-provided function. Each element in the input range is passed to the function, and the return value from the function is copy-assigned to the destination iterator. This makes transform() a singularly useful and powerful algorithm.

It's worth noting that transform() does not guarantee the elements will be processed in order. In other words, while the output order is preserved, the functor (or lambda) may be called out of order. If you need to ensure the order of the transformation, you will want to use a for loop instead:

v2.clear();    // reset vector v2 to empty state for(auto e : v1) v2.push_back(e * e); printc(v2, "v2");

Output:

v2: 1 4 9 16 25 36 49 64 81 100

Search containers with std::find

The algorithm library contains a set of functions for finding elements in a container. The std::find() function, and its derivatives, search sequentially through a container and return an iterator pointing to the first matching element, or the end() iterator if there's no match.

How to do it

The find() algorithm works with any container that satisfies the Forward or Input iterator qualifications. For this recipe, we'll use vector containers. The find() algorithm searches sequentially for the first matching element in a container. In this recipe, we'll walk through a few examples:

• Let's start by declaring a vector of int in the main() function:

  int main() {     const vector<int> v {1, 2, 3, 4, 5, 6, 7, 8, 9, 10};     ... }

• We can now search for the element with the value 7 :

  auto it1 = find(v.begin(), v.end(), 7); if (it1 != v.end()) println("found: {}", *it1); else println("not found");

  The find() algorithm takes three arguments: begin() and end() iterators, and the value to search. It returns an iterator to the first element it finds, or the end() iterator if the search failed to find a match.

  Output:

  found: 7

• We can also search for something more complex than a scalar. The object needs to support the equality comparison operator == . Here's a simple struct with an operator==() overload:

  struct City {     string name {};     unsigned pop {};     bool operator==(const City& o) const {         return name == o.name;     }     string str() const {         return format("[{}, {}]", name, pop);     } };

  The struct is named City and it has two members, name and pop , for the name and population of the city.

  The operator=() overload only compares the name members. This allows us to search with only a name .

  I've also included an str() function that returns a string representation of a City element.

• Now we can declare a vector of City elements:

  const vector<City> c{     { "London", 9425622 },     { "Berlin", 3566791 },     { "Tokyo",  37435191 },     { "Cairo",  20485965 } };

• We can search the vector of City just as we did with the vector of int :

  auto it2 = find(c.begin(), c.end(), City({"Berlin", {}})); if (it2 != c.end()) println("found: {}", it2->str()); else println("not found");

  Output:

  found: [Berlin, 3566791]

  Notice that we passed a City object, with only a name parameter, to the find() function. If we want to compare against a string literal (a const C-string), we could add another operator==() overload:

  bool operator==(const char* cstr) const {     return name == cstr; }

  Now we can perform our search with a string literal:

  auto it3 = find(c.begin(), c.end(), "Berlin"); if (it3 != c.end()) println("found: {}", it3->str()); else println("not found");

  Output:

  found: [Berlin, 3566791]

• If we want to search on the pop member instead of name , we can use the find_if() function with a predicate:

  auto it4 = find_if(begin(c), end(c),     [](const City& item) { return item.pop > 20'000'000; }); if (it4 != c.end()) println("found: {}", it4->str()); else println("not found");

  Note the use of apostrophe ' separators in the literal numeric values. This is a C++14 feature which makes large numbers easy to read. In modern C++, 20'000'000 is treated the same as 20000000 .

  The predicate tests the pop member for elements with a pop value greater than 20,000,000, so we get this output:

  found: [Tokyo, 37435191]

• Notice that the result from find_if() returns only the first element that satisfies the predicate, even though there are two elements in the vector with pop values greater than 20,000,000.

  The find() and find_if() functions return only one iterator. The ranges library provides ranges::views::filter() , a view adapter that will give us all the matching iterators without disturbing our vector :

  auto vw1 = views::filter(c,     [](const City& c){ return c.pop > 20'000'000; }); for (const City& e : vw1) println("{}", e.str());

  This gives us both matching elements in our output:

  [Tokyo, 37435191] [Cairo, 20485965]

How it works

The find() and find_if() functions search sequentially through a container, checking each element until they find a match. If they find a match, they return an iterator pointing to that match. If they reach the end() iterator without finding a match, they return the end() iterator to indicate no match was found.

The find() function takes three arguments: begin() and end() iterators, and a search value. The signature looks like this:

template<class InputIt, class T> constexpr InputIt find(InputIt, InputIt, const T&)

The find_if() function uses a predicate instead of a value:

template<class InputIt, class UnaryPredicate> constexpr InputIt find_if(InputIt, InputIt, UnaryPredicate)

These functions are simple, and work with any Forward iterator, so they don't require random access. This also means they work with linear O ( n ) complexity. Faster performance would require more complex iterators.

There's more…

Both find() functions search sequentially and return when they find the first match. If you want to find more matching elements, you can use the filter() function from the ranges library:

template<ranges::viewable_range R, class Pred> constexpr ranges::view auto ranges::views::filter(R&&,Pred&&);

The filter() function returns a view , a non-destructive window into the container with only the filtered elements. We can then use the view as we would any other container:

auto vw1 = views::filter(c,     [](const City& c){ return c.pop > 20000000; }); for (const City& e : vw1) println("{}", e.str());

Output:

[Tokyo, 37435191] [Cairo, 20485965]

The new contains() method

Beginning with C++23, some STL containers include a contains() method which returns a simple true or false indicating whether a value exists in the container.

auto needle = "n"; for (auto [city, pop] : c) {     if (name.contains(needle)) {         println("{} found in {}", needle name);     } }

In this example we use the string_view::contains() method to discover which cities have the letter n in their name.

Output:

n found in London n found in Berlin

The string and string_view classes, along with the map and set containers, now include a contains() method.

Limit container values with std::clamp

Introduced with C++17, the std::clamp() function can be used to limit the range of a numeric scalar to within minimum and maximum values. The function is optimized to use move semantics , where possible, for maximum speed, and efficiency.

The clamp() function is in the <algorithm> header.

How to do it

We can use clamp() to constrain the values of a container by using it in a loop or with the transform() algorithm. Let's look at some examples.

• We start with a simple function for printing out the values of a container:

  void printc(auto& c, string_view s = "") {     if (s.size()) print("{}: ", s);     for (auto e : c) print("{:>5} ", e);     print("\n"); }

  Notice the format string "{:>5} " . This right-aligns each value to 5 spaces, for a tabular view.

• In the main() function, we'll define an initializer list for use with our container. This allows us to use the same values more than once:

  int main() {     const auto il = {0, -12, 2001, 4, 5, -14,         100, 200, 30000};     ... }

  That's a nice range of values to work with clamp() .

• Let's also define some constants for use as our limits:

  constexpr int ilow {0}; constexpr int ihigh {500};

  We'll use these values in our calls to clamp() .

• Now we can define a container in our main() function. We'll use a vector of int :

  vector<int> voi {il}; println("vector voi before:"); printc(voi);

  Using the values from our initializer list, the output is:

  vector voi before:     0   -12  2001     4     5   -14   100   200 30000

• Now we can use a for loop with clamp() to limit the values to between 0 and 500 :

  println("vector voi after:"); for (auto&e:voi)e=clamp(e,ilow,ihigh); printc(voi);

  This applies the clamp() function to each value in the container, using 0 and 500 for the low and high limits, respectively. Now, the output is:

  vector voi before:     0   -12  2001     4     5   -14   100   200 30000 vector voi after:     0     0   500     4     5     0   100   200   500

  After the clamp() operation, the negative values are 0 and the values greater than 500 are 500 .

• We can do the same thing with the transform() algorithm, using clamp() in a lambda. This time we'll use a list container:

  list<int> loi {il}; println("list loi before:"); printc(loi); transform(loi.begin(), loi.end(), loi.begin(),     [=](auto e){ return clamp(e, ilow, ihigh); }); println("list loi after:"); printc(loi);

  The output is the same as in the version with a for loop:

  list loi before:     0   -12  2001     4     5   -14   100   200 30000 list loi after:     0     0   500     4     5     0   100   200   500

How it works

The clamp() algorithm is a simple function that looks something like this:

template<class T> constexpr const T& clamp( const T& v, const T& lo,         const T& hi ) {     return less(v, lo) ? lo : less(hi, v) ? hi : v; }

If the value of v is less than lo , it returns lo . If hi is less than v , it returns hi . The function is fast and efficient.

In our examples, we used a for loop to apply clamp() to a container:

For (auto&v:voi)v=clamp(v,ilow,ihigh);

We also used the transform() algorithm with clamp() in a lambda:

transform(loi.begin(), loi.end(), loi.begin(),     [=](auto v){ return clamp(v, ilow, ihigh); });

In my experiments, both versions gave the same results, and both produced similar code from the GCC compiler. There was a slight difference in compiled size (the version with the for loop was smaller, as expected) and a negligible difference in performance.

In general, I prefer the for loop, but the transform() version may be more flexible in some circumstances.

Sample data sets with std::sample

The std::sample() algorithm takes a random sample of a sequence of values and populates a destination container with the sample. It is useful when analyzing a larger set of data, where the random sample is taken to be representative of the whole.

A sample set allows us to approximate the characteristics of a large set of data, without analyzing the full set. This provides efficiency in exchange for accuracy, a fair trade-off in many circumstances.

How to do it

In this recipe, we use an array of 200,000 random integers with a standard normal distribution . We'll sample a few hundred values to create a histogram of the frequency of each value.

• We'll start with a simple function to return a rounded int from a double . The standard library lacks such a function and we'll need it later:

  int iround(const double& d) {     return static_cast<int>(std::round(d)); }

  The standard library provides several versions of std::round() , including one that returns a long int . But we need an int , and this is a simple solution that avoids compiler warnings about narrowing conversion while hiding away the unsightly static_cast .

• In the main() function, we start with some useful constants:

  int main() {     constexpr size_t n_data {200000};     constexpr size_t n_samples {500};     constexpr int mean {};     constexpr size_t dev {3};     ... }

  We have values for n_data and n_samples , used for the size of the data and sample containers, respectively. We also have values for mean and dev , the mean and standard deviation parameters for the distribution of random values.

• We now set up our random number generator and distribution objects. These are used to initialize the source data set:

  std::random_device rd {}; std::mt19937 rng(rd()); std::normal_distribution<> dist(mean, dev);

  The random_device object provides access to the hardware random number generator. The mt19937 class is an implementation of the Mersenne Twister random number algorithm, a high-quality algorithm that will perform well on most systems with a data set of the size we're using. The normal_distribution class provides a distribution of random numbers around the mean with the standard deviation provided.

• Now we populate an array with an n_data number of random int values:

  array<int, n_data> data {}; for (auto&e:data)e=iround(dist(rng));

  The array container is fixed in size, so the template parameters include a size_t value for the number of elements to allocate. We use a for loop to populate the array.

  The rng object is the hardware random number generator. This is passed to dist() , our normal_distribution object, and then to iround() , our integer rounding function.

• At this point, we have an array with 200,000 data points. That's a lot to analyze, so we use the sample() algorithm to take a sample of 500 values:

  array<int, n_samples> samples {}; sample(data.begin(), data.end(), samples.begin(),     n_samples, rng);

  We define another array object to hold the samples. This one is n_samples in size. Then we use the sample() algorithm to populate the array with n_samples random data points.

• We create a histogram to analyze the samples. A map structure is perfect for this so we can easily map the frequency of each value:

  std::map<int, size_t> hist {}; for (const int i : samples) ++hist[i];

  The for loop takes each value from the samples container and uses it as a key in the map . The increment expression ++hist[i] counts the number of occurrences of each value in the sample set.

• We print out the histogram using a format string in the println() function:

  constexpr size_t scale {3}; println("{:>3} {:>5} {:<}/{}", "n", "count",     "graph", scale); for (const auto& [value, count] : hist) {     println("{:>3} ({:>3}) {}", value, count,         string(count / scale, '*')); }

  The format specifiers make space for a certain number of characters. The angle bracket specifies right alignment.

  The string(count, char) constructor creates a string object with a character repeated the number of times specified, in this case, n asterisk characters * , where n is count / scale , the frequency of a value in the histogram, divided by the scale constant.

  The output looks like this:

  $ ./sample   n count graph/3 -9 (  2) -7 (  5) * -6 (  9) *** -5 ( 22) ******* -4 ( 24) ******** -3 ( 46) *************** -2 ( 54) ****************** -1 ( 59) *******************   0 ( 73) ************************   1 ( 66) **********************   2 ( 44) **************   3 ( 34) ***********   4 ( 26) ********   5 ( 18) ******   6 (  9) ***   7 (  5) *   8 (  3) *   9 (  1)

  This is a nice graphical representation of the histogram. The first number is the value, the second number is the frequency of the value, and the asterisks are a visual representation of the frequency, where each asterisk represents scale ( 3 ) occurrences in the sample set.

  Your output will differ each time you run the code.

How it works

The std::sample() function selects a specific number of elements from random locations in the source container and copies them to the destination container.

The signature of sample() looks like this:

OutIter sample(SourceIter, SourceIter, OutIter, SampleSize,RandNumGen&&);

The first two arguments are begin() and end() iterators on a container with the full data set. The third argument is an iterator for the destination of the samples. The fourth argument is the sample size, and the final argument is a random number generator function.

The sample() algorithm uses uniform distribution , so each data point has the same chance of being sampled.

Use ranges for more powerful algorithms

Ranges are an abstraction that allow algorithms to work with any sequence of elements. A range is essentially the normalization of begin() and end() iterators as the boundaries of an operational sequence in the STL. Many classes in the ranges library also return view objects. A view is a non-owning adapter that provides sequential access to underlying data.

The ranges library was introduced with C++20 and expanded in C++23. It provides alternative, more efficient, and convenient versions of most of the functions in the algorithms library.

In this recipe we will consider a few representative examples of algorithms in the ranges library.

How to do it

The ranges library includes alternative versions of a number of functions from the algorithms library. Let's consider some examples.

• First, we'll need a few common elements for these examples. We'll use these namespace aliases for ranges and views :

  namespace ranges = std::ranges; namespace views = ranges::views;

  We'll need a function to print a range:

  void p_range(auto r) {     for (const auto& v : r) print("{} ", v);     print("\n"); }

  This uses an abbreviated function template to deduce the type of the range.

  Because the range may be a non-owning view , we cannot use the const qualifier or a reference for the range r parameter, but we can for the value v in the for loop.

• We'll also define a couple of lambdas for use with the algorithms:

  auto even = [](auto i) { return 0 == i % 2; }; auto square = [](auto i) { return i * i; };

  even is a predicate that filters even-numbered values and square returns the square of a numeric value.

  In the main() function, we'll use a simple range of integers for these examples:

  const auto r = views::iota(0, 10);

• The views::iota() function returns a view object representing a range of integers. This view is lazy, with its members generated as they are needed.

  We can print the range r using our p_range() function:

  p_range(r);

  We get this output:

  0 1 2 3 4 5 6 7 8 9

  The views::iota(0, 10) function call returns a bounded range of 10 integers beginning with 0 . The first argument is the start of the series and the second argument is the number of elements.

• We can populate a container from the range using ranges::copy() :

  vector<int> v1 (r.size()); ranges::copy(r, v1.begin()); p_range(v1);

  We initialize the vector with the size of the range object to create a vector with room for the range. The ranges::copy algorithm takes two arguments, the range and an iterator. We use the begin() iterator from our vector as the target of the copy operation. We then print the vector with p_range() for this output:

  0 1 2 3 4 5 6 7 8 9

• Or we can use back_inserter() instead of initializing the vector with the size of the range:

  ranges::copy(r, std::back_inserter(v2));

  This gives us the same result:

  0 1 2 3 4 5 6 7 8 9

• The ranges library provides a new piping syntax, using the | operator ( bitwise or ) to chain together range adapters, similar to how Unix command pipes work on the command line:

  vector<int> v3 = r   | views::transform([](auto i) { return i * 2; })   | ranges::to<vector<int>>(); p_range(v3);

  This creates a new vector , v3 , and populates it with the output of r , piped into the transform algorithm with a lambda that multiplies by 2 , piped into the ranges::to algorithm to populate the vector . The output is:

  0 2 4 6 8 10 12 14 16 18

  The piping syntax is nicely readable and produces efficient code due to the lazy evaluation of ranges and views.

• We can scramble vectorv1 using the ranges::shuffle algorithm. First, we need a random number generator, which we can create using this function:

  auto rng() {     std::random_device rd {};     return std::mt19937(rd()); }

  Now we can use ranges::shuffle to scramble v1 :

  ranges::shuffle(v1, rng()); p_range(v1);

  My output looks like this:

  6 2 7 0 3 8 1 5 9 4

  Your output will be different. In fact, each time you run it you should get a different randomization. Let's try running it 5 times:

  for (int i {}; i < 5; ++i) {     ranges::shuffle(v1, rng());     p_range(v1); }

  Output:

  9 4 2 0 8 6 7 3 5 1 7 3 1 9 4 5 6 0 2 8 1 7 2 8 9 0 3 5 6 4 9 1 0 5 7 4 3 8 6 2 5 4 7 1 2 0 8 6 3 9

  Of course, your result will differ each time you run it.

• Now we can sort v1 with ranges::sort() :

  ranges::sort(v1); p_range(v1);

  After the sort , v1 looks like this:

  0 1 2 3 4 5 6 7 8 9

• We've seen the views::iota() function used with two arguments, where the second argument is the length of the series.

  If we call views::iota() without a second argument, iota() will generate an indefinite, or unbounded , series. We can use views::take() to take a specific number of values from an unbounded view:

  p_range(views::iota(0) | views::take(10));

  With just one argument, iota() generates an unbounded view. The take(10) call returns the first 10 elements from the iota() view. Here, we pass the pipeline directly to our p_range() function and we get the first 10 elements of the view:

  0 1 2 3 4 5 6 7 8 9

• Most of the functions in the algorithm library now have ranges analogs. Here's an example that pipes together filter , transform , and reverse :

  p_range(r | views::filter(even) | views::transform(square) | views::reverse);

  This gives us the following result:

  64 36 16 4 0

How it works

A range is an abstraction that represents a sequence of elements with begin() and end() iterators. The purpose is to make it easier for algorithms to operate on any iterable sequence, including containers, views, or any iterable object.

The std::ranges library provides a set of tools and algorithms that operate on ranges directly, rather than requiring separate iterators. For example, the std::sort() algorithm requires iterators. Its signature looks like this:

template< class It > void sort( It first, It last );

It is typically called with the begin() and end() iterators of a container:

vector<int> v {3, 9, 7, 4, 6, 5, 2, 1, 0, 8}; std::sort(v.begin(), v.end()); for (const auto& i : v) print("{} ", i); print("\n");

The arguments to the std::sort() algorithm are iterators which specify the range to be sorted.

The std::ranges::sort() version of the same algorithm looks like this:

template< ranges::random_access_range R > sort(R&&r);

This means that we can simply pass the container directly to std::ranges::sort() instead of its iterators:

vector<int> v {3, 9, 7, 4, 6, 5, 2, 1, 0, 8}; std::ranges::sort(v); for (const auto& i : v) print("{} ", i); print("\n");

The output of both of these examples is the same:

0 1 2 3 4 5 6 7 8 9

For many circumstances, this syntax is simpler and more concise.

A view is a further abstraction that exposes iterators for a non-owning sequence of values. From the caller's perspective, it looks very much like a range, but its values are owned by an underlying object. View adapters can be chained using the piping syntax, which leverages the bitwise or operator | in much the same way that streams leverage the bitwise left-shift operator << . This allows us to chain views together like this:

for (const auto& i : views::iota(0, 10) |   views::filter(even) |   views::transform(square) |   views::reverse) {     print("{} ", i); } print("\n");

Output:

64 36 16 4 0

As these new ranges and views versions of the algorithm library become more widely implemented, they will allow us to write more expressive and intuitive code.

Generate permutations of data sequences

There are many use cases for permutations, including testing, statistics, research, and more. The next_permutation() algorithm generates permutations by re-ordering a container to the next lexicographical permutation.

How to do it

For this recipe, we'll print out the permutations of a set of three strings:

• We start by creating a short function for printing the contents of a container:

  void printc(const auto& c, string_view s = "") {     if (s.size()) print("{}: ", s);     for (const auto& e : c) print("{} ", e);     print("\n"); }

  We'll use this simple function to print our data set and permutations.

• In the main() function, we declare a vector of string objects and sort it with the sort() algorithm.

  int main() {     vector<string> vs {"dog", "cat", "velociraptor"};     sort(vs.begin(), vs.end());     ... }

  The next_permutation() function requires a sorted container.

• Now we can list the permutations with next_permutation() in a do loop:

  do {     printc(vs); } while (next_permutation(vs.begin(), vs.end()));

  The next_permutation() function modifies the container and returns true if there is another permutation, or false if not.

  The output lists six permutations of our three pets:

  cat dog velociraptor cat velociraptor dog dog cat velociraptor dog velociraptor cat velociraptor cat dog velociraptor dog cat

How it works

The std::next_permutation() algorithm generates lexicographical permutations of a set of values, that is, permutations based on dictionary ordering. The input must be sorted because the algorithm steps through permutations in lexicographical order. So, if you start with a set like 3, 2, 1, it will terminate immediately as this is the last lexicographical order of those three elements.

For example:

vector<string> vs {"velociraptor", "dog", "cat"}; do {     printc(vs); } while (next_permutation(vs.begin(), vs.end()));

This gives us the following output:

velociraptor dog cat

While the term lexicographical implies alphabetical ordering, the implementation uses standard comparison operators, so it works on any sortable values.

Likewise, if values in the set repeat, they are only counted according to lexicographical order. Here we have a vector of int with two repeating sequences of five values:

vector<int> vi {1, 2, 3, 4, 5, 1, 2, 3, 4, 5}; sort(vi.begin(), vi.end()); printc(vi, "vi sorted"); long count {}; do {     ++count; } while (next_permutation(vi.begin(), vi.end())); print("number of permutations: {}\n", count);

Output:

vi sorted: 1 1 2 2 3 3 4 4 5 5 number of permutations: 113400

There are 113,400 permutations of these values. Notice that it's not 10! (3,628,800) because some values repeat. Since 3,3 and 3,3 sort the same, they are not different lexicographical permutations.

In other words, if I list the permutations of this short set:

vector<int> vi2 {1, 3, 1}; sort(vi2.begin(), vi2.end()); do {     printc(vi2); } while (next_permutation(vi2.begin(), vi2.end()));

We get only three permutations, not 3! (6), because of the repeating values:

1 1 3 1 3 1 3 1 1

Merge sorted containers

The std::merge() algorithm takes two sorted sequences and creates a third merged and sorted sequence. This technique is often used as part of a merge sort , allowing very large amounts of data to be broken down into chunks, sorted separately, and merged into one sorted target.

How to do it

For this recipe, we'll take two sorted vector containers and merge them into a third vector using std::merge() .

• We start with a simple function to print the contents of a container:

  void printc(const auto& c, string_view s = "") {     if (s.size()) print("{}: ", s);     for (const auto& e : c) print("{} ", e);     print("\n"); }

  We'll use this to print the source and destination sequences.

• In the main() function, we'll declare our source vectors, along with the destination vector, and print them out:

  int main() {     vector<string> vs1 {"dog", "cat", "velociraptor"};     vector<string> vs2 {"kirk", "sulu", "spock"};     vector<string> dest {};     printc(vs1, "vs1");     printc(vs2, "vs2");     ... }

  The output is:

  vs1: dog cat velociraptor vs2: kirk sulu spock

• Now we can sort our vectors and print them again:

  sort(vs1.begin(), vs1.end()); sort(vs2.begin(), vs2.end()); printc(vs1, "vs1 sorted"); printc(vs2, "vs2 sorted");

  Output:

  vs1 sorted: cat dog velociraptor vs2 sorted: kirk spock sulu

  Now that our source containers are sorted, we can merge them for our final merged result:

  merge(vs1.begin(), vs1.end(), vs2.begin(), vs2.end(),     back_inserter(dest)); printc(dest, "dest");

  Output:

  dest: cat dog kirk spock sulu velociraptor

  This output represents the merge of the two sources into one sorted vector.

How it works

The merge() algorithm takes begin() and end() iterators from both sources and an output iterator for the destination:

OutputIt merge(InputIt1, InputIt1, InputIt2, InputIt2, OutputIt)

It takes the two input ranges, performs its merge/sort operation, and sends the resulting sequence to the output iterator.

Get this book's PDF version and more

Scan the QR code (or go to ). Search for this book by name, confirm the edition, and then follow the steps on the page.

Note: Keep your invoice handy. Purchases made directly from Packt don't require an invoice.