11

More Practical Ideas

We've used some useful techniques in this book, like optional values, containers, iterators, algorithms, smart pointers, and more. Let's now apply them to a few more practical ideas. The recipes in this chapter represent concepts that you may find useful, as you work on practical applications in the real world.

In this chapter, we cover the following recipes:

• Create a trie class for search suggestions
• Calculate the error sum of two vectors
• Build your own algorithm: split
• Leverage existing algorithms: gather
• Remove consecutive whitespace
• Convert numbers to words

Create a trie class for search suggestions

A trie , sometimes called a prefix tree , is a type of search tree, commonly used for predictive text and other search applications. A trie is a recursive structure designed for depth-first searches, where each node is both a key and another trie.

A common use case is a trie of strings , where each node is a string in a sentence.

Figure 11.1: A trie of strings

We often start a search at the head of a trie, looking for sentences that begin with a specific word. In this example, when I search for all I get three nodes: you , the , and along . If I search for love I get me and is .

A string trie is commonly used for creating search suggestions. Here we will implement a string trie using std::map for the trie structure.

How to do it

In this recipe we create a recursive trie class that stores nodes in a std::map container. It's a simple solution for a small in-memory trie. This is a rather large class, so we'll only show the important parts here.

For the full source code, please see the source code on github .

• We have one convenience alias:

  using ilcstr = initializer_list<const char *>;

  We use ilcstr in for searching the trie.

• We'll put this class in a private namespace to avoid collisions:

  namespace bw {     using std::map;     using std::deque;     using std::initializer_list;

  We have a few using statements in this namespace for convenience.

• The class itself is called trie. It has three data members:

  class trie {     using get_t = deque<deque<string>>;     using nodes_t = map<string, trie>;     using result_t = optional<const trie*>;      nodes_t nodes {};     mutable get_t result_dq {};     mutable deque<string> prefix_dq {};

  The trie class has a few local type aliases:

  • get_t is a deque of deque of string, used for string results.
  • nodes_t is a map of trie classes with string keys.
  • result_t is an optional of a pointer to a trie, for returning search results. An empty trie is a valid result, so we use an optional value.

  The nodes object is used for holding a recursive map of nodes, where each node on a trie is another trie .

• The public interface often calls utility functions in the private interface. For example, the insert() method takes an initializer_list and calls the private function p_insert() :

  void insert(const ilcstr& il) {     p_insert(il.begin(), il.end()); }

  The private p_insert() function does the work of inserting elements:

  template <typename It> void p_insert(It it, It end_it) {     if (it == end_it) return;     nodes[*it].p_insert(++it, end_it); }

  This facilitates the recursive function calls necessary to navigate the trie of trie classes. Note that referencing a key that does not appear in a map creates an empty element with that key. So, the line that calls _insert() on a nodes element creates an empty trie object if the element doesn't already exist.

• The get() method returns a get_t object, which is an alias for a deque of deque of string . This allows us to return multiple sets of results:

  get_t& get() const {     result_dq.clear();     deque<string> dq {};     p_get(dq, result_dq);     return result_dq; }

  The get() method calls the private p_get() function, which recursively traverses the trie:

  void p_get(deque<string>& dq, get_t& r_dq) const {     if(empty()) {         r_dq.emplace_back(dq);         dq.clear();     }     for(const auto& p : nodes) {         dq.emplace_back(p.first);         p.second.p_get(dq, r_dq);     } }

• The find_prefix() function returns a deque with all matches to a partial string:

  deque<string>& find_prefix(const char * s) const {     p_find_prefix(s, prefix_dq);     return prefix_dq; }

  The public interface calls the private function p _ find_prefix() :

  void p_find_prefix(const string& s, auto& pre_dq) const {     if (empty()) return;     for (const auto& [k, v] : nodes) {         if (k.starts_with(s)) {             pre_dq.emplace_back(k);             v.p_find_prefix(k, pre_dq);         }     } }

  The private p_find_prefix() function traverses the trie recursively, comparing the prefix with beginning of each key. The starts_with() method is new with C++20. With an older STL, you could use the find() method and check the return value for 0:

  If (k.find(s) == 0) {     ...

• The search() function returns an optional<const trie*> , aliased as result_t . It has two overloads:

  result_t search(const ilcstr& il) const {     return p_search(il.begin(), il.end()); }  result_t search(const string& s) const {     const ilcstr il {s.c_str()};     return p_search(il.begin(), il.end()); }

  These methods pass iterators to the private member function p_search() , which does the work of the search:

  template <typename It> result_t p_search(It it, It end_it) const {     if (it == end_it) return {this};     auto found_it = nodes.find(*it);     if (found_it == nodes.end()) return {};     return found_it->second.p_search(++it, end_it); }

  The p_search() function searches recursively until it finds a match, then returns a node in the result_t object. If it finds no match, it returns the non-value optional .

• We also have two overloads of a print_trie_prefix() function. This function prints the contents of a trie from a prefix, used as a search key. One version uses a string for the prefix, the other uses an initializer_list of C-strings:

  void print_trie_prefix(const bw::trie& t,       const string& prefix) {     auto& trie_strings = t.get();     println("results for \"{}...\":", prefix);     for (auto& dq : trie_strings) {         print("{} ", prefix);         for (const auto& s : dq) print("{} ", s);         print("\n");     } }  void print_trie_prefix(const bw::trie& t,         const ilcstr & prefix) {     string sprefix {};     for (const auto& s : prefix) sprefix += format("{} ", s);     print_trie_prefix(t, sprefix); }

  These functions call the get() member function to retrieve the results from the trie.

• Now we can test the trie class in the main() function. First, we declare a trie and insert some sentences:

  int main() {     bw::trie ts {};     ts.insert({ "all", "along", "the", "watchtower" });     ts.insert({ "all", "you", "need", "is", "love" });     ts.insert({ "all", "shook", "up" });     ts.insert({ "all", "the", "best" });     ts.insert({ "all", "the", "gold", "in", "california" });     ts.insert({ "at", "last" });     ts.insert({ "love", "the", "one", "you're", "with" });     ts.insert({ "love", "me", "do" });     ts.insert({ "love", "is", "the", "answer" });     ts.insert({ "loving", "you" });     ts.insert({ "long", "tall", "sally" });     ...

  The insert() calls pass an initializer_list with C-strings representing the words a sentence. Each of the strings are inserted into the hierarchy of the trie .

  Now we can search the trie . Here's a simple search for the single string "love" .

  const auto prefix = {"love"}; if (auto st = ts.search(prefix); st.have_result) {     print_trie_prefix(*st.t, prefix); } print("\n");

  This calls ts.search() with an initializer_list of one C-string, called prefix . The result, along with the prefix is then passed to the print_trie_prefix() function.

  The output is:

  results for "love...": love is the answer love me do love the one you're with

  Here's a search for a two-string prefix:

  const auto prefix = {"all", "the"}; if (auto st = ts.search(prefix); st.have_result) {     print_trie_prefix(*st.t, prefix); } print("\n");

  Output:

  results for "all the ...": all the  best all the  gold in california

  And here's a search for a partial prefix, using the find_prefix() function:

  const char * prefix{ "lo" }; auto prefix_dq = ts.find_prefix(prefix); for(const auto& s : prefix_dq) {     println("match: {}-> {}", prefix, s);     if (auto st = ts.search(s); st.have_result) {         print_trie_prefix(*st.t, s);     } } print("\n");

  Output:

  match: lo -> long results for "long...": long tall sally match: lo -> love results for "love...": love is the answer love me do love the one you're with match: lo -> loving results for "loving...": loving you

  The find_prefix() search returned several results, each of which we passed to a search of its own, resulting in several recursive searches.

How it works

The data for the trie class is stored in recursive map containers. Each node in the map contains another trie object, which in turn has its own map node.

using nodes_t = map<string, trie>

The p_insert() function takes begin and end iterators and uses them to recursively call p_insert() on new nodes:

template <typename It> void p_insert(It it, It end_it) {     if (it == end_it) return;     nodes[*it].p_insert(++it, end_it); }

Likewise, the p_search() function recursively calls p_search() on the nodes it finds:

template <typename It> result_t p_search(It it, It end_it) const {     if (it == end_it) return {this};     auto found_it = nodes.find(*it);     if (found_it == nodes.end()) return {};     return found_it->second.p_search(++it, end_it); }

This recursive approach using std::map allows us to implement a trie class concisely and efficiently.

Calculate the error sum of two vectors

Given two similar vectors that differ only by quantization or resolution, we can use the inner_product() algorithm to calculate an error sum , defined as:

Figure 11.2: Error sum definition

Where e is the error sum: the sum of the squares of the differences between the series of points i to n in the two vectors, a and b .

We can use the inner_product() algorithm, from the <numeric> header, to calculate the error sum between two vector objects.

How to do it

In this recipe we define two vector objects, each with a sine wave. One vector has values of type double and the other has type int . This gives us vectors that differ in quantization , because the int type cannot represent fractional values. We then use inner_product() to calculate the error sum between the two:

• In our main() function we define our vector s and a handy index variable:

  int main() {     constexpr size_t vlen {100};     vector<double> ds(vlen);     vector<int> is(vlen);     size_t index{};     ...

  ds is the vector of double sine waves and is is the vector of int sine waves. Each vector has 100 elements to hold a sine wave. The index variable is used to initialize the vector objects.

• We generate the sine wave in the vector of double , using a loop and a lambda:

  auto sin_gen = [&index]{   return 5.0 * sin(index++ * 2 * pi / 100); }; for (auto& v : ds) v = sin_gen();

  The lambda captures a reference to the index variable so it can be incremented.

  The pi constant is from the std::numbers library.

• We now have a double sine wave, and we can use it to derive the int version:

  index = 0; for (auto& v : is) {     v = static_cast<int>(round(ds.at(index++))); }

  This takes each point from ds , rounds it, casts it to an int , and updates it in position in the is container.

• We display our sine waves with a simple loop:

  for (const auto& v : ds) print("{:-5.2f} ", v); print("\n\n"); for (const auto& v : is) print("{:-3d} ", v); print("\n\n");

  Our output is the sine waves as data points in the two containers:

  0.00  0.31  0.63  0.94  1.24  1.55  1.84  2.13  2.41  2.68  2.94  3.19  3.42  3.64  3.85  4.05  4.22  4.38  4.52  4.65  4.76  4.84  4.91  4.96  4.99  5.00  4.99  4.96  4.91  4.84  4.76  4.65  4.52  4.38  4.22  4.05  3.85  3.64  3.42  3.19  2.94  2.68  2.41  2.13  1.84  1.55  1.24  0.94  0.63  0.31  0.00 -0.31 -0.63 -0.94 -1.24 -1.55 -1.84 -2.13 -2.41 -2.68 -2.94 -3.19 -3.42 -3.64 -3.85 -4.05 -4.22 -4.38 -4.52 -4.65 -4.76 -4.84 -4.91 -4.96 -4.99 -5.00 -4.99 -4.96 -4.91 -4.84 -4.76 -4.65 -4.52 -4.38 -4.22 -4.05 -3.85 -3.64 -3.42 -3.19 -2.94 -2.68 -2.41 -2.13 -1.84 -1.55 -1.24 -0.94 -0.63 -0.31    0   0   1   1   1   2   2   2   2   3   3   3   3   4   4   4   4   4   5   5   5   5   5   5   5   5   5   5   5   5   5   5   5   4   4   4   4   4   3   3   3   3   2   2   2   2   1   1   1   0   0   0  -1  -1  -1  -2  -2  -2  -2  -3  -3  -3  -3  -4  -4  -4  -4  -4  -5  -5  -5  -5  -5  -5  -5  -5  -5  -5  -5  -5  -5  -5  -5  -4  -4  -4  -4  -4  -3  -3  -3  -3  -2  -2  -2  -2  -1  -1  -1   0

• Now we calculate the error sum using inner_product() :

  double errsum = inner_product(ds.begin(), ds.end(),     is.begin(), 0.0, std::plus<double>(),     [](double a, double b){ return pow(a - b, 2); }); print("error sum: {:.3f}\n\n", errsum);

  The lambda expression returns the ( a _i – b _i ) ² part of the formula. The std::plus() algorithm performs the sum operation.

  Output:

  error sum: 7.304

How it works…

The inner_product() algorithm computes a sum of products on the first input range. Its signature is:

T inner_product(InputIt1 first1, InputIt1 last1,     InputIt2 first2, T init, BinaryOperator1 op1,     BinaryOperator2 op2)

The function takes two binary operator functors, op1 and op2 . op1 is for the sum and op2 is for the product . We use std::plus() as the sum operator and a lambda as the product operator:

double errsum = inner_product(ds.begin(), ds.end(),     is.begin(), 0.0, std::plus<double>(),     [](double a, double b){ return pow(a - b, 2); });

The init parameter can be used as a starting value or bias. We pass it the literal value, 0.0.

The return value is the accumulated sum of the products.

There's more…

We can calculate an accumulated error sum by putting inner_product() in a loop:

println("accumulated error:"); for (auto it {ds.begin()}; it != ds.end(); ++it) {     double accumsum = inner_product(ds.begin(), it,         is.begin(), 0.0, std::plus<double>(),         [](double a, double b){ return pow(a - b, 2); });     print("{:-5.2f} ", accumsum); } print("\n");

Output:

accumulated error:  0.00  0.00  0.10  0.24  0.24  0.30  0.51  0.53  0.55  0.72  0.82  0.82  0.86  1.04  1.16  1.19  1.19  1.24  1.38  1.61  1.73  1.79  1.82  1.82  1.83  1.83  1.83  1.83  1.83  1.84  1.86  1.92  2.04  2.27  2.42  2.46  2.47  2.49  2.61  2.79  2.83  2.83  2.93  3.10  3.12  3.14  3.35  3.41  3.41  3.55  3.65  3.65  3.75  3.89  3.89  3.95  4.16  4.19  4.20  4.37  4.47  4.48  4.51  4.69  4.82  4.84  4.84  4.89  5.03  5.26  5.38  5.44  5.47  5.48  5.48  5.48  5.48  5.48  5.48  5.49  5.51  5.57  5.70  5.92  6.07  6.12  6.12  6.14  6.27  6.45  6.48  6.48  6.59  6.75  6.77  6.80  7.00  7.06  7.07  7.21

This could be useful in some statistical applications.

Build your own algorithm: split

The STL has a rich algorithm library. Yet, on occasion you may find it missing something you need. One common need is a split function.

A split function splits a string on a character separator. For example, here's a Unix /etc/passwd file from a standard Debian installation:

root:x:0:0:root:/root:/bin/bash daemon:x:1:1:daemon:/usr/sbin:/usr/sbin/nologin bin:x:2:2:bin:/bin:/usr/sbin/nologin sys:x:3:3:sys:/dev:/usr/sbin/nologin sync:x:4:65534:sync:/bin:/bin/sync

Each field is separated by a colon : character, where the fields are:

• Login name
• Optional encrypted passwd
• User ID
• Group ID
• Username or comment
• Home directory
• Optional command interpreter

This is a standard file in POSIX-based operating systems, and there are others like it.

Most scripting languages include a built-in function for splitting a string on a separator. There are simple ways to do this in C++. Still, std::string is just another container in the STL, and a generic algorithm that splits a container on a separator could be a useful addition to the toolbox. So, let's build one.

How to do it

In this recipe we'll build a generic algorithm that splits a container on a separator and puts the results in a target container.

• Our algorithm is in the bw namespace, to avoid collisions with std :

  namespace bw {     template<typename It, typename Oc, typename V,         typename Pred>     It split(It it, It end_it, Oc& dest,             const V& sep, Pred& f) {         using SliceContainer = typename Oc::value_type;         while (it != end_it) {             SliceContainer dest_elm{};             auto slice {it};             while (slice != end_it) {                 if (f(*slice, sep)) break;                 dest_elm.push_back(*slice++);             }             dest.push_back(dest_elm);             if (slice == end_it) return end_it;             it = ++slice;         }         return it;     } };

  The split() algorithm searches a container for separators and collects the separated slices into a new output container, where each slice is a container within the output container.

  We want the split() algorithm to be as generic as possible, just like those in the algorithm library. This means that all the parameters are templated, and the code will work with a variety of parameter types.

• First, let's look at the template parameters
  • It is the input iterator type for the source container.
  • Oc is the output container type. This is a container of containers.
  • V is the separator type.
  • Pred is for the predicate functor.

  Our output type is a container of containers. It needs to hold containers of slices. It could be vector<string> , where the string values are slices, or vector<vector<int>> , where the inner vector<int> contains the slices. This means we need to derive the type of the inner container from the Oc container type. We do that with the using declaration in the body of the function.

  using SliceContainer = typename Oc::value_type;

  This is also why we cannot use an output iterator for the output parameter. An output iterator cannot determine the type of its contents and its value_type is set to void .

  We use SliceContainer to define a temporary container that is added to the output container with the statement:

  dest.push_back(dest_elm);

• The predicate is a binary operator that compares an input element with the separator. We include a default equality operator in the bw namespace:

  constexpr auto eq = [](const auto& el, const auto& sep) {     return el == sep; };

• We also include a specialization of split() that uses the eq operator by default:

  template<typename It, typename Oc, typename V> It split(It it, const It end_it, Oc& dest, const V& sep) {     return split(it, end_it, dest, sep, eq); }

• Because splitting string objects is a common use case for this algorithm, we include a helper function for that specific purpose:

  template<typename Cin, typename Cout, typename V> Cout& strsplit(const Cin& str, Cout& dest, const V& sep) {     split(str.begin(), str.end(), dest, sep, eq);     return dest; }

• We test our split algorithm in main() , starting with a string object:

  int main() {     constexpr char strsep {':'};     const string str       {"sync:x:4:65534:sync:/bin:/bin/sync"};     vector<string> dest_vs {};     bw::split(str.begin(), str.end(), dest_vs, strsep,       bw::eq);     for (const auto& e : dest_vs) print("[{}] ", e);     print("\n"); }

  We use a string from the /etc/passwd file to test our algorithm, with this result:

  [sync] [x] [4] [65534] [sync] [/bin] [/bin/sync]

• It's even simpler using our strsplit() helper function:

  vector<string> dest_vs2 {}; bw::strsplit(str, dest_vs2, strsep); for (const auto& e : dest_vs2) print("[{}] ", e); print("\n");

  Output:

  [sync] [x] [4] [65534] [sync] [/bin] [/bin/sync]

  This would make it easy to parse the /etc/passwd file.

• Of course, we can use the same algorithm with any container:

  constexpr int intsep {-1}; vector<int> vi {1, 2, 3, 4, intsep, 5, 6, 7, 8, intsep, 9,   10, 11, 12}; vector<vector<int>> dest_vi {}; bw::split(vi.begin(), vi.end(), dest_vi, intsep); for (const auto& v : dest_vi) {     string s;     for (const auto& e : v) s += format("{}", e);     print("[{}] ", s); } print("\n");

  Output:

  [1234] [5678] [9101112]

  In this example we use a simple vector of int with ‑1 as the separator value.

How it works

The split algorithm itself is relatively simple. The magic in this recipe is in the use of templates to make it as generic as possible.

The derived type in the using declaration allows us to create a container for use with the output container:

using SliceContainer = typename Oc::value_type;

This gives us a SliceContainer type that we can use to create a container for the slices:

SliceContainer dest_elm{};

This is a temporary container that is added to the output container for each slice:

dest.push_back(dest_elm);

There's more…

Because our algorithm uses the push_back() method on the output container, it will not work on a container that doesn't support a push_back() method.

We can use a concept requiring a push_back() -compatible container in our split template:

template<typename Oc> concept PushBackContainer =     requires(Oc c, typename Oc::value_type v) {         c.push_back(v);     };

We apply the concept in our template like this:

    template<typename It, PushBackContainer Oc, typename V,       typename Pred>

Now if we try to use our split algorithm with an incompatible output container, it will fail to compile:

std::forward_list<string> dest_ls2 {}; bw::strsplit(str, dest_ls2, strsep); for (const auto& e : dest_ls2) print("[{}] ", e); print("\n");

When we try to compile this code with GCC, we get a cascade of errors that includes this useful message:

   26 |     It split(It it, const It end_it, Oc& dest, const V& sep, const Pred& f) {       |        ^~~~~ working.cpp:26:8: note: template argument deduction/substitution failed: working.cpp:26:8: note: constraints not satisfied

If we change this to a compatible container, for example, list , it now compiles and runs as expected:

std::list<string> dest_ls2 {};

Output:

[sync] [x] [4] [65534] [sync] [/bin] [/bin/sync]

Leverage existing algorithms: gather

gather() is an example of an algorithm that leverages existing algorithms.

The gather() algorithm takes a pair of container iterators, moves the elements that satisfy a predicate toward a pivot position within the sequence, and returns a pair of iterators that contain the elements that satisfy the predicate.

For example, we could use a gather algorithm to sort all the even numbers to the mid-point of a vector:

vector<int> vint{ 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 }; gather(vint.begin(), vint.end(), mid(vint), is_even); for (const auto& el : vint) print("{}", el);

Our output is:

1302468579

Notice that the even numbers are all in the middle of the output.

In this recipe, we will implement a gather() algorithm using standard STL algorithms.

How to do it

Our gather algorithm uses the std::stable_partition() algorithm to move items before the pivot iterator and again to move items past the pivot.

• We put the algorithm in the bw namespace to avoid naming collisions

  namespace bw {     using std::stable_partition;     using std::pair;     using std::not_fn;      template <typename It, typename Pred>     pair<It, It> gather(It first, It last, It pivot,       Pred pred) {         return {stable_partition(first, pivot,           not_fn(pred)),         stable_partition(pivot, last, pred)};     } ... };

  The gather() algorithm returns a pair of iterators, returned from two calls to stable_partition() .

• We also include some helper lambdas in the bw namespace:

  constexpr auto midit = [](auto& v) {     return v.begin() + (v.end() - v.begin()) / 2; }; constexpr auto is_even = [](auto i) {     return i % 2 == 0; }; constexpr auto is_even_char = [](auto c) {     if (c >= '0' && c <= '9') return (c - '0') % 2 == 0;     else return false; };

  These three lambdas are as follows:

  • midit returns an iterator at the midpoint of a container, for use as a pivot point.
  • is_even returns true if the value is even, for use as a predicate.
  • is_even_char returns Boolean true if the value is a character between '0' and '9' and is even, for use as a predicate.
• We call gather() from the main() function with a vector of int like this:

  int main() {     vector<int> vint {0, 1, 2, 3, 4, 5, 6, 7, 8, 9};     auto gathered_even = bw::gather(vint.begin(),       vint.end(), bw::midit(vint), bw::is_even);     for (const auto& el : vint) print("{}", el);     print("\n"); }

  Our output shows that the even numbers have been gathered in the middle:

  1302468579

• The gather() function returns a pair of iterators that contain just the even values:

  auto& [it1, it2] = gathered_even; for (auto it {it1¯}; it < it2; ++it) print("{}", *it); print("\n");

  Output:

  02468

  We can set the pivot point to the end() iterators:

  bw::gather(vint.begin(), vint.end(), vint.begin(),   bw::is_even); for (const auto& el : vint) print("{}", el); print("\n");  bw::gather(vint.begin(), vint.end(), vint.end(),   bw::is_even); for (const auto& el : vint) print("{}", el); print("\n");

  Output:

  0246813579 1357902468

• Because gather() is iterator-based, we can use it with any container. Here's a string of character digits:

  string jenny {"867-5309"};bw::gather(jenny.begin(), jenny.end(), jenny.end(),   bw::is_even_char); for (const auto& el : jenny) print("{}", el); print("\n");

  This moves all the even digits to the end of the string :

  Output:

  7-539860

How it works

The gather() function uses the std::stable_partition() algorithm to move the elements that match the predicate to the pivot point.

gather() has two calls to stable_partition() , one with the predicate and one with the predicate negated:

template <typename It, typename Pred> pair<It, It> gather(It first, It last, It pivot, Pred pred) {     return { stable_partition(first, pivot, not_fn(pred)),              stable_partition(pivot, last, pred) }; }

The iterators returned from the two stable_partition() calls are returned in the pair .

Remove consecutive whitespace

When receiving input from users, it's common to end up with excessive consecutive whitespace characters in your strings. This recipe presents a function for removing consecutive spaces, even when it includes tabs or other whitespace characters.

How to do it

This function leverages the std::unique() algorithm to remove consecutive whitespace characters from a string.

• In the bw namespace, we start with a function to detect whitespace:

  template<typename T> bool isws(const T& c) {     constexpr const T whitespace[] {" \t\r\n\v\f"};     for (const T& wsc : whitespace) {         if (c == wsc) return true;     }     return false; }

  This templated isws() function should work with any character type.

• The delws() function uses std::unique() to erase consecutive whitespace in a string:

  string delws(const string& s) {     string outstr {s};     auto its = unique(outstr.begin(), outstr.end(),         [](const auto &a, const auto &b) {             return isws(a)&&isws(b);         });     outstr.erase(its, outstr.end());     outstr.shrink_to_fit();     return outstr; }

  delws() makes a copy of the input string , removes consecutive whitespace, and returns the new string .

• We call it with a string from main() :

  int main() {     const string s {"big     bad    \t   wolf"};     const string s2 {bw::delws(s)};     println("[{}]", s);     println("[{}]", s2);     return 0; }

  Output:

  [big     bad           wolf] [big bad wolf]

How it works

This function uses the std::unique() algorithm with a comparison lambda to find consecutive whitespace in a string object.

The comparison lambda calls our own isws() function to determine if we have found consecutive whitespace:

auto its = unique(outstr.begin(), outstr.end(),     [](const auto &a, const auto &b) {         return isws(a)&&isws(b);     });

We could use the isspace() function from the standard library, but it's a standard C function that depends on a narrowing type conversion from int to char . This may issue warnings on some modern C++ compilers and is not guaranteed to work without an explicit cast. Our isws() function uses a templated type and should work on any system and with any specialization of std::string .

Convert numbers to words

Over the course of my career, I've used a lot of programming languages. When learning a new language, I like to have a project to work on that exposes me to the nuances of the language. The numword class is one of my favorite exercises for this purpose. I have written it in dozens of languages over the years, including several times in C and C++.

numword is a class that spells out a number in words. It can be useful for banking and accounting applications. It looks like this in use:

int main() {     numword nw {};     uint64_t n {};      println("n is {}, {}", nw.getnum(), nw);     nw = 3; println("n is {}, {}", nw.getnum(), nw);     nw = 47; println("n is {}, {}", nw.getnum(), nw);     nw = 73; println("n is {}, {}", nw.getnum(), nw);     nw = 10012; println("n is {}, {}", nw.getnum(), nw);     n = 100073; println("n is {}, {}", n, bw::numword{n});     n = 1000000001; println("n is {}, {}", n, bw::numword{n});     n = 123000000000; println("n is {}, {}", n, bw::numword{n});     n = 1474142398007; println("n is {}, {}", n, nw(n));     n = 999999999999999999; println("n is {}, {}", n, nw(n));     n = 1000000000000000000; println("n is {}, {}", n, nw(n)); }

Output:

n is 3, three n is 47, forty-seven n is 100073, one hundred thousand seventy-three n is 1000000001, one billion one n is 123000000000, one hundred twenty-three billion n is 1474142398007, one trillion four hundred seventy-four billion one hundred forty-two million three hundred ninety-eight thousand seven n is 999999999999999999, nine hundred ninety-nine quadrillion nine hundred ninety-nine trillion nine hundred ninety-nine billion nine hundred ninety-nine million nine hundred ninety-nine thousand nine hundred ninety-nine n is 1000000000000000000, error

How to do it

This recipe originated as an exercise in creating production-ready code. For that reason, it's in three different files:

• numword.h is the header/interface file for the numword class.
• numword.cpp is the implementation file for the numword class.
• numword‑test.cpp is the application file for testing the numword class.

The class itself is about 180 lines of code so we'll just cover the highlights here. You can find the full source code on Github ( ).

In the numword.h file, we put the class in the bw namespace and start with some using statements:

namespace bw {     using std::string;     using std::string_view;     using numnum = uint64_t;     using bufstr = std::unique_ptr<string>;

We use string and string_view objects throughout the code.

uint64_t is our primary integer type because it will hold very large numbers. Because the class is called numword , I alias it as numnum for this purpose.

bufstr is the main output buffer. It's a string wrapped in a unique_ptr , which handles the memory management for automatic RAII compliance.

• We also have a few constants for various purposes:

  constexpr numnum maxnum = 999'999'999'999'999'999; constexpr int zero_i {0}; constexpr int five_i {5}; constexpr numnum zero {0}; constexpr numnum ten {10}; constexpr numnum twenty {20}; constexpr numnum hundred {100}; constexpr numnum thousand {1000};

  The maxnum constant translates to nine hundred ninety-nine quadrillion nine hundred ninety-nine trillion nine hundred ninety-nine billion nine hundred ninety-nine million nine hundred ninety-nine thousand nine hundred ninety-nine , which should be sufficient for most purposes.

  The rest of the numnum constants are used to avoid literals in the code.

  The main data structures are constexpr arrays of string_view objects, representing the words used in the output. The string_view class works great for constants:

  constexpr string_view errnum {"error"}; constexpr string_view _singles[] {     "zero", "one", "two", "three", "four", "five", "six",     "seven", "eight", "nine" }; constexpr string_view _teens[] {     "ten", "eleven", "twelve", "thirteen", "fourteen",     "fifteen", "sixteen", "seventeen", "eighteen",     "nineteen" }; constexpr string_view _tens[] {     errnum, errnum, "twenty", "thirty", "forty", "fifty",     "sixty", "seventy", "eighty", "ninety", }; constexpr string_view _hundred_string = "hundred"; constexpr string_view _powers[] {     errnum, "thousand", "million", "billion", "trillion",     "quadrillion" };

  The words are grouped into sections, useful in translating numbers to words. Many languages use a similar breakdown so this structure should translate easily to those languages.

• The numword class has a few private members:

  class numword {     bufstr _buf {std::make_unique<string>(string{})};     numnum _num {};     bool _hyphen_flag {false};

  • _buf is the output string buffer. Its memory is managed by a unique_ptr .
  • _num holds the current numeric value.
  • _hyphen_flag is used during the translation process to insert a hyphen between words, rather than a space character.
• These private methods are used to manipulate the output buffer:

  void clearbuf(); size_t bufsize(); void appendbuf(conststring&s); void appendbuf(const string_view&s); void appendbuf(const char c); void appendspace();

• There is also a pow_i() private method used to calculate xy with numnum types:

  numnum pow_i(const numnum n, const numnum p);

  pow_i() is used to discriminate parts of the numeric value for word output.

• The public interface includes constructors and various ways to call the words() method, which does the work of translating a numnum to a string of words:

  numword(const numnum& num = 0) : _num(num) {} numword(const numword& nw) : _num(nw.getnum()) {} const char * version() const { return _version; } void setnum(const numnum& num) { _num = num; } numnum getnum() const { return _num; } numnum operator=(const numnum#); conststring&words(); const string& words(const numnum#); const string& operator() (const numnum& num) {     return words(num); };

• In the implementation file, numword.cpp , the bulk of the work is handled in the words() member function:

  const string& numword::words( const numnum& num ) {     numnum n {num};     clearbuf();     if (n > maxnum) {         appendbuf(errnum);         return *_buf;     }     if (n == 0) {         appendbuf(_singles[n]);         return *_buf;     }     // powers of 1000     if (n >= thousand) {         for(int i{ five_i }; i > zero_i; --i) {             numnum power{ pow_i(thousand, i) };             numnum _n {( n - ( n % power ) ) / power};             if (_n) {                 int index = i;                 numword _nw {_n};                 appendbuf(_nw.words());                 appendbuf(_powers[index]);                 n -= _n * power;             }         }     }     // hundreds     if (n >= hundred && n < thousand) {         numnum _n {( n - ( n % hundred ) ) / hundred};         numword _nw {_n};         appendbuf(_nw.words());         appendbuf(_hundred_string);         n -= _n * hundred;     }     // tens     if (n >= twenty && n < hundred) {         numnum _n {( n - ( n % ten ) ) / ten};         appendbuf(_tens[_n]);         n -= _n * ten;         _hyphen_flag = true;     }     // teens     if (n >= ten && n < twenty) {         appendbuf(_teens[n - ten]);         n = zero;     }     // singles     if (n > zero && n < ten) {         appendbuf(_singles[n]);     }     return *_buf; }

  Each part of the function peels off part of the number with a modulus of a power of ten , recursively in the case of the thousands, and appending strings from the string_view constant arrays.

• There are three overloads of appendbuf() . One appends a string:

  void numword::appendbuf(const string& s) {     appendspace();     _buf->append(s); }

  Another appends a string_view :

  void numword::appendbuf(const string_view& s) {     appendspace();     _buf->append(s.data()); }

  And the third appends a single character:

  void numword::appendbuf(const char c) {     _buf->append(1, c); }

• The appendspace() method appends a space character or a hyphen, depending on context:

  void numword::appendspace() {     if(bufsize()) {         appendbuf(_hyphen_flag ? _hyphen : _space);         _hyphen_flag = false;     } }

• The numword‑test.cpp file is the testing environment for bw::numword . It includes a formatter specialization:

  template<> struct std::formatter<bw::numword>: std::formatter<std::string> {     template<typename FormatContext>     auto format(const bw::numword& nw, FormatContext& ctx)       const {         bw::numword _nw{nw};         return std::formatter<std::string,           char>::format(_nw.words(), ctx);     } };

  This allows us to pass a bw::numword object directly to println() .

• In main() , we declare a bw::numword object and a bw::numnum for use in testing:

  int main() {     bw::numword nw {};     bw:numnum n {};      bw::print("n is {}, {}\n", nw.getnum(), nw);     ...

  The numword object is initialized to zero, giving us this output from our println() statement:

  n is 0, zero

  We test a variety of ways to call numword :

  nw = 3; println("n is {}, {}", nw.getnum(), nw); nw = 47; println("n is {}, {}", nw.getnum(), nw); ... n = 100073; println("n is {}, {}", n, bw::numword{n}); n = 1000000001; println("n is {}, {}", n, bw::numword{n}); ... n = 474142398123; println("n is {}, {}", n, nw(n)); n = 1474142398007; println("n is {}, {}", n, nw(n)); ... n = 999999999999999999; println("n is {}, {}", n, nw(n)); n = 1000000000000000000; println("n is {}, {}", n, nw(n));

  Output:

  n is 3, three n is 47, forty-seven ... n is 100073, one hundred thousand seventy-three n is 1000000001, one billion one ... n is 474142398123, four hundred seventy-four billion one hundred forty-two million three hundred ninety-eight thousand one hundred twenty-three n is 1474142398007, one trillion four hundred seventy-four billion one hundred forty-two million three hundred ninety-eight thousand seven ... n is 999999999999999999, nine hundred ninety-nine quadrillion nine hundred ninety-nine trillion nine hundred ninety-nine billion nine hundred ninety-nine million nine hundred ninety-nine thousand nine hundred ninety-nine n is 1000000000000000000, error

How it works

This class is significantly driven by the data structures. By organizing string_view objects into arrays, we can easily translate scalar values into corresponding words:

appendbuf(_tens[_n]);  // e.g., _tens[5] = "fifty"

The rest of it is mostly the math:

numnum power {pow_i(thousand, i)}; numnum _n {( n - ( n % power ) ) / power}; if (_n) {     int index = i;     numword _nw {_n};     appendbuf(_nw.words());     appendbuf(_powers[index]);     n -= _n * power; }

There's more…

I also have a utility that uses the numword class to tell time in words. Its output looks like this:

$ ./saytime three past five

In test mode, it gives this output:

$ ./saytime test 00:00 midnight 00:01 one past midnight 11:00 eleven o'clock 12:00 noon 13:00 one o'clock 12:29 twenty-nine past noon 12:30 half past noon 12:31 twenty-nine til one 12:15 quarter past noon 12:30 half past noon 12:45 quarter til one 11:59 one til noon 23:15 quarter past eleven 23:59 one til midnight 12:59 one til one 13:59 one til two 01:60 OOR 24:00 OOR

I leave its implementation as an exercise for the reader.

Subscribe to Deep Engineering

Join thousands of developers and architects who want to understand how software is changing, deepen their expertise, and build systems that last.

Deep Engineering is a weekly expert-led newsletter for experienced practitioners, featuring original analysis, technical interviews, and curated insights on architecture, system design, and modern programming practice.

Scan the QR or visit the link to subscribe for free.