In this chapter, we discuss the theory and methodology of computational thinking. As such, this chapter doesn’t include much code. However, some of the later sections do have some samples of C++ code, and, as with the rest of this book, some familiarity with C++ is expected. Since the latter sections describe good practice for working with code, the Chapter-01 folder in the GitHub repository for this book (https://github.com/PacktPublishing/The-CPP-Programmers-Mindset) includes these samples of code along with unit tests. These tests do not contribute to the content of the chapter.

Solving problems is an iterative process. There are many things to consider at each step. As some challenges are overcome, others will emerge. Computational thinking provides the framework for deciding what step to take next. As with all iterative processes, there will be steps that don’t work out because the solutions you arrive at are unsatisfactory or simply don’t work, but this is all part of the process.

Before we continue, we need to discuss what we mean by a “problem.” For the purposes of this book, a problem is a specific task with well-defined constraints and parameters. The actual nature of the task can be relatively simple or highly complex, as long as it is specific. The constraints can also be broad in nature: they can be managerial (time constraints, deadlines), technical (performance), or domain-specific (physical limitations). The parameters describe the data and other information that is provided in order to solve the task.

The four components of computational thinking are as follows:

• Decomposition
• Abstraction
• Pattern recognition
• Algorithm design

Each step in the problem-solving process will involve one or more of these components, but they are not, in themselves, the steps that one must follow. For instance, some steps will fall into a class of well-known problems with “off-the-shelf” solutions that can be implemented with ease. Other steps will be complex and require decomposition into many smaller problems. Moreover, these components cannot be considered in isolation. One cannot decompose a problem without understanding the essential constituents of the problem or recognizing standard patterns among the noise of contextual information that may or may not be relevant. You must consider all the components at once.

It is sometimes easy to miss the bigger picture when you are solving small and nuanced problems – especially how your solution will interface with the larger system. This could be the larger piece of software in which your solution will live, or the way clients interact with your software. These issues are also part of the problem that you would need to solve, using the components of computational thinking to guide you.

As you gain experience, the number of patterns and standard problems that you recognize will grow, and the speed at which you arrive at useful abstractions will increase. In the beginning, these aspects will be the most troublesome. In the remainder of this book, we will look at common techniques and some standard problems that will allow you to get started with problem-solving. Unfortunately, we cannot simply give you a complete catalogue of patterns and abstractions: if all problems were already solved, there would be no need for a framework for solving problems.

Solving problems is not only an iterative process, but also a dynamic process. Some choices will have implications for the rest of the process and possibly even for previous steps. For example, selecting a programming language, such as C++, will have a dramatic effect on the way you go about designing algorithms, selecting abstractions, the standard patterns available, and the way you further decompose problems. For example, if one solves a problem in Python, one might try to lean on the numerous high-performance libraries, which may or may not provide the exact functionality required. However, in C++, you have more freedom to implement your own high-performance primitive operations.

There will be times when you have to undo several steps of the process, especially while you’re still building experience. The important thing here is to understand that this is a necessary step in the learning process. You must endeavor to understand why that particular line of investigation failed and how to incorporate this knowledge into the next iteration. Don’t be afraid to go back to the beginning (time allowing) and start again. Sometimes this is the only way to make progress.

In the remainder of this chapter, we look in more detail at the four components of computational thinking. For now, we will only discuss the components in general. We will revisit these components in far more detail in later chapters, when we look at real examples and how to apply these concepts using C++.

General advice

Solving problems can be hard, especially when you’re fairly new to a particular domain, language, tool, or working environment. Here is some general advice on how to make this easier and more enjoyable.

• Keep a journal of patterns, abstractions, and other information that you can refer back to when new problems appear. As you get more experience, you will internalize many of these, but there will always be some that you forget about that you might need to call on in the future.
• Seek out small problems to hone your skills. Websites such as LeetCode (https://leetcode.com/) have huge libraries of small problems that are designed to teach specific patterns and techniques. This can help, especially at the beginning when you don’t have your own catalogue to draw upon. The greater the variety of problems that you see, the more you have to draw upon when you’re looking for patterns and abstractions when solving entirely new problems; the problems don’t need to be identical, just similar enough to provide inspiration.
• Talk to colleagues and friends about problems, where this is appropriate. Sometimes the act of explaining a problem can help make it clearer for you and will sometimes help you to solve the problem directly. If you can find a more senior or experienced colleague who is willing to help, then they can share their own expertise with you, which can sometimes help you arrive at solutions more quickly. If no colleagues or friends are available, even talking the problem through with your rubber duck can help – and they are always willing to listen.

A far too mathematical example

Before we go into detail about the components of computational thinking, we should first look at an example where many of these ideas manifest. The example we will use is solving a specific differential equation from elementary calculus. Don’t be put off by the presence of equations in this section. The actual mathematics used here is not the important part; the way that we work through the problem is. Nevertheless, this example is a good choice precisely because of this added complexity; you will sometimes have to operate outside your comfort zone.

A differential equation is an equation that involves one or more derivatives of a function that evolves according to some other variable . Differential equations are used in many fields to describe how a system evolves depending on various factors. For instance, Newton’s theory of mechanics is described using differential equations (he invented calculus in order to describe the world through these equations). The equation we consider here is far simpler; it involves the first and second derivatives of , denoted and , whose coefficients are simple constants. The equation is

with some initial conditions . The objective here is to find an expression for the function , written in terms of , that when “plugged in” to this equation on the left-hand side, gives the right-hand side. To solve this problem, one has to break it down into smaller parts; it cannot be solved directly as a whole (at least not easily).

The first level of decomposition involves solving two separate problems: first, we find a solution to the simpler equation where the right-hand side is zero; the second is to find an expression that “displaces” the solution to the first sub-problem to obtain the correct right-hand side. This is akin to fitting a straight line to a set of data; first, you find the gradient and then move the line up and down until it fits properly. (In fact, mathematically speaking, it is exactly this.)

Let’s focus on the first sub-problem, finding the “general solution.” Here, we’re asked to find a solution to the simpler equation

This seems tricky until one realizes that an equation of this kind has solutions that look like . The derivatives of this are and , so plugging those into the equation gives

There are two ways the far-right expression can be zero. The first is that the function is constantly zero (which cannot be true, since ), or if the quadratic equation holds. We have reduced solving a part of the differential equation to finding the roots of a simple quadratic polynomial – a common pattern often taught in high-school mathematics.

The so-called auxiliary equation can be factorized into , meaning the two roots (the values of for which the quadratic equals ) are or . The general solution to our simple differential equation is thus given by a linear combination of and , something like

To find the values of the two constants and , we need to use the two initial conditions. The condition is straightforward to apply, because we just substitute for and in the equation to get

For the second equation, we need to differentiate, but this is also not too hard:

This is a common pattern in mathematics called a system of simultaneous equations (again, often taught in high-school level mathematics). We can solve this by subtracting the former equation from the latter to get , leaving . (Don’t worry too much if you haven’t seen this before; it isn’t important.) This means our general solution is now .

Now we have a solution that behaves correctly, in shape, but it doesn’t solve our original equation. For that, we need to find an “offset” that translates our general solution into the true solution. To do this, we look at the right-hand side of the original equation . It’s quite reasonable to presume that the factor by which we need to translate our general solution has a similar form to this expression, perhaps something like , where , , and are constants that we need to find.

We need to plug our proposed translation into the differential equation, so we need to differentiate it. The first derivative is and the second derivative is just . (Again, don’t worry if you’re not following this working; it isn’t important.) Thus, we need to solve the new equation

This is yet another common pattern in mathematics called “comparing coefficients” of the left and right. (Two quadratic expressions are equal if and only if each pair of corresponding coefficients is equal.) Let’s rearrange the left-hand side to make this more clear:

From this, we see that we need each of the equations , , and (no constant term appears on the right-hand side) to hold. Again, we find ourselves back at solving simultaneous equations. To avoid repeating the process, the solution is , , and . Putting everything back together now gives the solution

Now for the important bit, reflecting on what we have done. In solving this single mathematics problem, we have actually decomposed it into a number of smaller problems, which required far less knowledge of mathematics. We divided the initial problem into two: the simpler problem (general solution) and then the translation problem (specific solution).

• Within the general solution branch, we recognized the form of the equation (pattern recognition). Finding the roots of the auxiliary equation is another sub-problem – one that is completely isolated from the main problem – and then solving the system of equations to obtain the general solution is yet another. This gives us the form of the general solution, which we must then use the two initial conditions to turn into the actual general solution, yet another sub-problem. We differentiate the form of the general solution and apply the initial conditions to obtain a system of equation. We can apply the standard techniques for solving such a system (pattern recognition) to obtain the true general solution.
• Within the particular solution branch of the problem, we recognize that the translation must have a similar form as the right-hand side of the original equation, prompting us to find the derivatives of a general quadratic expression (two sub-problems where the second is dependent on the first). After plugging these derivatives into the equation, we observed that we could compare coefficients (pattern recognition) we obtain another system of equations to solve.

After resolving both branches, we have to put everything back together to obtain the full solution. This is actually a crucial step, and often non-trivial, especially as the division into smaller problems becomes more complex, and where there are interdependencies.

You might be wondering where abstraction and, to a lesser extent, algorithms come into this problem. Mathematical problems are often abstract in nature; they are already an instance of a larger, specific problem in which the crucial components have been extracted. However, this is not to say there is no room for abstraction within this problem. For instance, finding the roots of a quadratic expression and solving systems of linear equations are both well-understood general problems that appear all over the place. We didn’t mention this explicitly, but the techniques we used (factorization and Gaussian elimination) are general techniques for solving the respective abstract problem, applied specifically here.

The question of algorithm design is trickier to discuss here. Obviously, solving this kind of problem is a fairly standard “algorithm” in mathematics. Indeed, it is taught in many mathematics courses at various levels. It might not be presented in the usual way that an algorithm is presented in computer science, but it is a set of simple steps that one can repeat to solve exactly this kind of problem. Gaussian elimination (the process we used to solve both systems of equations) is a well-known algorithm from numerical linear algebra that is used all over the place. Perhaps you could try and think of a few places where systems of equations like these might appear in your field of work?

Now that we have seen an example of solving a multifaceted problem (albeit from a very different context), we can examine the components of computational thinking in more detail and see how these components work together to derive solutions to new problems.

One of the most significant stumbling blocks, particularly when starting out, is breaking down a problem into smaller, more tractable parts. The tendency is to try to tackle the problem as a whole, rather than attempting to decompose it into smaller parts. There are two common reasons for this. The first is that the solver lacks confidence in their skills to correctly decompose. This is common among beginners. The second, which is more common among slightly more experienced solvers, is due to a fear of losing sight of the bigger picture. Obviously, one must keep track of the larger picture; a client would not accept a piece of software that solves one aspect of their problem but not the whole. A balance must be found between finding plausible routes to a solution without losing track of the overall problem.

Ideally, one would break down a problem into a number of isolated sub-problems, but generally this requires many steps of decomposition. Once you have sub-divided the problem several times, this might become the case, but generally, there will be dependencies between these sub-problems. These could be temporal dependencies – one problem must be solved before the other – or technical dependencies – where the solution to one problem depends on or is otherwise informed by the solution to (not the result of) another sub-problem. As the solver, you need to be wary of these constraints. Sometimes, embracing these interdependencies is key to finding a full solution.

Decomposing can also increase the overall complexity of the problem. Each stage of decomposition increases the number of items that must be incorporated back into the overall solution. This is not to say that these stages should be avoided, but it is something to keep in mind. Aim to decompose a problem as minimally as possible to avoid adding complexity and to make sure you don’t get too bogged down in the detail and lose track of the larger problem.

Some problems come with obvious decompositions, but this is not always the case. When this does happen, these easily defined sub-problems are almost always the best way to proceed. As you gain confidence and experience, more problems will start to look like this, and there will be more obvious divisions between parts of even complex problems.

Decomposing a simple thought experiment

Suppose you’re planning a dinner. The problem comes with already well-defined parts: the starter, main course, dessert, and drinks. Each of these is a specific problem to be solved, although they do have some weak linkages. (For example, the choice of main course will impact the choice of wine, which is a kind of technical dependency. Dinner is served after the starter, which is a temporal dependency. Both are weak, since one could technically order any wine with any main, and starters could be brought with mains.) If there are no complicating factors, such as specific dietary requirements, then each of these problems can be solved rather easily. In any case, these three parts will always need to be solved in some way or another in order to successfully deliver dinner to the guests.

To solve this problem, one might start by selecting the main course. Then one can select the starters and dessert courses (separately) to complement the mains. Finally, the drinks can be selected to complement each of the other components. In this way, we reduce the likelihood of having to backtrack because of incompatible course choices; the main course is the most important component, so solve this problem first.

General strategies for decomposing problems

Not all problems can be decomposed easily. Sometimes you must formulate an abstraction for a problem before you start trying to decompose it. Other times, the decomposition comes by recognizing that the problem is similar to some well-known class of problems. Usually, it will be a combination of both, along with a lot of trial and error. Over time, this process becomes easier, but it is never easy.

There are some general strategies for how to go about decomposing a problem, but there are often many “correct” decompositions. There is certainly a trade-off between finding the best decomposition versus finding a decomposition that is sufficient to solve the problem; don’t let perfect be the enemy of good. Ultimately, the most successful strategy is simple trial and error, taking obvious steps where they present themselves and relying on experience and similarity to other problems otherwise. Sometimes, you need to refine (or create) your abstractions before a pathway to decomposition appears.

A good way to start to collect parts of a problem together into coherent sub-problems is to ask reasonable questions about the problem or parts thereof: what is going to be the most difficult part of this problem; what information do I need for that part; do I need to apply any preprocessing to change the information before I can use it; do I need to apply any postprocessing to results before I return them to the user?

Most coding problems have at least three components. The first is acquiring the data from the user and converting it into a form that can be used. The second is doing the actual work required by the problem. The final step is performing any postprocessing and returning the results to the user. Sometimes this involves abstraction mechanisms made available through the programming language (e.g., classes).

Computing the average annual temperature differences

Let us assume that you have a database of regional temperature readings from around the world at regular intervals over many years. The problem in such a case is to compute the average year-on-year change in temperature in each region for each year. A very simple approach is to simply compute the average temperature of each region over each year, compute the difference from the previous year, and then collect these differences together. However, this does not quite capture the nuance of the problem.

The most difficult aspect of this problem is accounting for seasonal variation that occurs within the yearly cycle. Merely computing the differences between yearly averages would not account for this. A much better approach is to compute the difference between corresponding values within consecutive years and then average these differences over the whole year. However, even this isn’t perfect because it doesn’t account for short-term variability in temperature. A far better approach, provided we have enough data, is to compute an indicative temperature for a given period within the year. We can compute the average temperature within a short sliding window around the time in question to “smooth out” the volatility in local weather. These smoothed values should be broadly comparable year to year.

Another problem that might appear here, and in many similar problems, is whether all the measurements were taken with the same units: in many places, Celsius is the preferred unit of measurement for temperature, but in some places, Fahrenheit is the preferred unit. Many errors have been caused throughout history by failing to account for units of measurement, sometimes with catastrophic consequences. Ideally, all measurements should be converted to Kelvin (the SI unit for temperature on an absolute scale) before any computations are done.

To formulate a decomposition, we first look at the three high-level components. The first is loading and preprocessing data, which involves applying the conversion to Kelvin and placing the standardized data in a place where we can find it later (either on disk or in RAM, for instance). The second is doing the actual work of computing average differences. This will involve many sub-problems outlined above. The final high-level component is postprocessing the results to return to the user. For this problem, there is little, if any, postprocessing to be done, but sometimes this will be a significant step.

Computing the average regional differences is the main challenge. We have several sub-problems to solve here. A flow chart depicting the order of operations involved here is shown in Figure 1.1.

• For each source of data, we need to compute the averages over sliding windows of time over the whole year. None of these computations relies on any of the other computations, so they are a strong candidate for parallelization.
• We need to compute the annual differences between corresponding window averages. This can also be done in parallel.
• Finally, we need to average the window differences over each region for each pair of consecutive years.

Figure 1.1: Flow chart showing the order of sub-components of a regional weather comparison problem, including where the data has dependencies on previous steps and where solutions can be done in parallel

Now we have a reasonable understanding of the challenges that we will face in order to completely solve this problem. We have not yet made any attempt to actually solve these sub-problems. We don’t need to decompose further; each of the sub-problems already seems feasible without further decomposition. However, the option remains open to us should we need it.

Concrete problems are often messy. They have many components and are generally provided with more information than one needs to actually solve the problem. This extraneous data is often distracting and gets in the way of solving the problem. To get around this, one needs to extract only the essential information, discarding the irrelevant excess, and identify only the general concepts of data and processes. This process is called abstraction.

An abstraction is a generalized view of a concept or data that keeps only the essential information and properties of the concept. A well-designed abstraction allows one to devise simple and elegant solutions to problems that are otherwise complex and opaque. They take time to build, but the payoff can be dramatic. A good abstraction will apply to a large class of problems and will become a useful tool for the future. They can help you realize your problem as a more general class of problem, or invent a new general class of solution that can be used elsewhere.

Abstraction is not just a tool for reducing problems to something simpler but more general. As a programmer, you use abstractions all the time, such as functions, classes, system memory, and file systems. Abstractions are very important in programming because they allow you to build reusable code that functions in many scenarios, rather than being specific to each problem. The C/C++ runtime libraries provide functions for allocating and freeing memory that can be used for many different things in many different circumstances.

There are several places where abstraction really matters. The first, and probably most immediately useful, is for the initial ingestion and preprocessing of data. When writing software, you will need to decide how your program will obtain the data it needs to solve a problem. Will it be a Unix command-line tool that reads directly from the terminal (stdin) or a file on the disk? Will it be a GUI application where the user types the data in directly? Will it be part of a library that exposes an interface that other developers can use? Each of these appears different, but with a well-designed abstraction, you could be flexible enough to answer any of these design objectives.

Another reason to abstract your input data is to make sure it conforms to your requirements. As described above, units of measurement are not standardized around the world, and assuming that all measurements use the same units is dangerous. Using an abstraction on the interface of your application would allow you to work with the data, placed in the correct units, regardless of the input type (assuming that the unit information was provided). We will come back to this idea later too.

Abstractions are also useful when designing algorithms, as we shall see later. For instance, if your data belongs to, or can be easily embedded in, a mathematical structure such as a vector space, then the operations and methodology of that structure can be used to devise an algorithm. This is advantageous for several reasons. Mathematical structures are well studied – perhaps too much so – so these can be used to make strong guarantees about the algorithm. Second, mathematical operations, particularly those concerning vector spaces, are well studied, and there are many optimized implementations of them.

Identifying commonalities in data

Data is an obvious place to look to build abstractions. As described previously, forming abstractions around the source and nature of the data provided can ease the acquisition, validation, and processing of data. However, before we can do this, we need to filter out the information that is not relevant to the problem. Of course, this is a classic “chicken and egg” problem since one sometimes cannot tell what information is relevant before actually solving the problem.

Finding these generalizations starts with asking some basic questions about your data. Is the data numerical in nature? If so, what kind of numbers? Numerical data is likely to fit into some kind of mathematical structure. It has natural orderings, which may or may not be relevant to your problem, and more specifically, there will be “equals comparable” to one another (the operation == is defined for numerical values). It also has arithmetic (+, -, *, /), which has well-defined interactions with the ordering and equality comparisons. Each of these is an abstract property that numbers happen to possess. Any given problem might require that your data be ordered and comparable (such as searching and sorting), or that it has some or all arithmetic operations, but not actually rely on the actual form of the underlying data.

Text data is a great example of an abstract class of data. Text is a sequence of characters taken from a particular “alphabet,” such as the ASCII code table or the UTF-8 code table. The actual nature of these characters might well be important. For instance, ASCII characters are represented by a single byte, whereas UTF-8 has multi-byte characters as well as single-byte characters. It is not necessarily important to know what alphabet is used for a particular set of text data, but it is important that you know how to identify individual characters, compare them, or otherwise operate upon them.

Broadly speaking, many problems can be generalized by considering what traits parts of the data must satisfy (having ordered, equality comparable, iterable, etc.). Sometimes it is easy to identify which traits are required up front (searching generally requires iterable and comparable), but other times this isn’t possible. Sometimes you need to solve the problem with concrete data to realize that it can be generalized. Sometimes it cannot be generalized at all.

Identifying structure in the problem

Sometimes it’s not just the data that can be abstracted. Sometimes the problem itself has a general structure that can be identified and exploited. A typical example of this might be to identify one part of a problem as an instance of a theoretical framework. For instance, if one step of a problem is to find particular patterns within data, which for text is usually accomplished with regular expressions (this is pattern recognition). The abstraction comes by understanding that the computational theory of regular expressions is deterministic finite automata (DFA), which are the abstraction that we seek. These kinds of abstractions can be difficult to spot but generally lead to high-quality results.

Finding abstractions such as this can give you a theoretical framework in which the solution to the main problem can be found. Finite automata (and finite state machines) are a very powerful pattern that can be used in a great many situations. Once you know that part of the problem involves such a construction, you can start to look for other parts of the problem that also fit this model. This might not be successful, but it does at least give options for where to look and how to proceed.

Having a good understanding of some of these fundamental theories obviously makes identifying these kinds of abstractions and understanding what capabilities they have easier. Topics such as regular expressions are very well understood, even if they are sometimes difficult to use in practice. There are several other similar patterns that you should endeavor to understand; sorting and searching algorithms are another great example. Numerical methods for solving linear systems, constrained optimization, and graph algorithms, such as shortest path, are great examples. Numerical algorithms have a habit of turning up in unexpected places.

A digression into Sudoku

Many common puzzles and games ultimately require the solver or player to recognize patterns within the context of the game. This is especially obvious in Sudoku puzzles. Here, the objective is to place the digits 1-9 in a 9-by-9 grid so that each digit appears once in each row, column, and 3-by-3 box. Simple Sudoku puzzles only require basic techniques such as identifying pairs of digits or other kinds of mutual exclusion within a given row or column. However, harder puzzles require the solver to identify more complex patterns within the grid.

For instance, more difficult Sudoku puzzles require the solver to identify intermediate patterns such as “X-wings.” Here, the solver identifies a pair of rows (or columns) and a digit where the only valid position for the digit in each of the rows appears in a pair of columns. Since both rows must contain the digit, and it cannot appear in the same column in both rows, we can deduce that the only valid position for the digit in the two identified columns is within the two given rows, allowing us to eliminate this digit from other positions within the columns. (The same logic applies symmetrically if one started with a pair of columns.) There are many patterns in Sudoku, and being a good solver requires one to be able to identify and exploit the deductions provided by these patterns.

Common functional patterns

There are many functional patterns that you should be familiar with. We’ve already mentioned a few. Sorting patterns involve placing elements in order according to a sorting predicate. A search is a related problem that uses a condition or predicate to find a specific element or range within a set of data. Other patterns include filtering (and the related random sampling), shuffling, and permutations of a range of data. These are useful patterns that appear frequently in programming, sometimes in their standard form, but often in a less obvious form.

Many problems eventually reduce to solving a numerical problem, such as solving a system of equations, constrained optimizations, or graph algorithms. These tend to require some work to find the correct mathematical formulation of the problem. Again, this is obvious in some cases and not in others. More important patterns come from statistics and probability. Generating high-quality random numbers is a complicated topic. Problems that have a statistical component are usually obvious; any time there is uncertainty in measurements or methodology, statistics will probably be needed.

Combinatorics is the branch of mathematics that deals with the various ways that a (finite) set can be combined – how the elements can be permuted, or paired up, and so on. This branch includes graph theory, which appears frequently in programming problems. Problems that make explicit use of graph theory include dependency resolution (dependencies of a project are usually expressed as a directed graph), scheduling (turns out to be a graph coloring problem), and route planning is either a shortest path or traversal problem depending on the objectives.

Common structural patterns

Recognizing functional patterns is usually an early step in the problem-solving process. Structural patterns usually appear in the final stages, when designing algorithms or finally implementing your solution. Structural patterns include the design patterns and idioms for a particular language that allow you to design interfaces and make your code efficient. (The classic books on design patterns includes “structural patterns” as one of the topics; our usage of the term includes everything described in this book and not just what they describe as structural patterns.) We will use many structural patterns.

For example, the strategy (or policy) pattern is a means of encapsulating a family of different, but interchangeable, methodologies that can be used to obtain a result in different circumstances. For instance, one might define various algorithms for reading data from a file as strategies, and change the strategy based on the file type. We will make use of this pattern several times later in this book.

Other patterns worth mentioning are adapters, facades, flyweights, and proxies. These are all examples of patterns that adapt the interface of a given object or class to allow it to be used in some other context. Another useful pattern is a decorator, where the capabilities of an object are extended by means of a wrapping class.

An algorithm is a set of instructions for taking data, subject to some conditions called preconditions, and producing an output, satisfying some postconditions. Being able to formulate, articulate, and understand algorithms is an essential skill for anyone who writes software. Algorithms are generally written in a pseudocode language that describes the steps in a language-agnostic way that should be comprehensible to anyone familiar with basic programming constructions.

Reasoning about algorithms and understanding their computational complexity is a much larger topic that we will return to in Chapter 3. In this section, we focus on how to read algorithms and understand what they do.

Before we continue, we need to understand some basic theory of computation. Broadly speaking, there are two (equivalent) models of computation: sequential (Turing machine) and functional (lambda calculus). In the sequential model, one starts at the beginning and performs one step at a time until the task is complete, whereas in the functional model, one tackles parts of the problem by recursive calls to routines. Most programming languages favor one model or the other, though it is common to take aspects from both models. For instance, C++ is primarily sequential, though C++ templates are functional. On the other hand, Haskell is a purely functional language. Regardless of whether you explicitly make use of either model, it is important that you have knowledge of how both models operate.

Discussing algorithms is best done by means of example. We will now look at a very simple algorithm that will serve as a good introduction to the terms, and learn how to read the pseudocode descriptions of the steps of an algorithm.

Finding the maximum value in a list

Suppose you have a list of numbers (for simplicity, let’s say these are all integers) and you wish to find the maximum value contained therein. A very simple way to accomplish this is as follows:

1. Take the first element and store this as the current maximum.
2. For each of the remaining elements, compare to the current maximum and replace if it is larger.
3. Return the current maximum, which should now contain the global maximum.

Unless you know more, it is hard to do better than this. To know that you have the maximum value, you must have compared the proposed maximum to all of the elements of the list and checked that no other element exceeds this value.

This is an algorithm, though it is not presented in the pseudocode language mentioned above. To formalize the procedure, we should translate from the plain language above into pseudocode, which is more similar to how it would be written in code. An example of an algorithm that finds the maximum value in a list of numbers is given here.

INPUT: L is a list of numbers with at least one element
OUTPUT: Maximum value of L
max <- first element of L
WHILE not at end of L
  current <- next element of L
  IF current > max
    max <- current
  END
END
RETURN max

The uppercase words are keywords that denote common operations such as conditionals, loops, inputs, outputs, and return outputs. The OUTPUT statement declares the postconditions on the value that is provided by the RETURN statement. The <- denotes assignment. This is to make it fully distinct from the equality operator =. Notice that this form doesn’t make any reference to specific means of accessing the data; that is for the implementation to define based on the form of the data that is provided. Let’s see how this translates to standard C++. We can write this as a function template that takes a “container” that has begin, end, and a dependent type called value_type that supports <.

template <typename Container>
typename Container::value_type max_element(const Container& container) {
    auto begin = container.begin();
    auto end = container.end();
    if (begin == end) {
        throw std::invalid_argument("container must be non-empty");
    }
    auto max = *begin;
    ++begin;
    for (; begin != end; ++begin) {
        const auto& current = *begin;
        if (max < current) {
            max = current;
        }
    }
    return max;
}

This is a very general implementation that makes basically no assumptions about the form of the container or the element type that it contains. We throw an exception if the container is empty, which is one “correct” way to handle this. The maximum of an empty collection is ill-defined; the defining condition is vacuously true for any value. Another option would be to change the return type to optional<...> and return an empty value in this case. This has the advantage of potentially allowing for noexcept to be added to the function declaration, reducing the runtime cost of launching this function. Of course, this implementation is for demonstration only; you should use the constrained algorithm std::max_element from the algorithm header instead.

Notice that the general structure of the implementation is exactly as set out in the pseudocode. This is by design. You might even want to annotate parts of your code with comments to indicate exactly which part of the algorithm is being implemented. This helps other developers (including your future self) understand how you have implemented the algorithm, and what the specific parts are supposed to do.

We could generalize this implementation further by taking an optional comparison operator to be used instead of >, but this is complicated because there are conditions on orderings for which the maximum is a well-defined and unique value. For instance, in some orderings, not all values are comparable, which would demand special handling in the implementation. This is beyond our capabilities at the moment.

Characteristics of an algorithm

Not all lists of instructions are algorithms. To earn that distinction, they must satisfy some reasonable conditions:

• Finiteness: An algorithm must terminate after a finite number of iterations. The actual number of iterations will usually depend on the inputs (and outputs), and the number of iterations might grow rapidly, but it must eventually terminate.
• Definiteness: The steps of an algorithm should be described precisely and unambiguously. The objective is to translate an algorithm into computer code, so enough information must be present in order to reasonably do this.
• Inputs: An algorithm should have zero or more inputs that belong to well-defined sets (defined by the preconditions mentioned above).
• Outputs: An algorithm should have one or more outputs, derived from the inputs using the steps of the algorithm.
• Effectiveness: An algorithm should be effective in producing the desired output from the input parameters. The individual steps should be sufficiently basic that the process can be carried out exactly using pen and paper.

One usually turns to the rigor of mathematical proof to show that an algorithm satisfies these properties. For instance, mathematical induction can be used to prove that an algorithm is effective. The number of steps required by an algorithm usually depends on the size and nature of the inputs (and possibly the outputs). This relationship is called the complexity of the algorithm, which we shall discuss in more detail later, in Chapter 3.

The preconditions on the inputs should usually be checked in a good implementation of the algorithm. This can be done implicitly by means of static types, such as those in C++, or explicitly by conditional statements. There are various ways to do this, of course, depending on how robustly these checks should be performed.

One additional consideration when writing algorithms out is clarity. An algorithm is only useful to you and others if it can be understood and implemented. When presenting the pseudocode for an algorithm, you should make some effort to make sure the steps are clearly presented and easy to follow. The same way that decomposition can help solve problems, it can also help articulate their solutions, especially when the decomposition is “obvious.”

Let’s examine our algorithm for finding the maximum value of a list of numbers for these properties. The algorithm “visits” each element of the list exactly once, so for a list that contains elements, the algorithm will terminate after exactly steps. Thus the finiteness condition is satisfied. The algorithm is written clearly and unambiguously. The actual mode of traversing the list is not specified exactly, but, as we see in the C++ implementation, this is necessary to accommodate the different forms of “list” that might be available in any given programming language. (Not all languages have a std::vector, and not all containers support index access.) The only input is a list of numbers, which must satisfy the precondition of being non-empty. The only output is a single number that satisfies the postcondition of being the maximum value from the list. (A number is the maximum value of a set of numbers if is a member of and if each taken from satisfies .) The final condition is effectiveness. The steps listed do indeed produce the valid maximum value, and each step specifies exactly (though not specifically) one operation that must be performed.

Recursive algorithms

Not all problems have an algorithm that is so easy to write down. Let’s look at a more complicated example. Consider a very simple “language” defined by the following grammar.

letter ::= 'a' | 'b'
word   ::= letter | '[' word ',' word ']'

This language consists of “words,” that consist of either a single “letter” (taken from an alphabet of two letters, ‘a’ and ‘b’) or a pair of words surrounded by square brackets and separated by a comma. The characters that appear in quotations are literals that are exactly as they should appear. The other terms are as defined by the language. For instance, all of the following are valid words in this language.

a
 [a,a]
 [a,[a,b]]
 [[a,a],[a,[a,b]]]

Notice that this language is recursive in nature. A word might contain a pair of words, so it is natural that algorithms to work with this language might also be recursive in nature.

Suppose that we want to design an algorithm to extract the end of the first valid word from a string. This problem is complicated because we need to make sure that every open bracket is correctly matched with its closing partner. There are ways to do this without recursion (simply counting brackets might be sufficient), but the purpose of this example is to demonstrate recursive algorithms. Here’s how this algorithm might be defined.

INPUT: String s that starts with a valid word
OUTPUT: the position of the last character of the first valid word
character <- get first character from s
IF character = 'a' or character = 'b'
    RETURN 0
END
position <- 0
# s[0] is a '['
position <- position + 1
# find the first word after '['
a <- substring of s starting from index position
i <- end index of first word from a
position <- position + i
# s[position+1] is ','
position <- position + 1
# get the end of first word after ','
b <- substring of s starting at index position
j <- end index of first word from b
position <- position + j
# s[position + 1] is a ']' matching s[0]
position <- position + 1
RETURN position

The lines prefixed by a # are comments that are there for exposition only. Notice that this algorithm invokes itself twice when there is a word that is not a letter. This is the best way to ensure that one always contains the correct number of matching pairs. This is how we might implement the preceding algorithm in C++.

size_t end_of_first_word(std::string_view s) noexcept {
    if (!s.starts_with('['))  {
        return 0;
    }
    size_t position = 0;
    assert(s[position] == '[');
    position += 1;
    auto a = s.substr(position);
    auto i = end_of_first_word(a);
    position += i;
    position += 1;
    assert(s[position] == ',');
    position += 1;
    auto b = s.substr(position);
    auto j = end_of_first_word(b);
    position += j;
    position += 1;
    assert(s[position] == ']');
    return position;
}

This is not an optimal implementation, but that doesn’t matter right now. This is an exact translation of the pseudocode set out in the algorithm into C++, including assertions for the comments that describe what should be the case if our algorithm is correct.

We’re making use of the string_view class from C++17, which is a better way to work with non-owning strings than using raw const char* C-style strings. Using string_view will help ensure we don’t access memory outside of the string, which would be easily done with a C-style string. Moreover, it provides many convenience methods such as substr and starts_with. An alternative would be to work directly with a pair of iterators defining the range of values, but this is not much better than working with C-style strings.

We haven’t included any error checking in this implementation beyond the assertions, and the function is marked noexecpt. This means calling this function on a string that doesn’t start with a valid word is undefined behavior. The precondition on the string is that the string starts with a valid word, so it is the responsibility of the caller to ensure that this condition holds. This might be necessary on the “hot path” of a program, where checking for invalid strings might be too costly.

Writing out computations recursively is often easier than writing them out in a sequential manner, but one must remember that languages like C++ are not designed to work in this way. Recursive implementations might perform worse than a sequential implementation, since calling functions in C++ can be an expensive operation. Modern optimizing compilers might be able to inline function calls or otherwise reduce the cost of invoking these functions, by tail recursion optimization or otherwise. However, if the number of recursions cannot be known at compile time, the options are limited. Here is an example of how one might implement an algorithm that does not rely on recursion.

size_t end_of_first_word(std::string_view s) noexcept {
    size_t position = 0;
    int depth = 0;
    for (const auto& c : s) {
        switch (c) {
            case '[': ++depth; break;
            case ']': --depth;
            default:
                if (depth == 0) {
                    return position;
                }
        }
        ++position;
    }
    return position;
}

You may notice that this implementation is more difficult to reason about. Moreover, this implementation cannot so easily be generalized if some other operation needs to be performed, other than simply finding the position of the end of the first valid word.

The trade-off between flexibility and performance is a common dilemma for programmers. It is crucial to understand the properties of your solutions and design algorithms according to what is required by the context. If flexibility is not a concern, then it’s fine to optimize further and cut off the pathway to adding capabilities. However, one should never optimize until the performance is measured and the algorithm is known to underperform; measure twice, cut once.

This concludes the four components of computational thinking. Now we can see how modern features of C++ and good software engineering practices can help solve problems too.

There are many reasons to use C++ for solving problems, but the main reason for choosing C++ is that you need to make high-performance solutions. Modern C++ has many features that make it easy to write fast and (relatively) safe code without taking away control of the low-level primitives that the programmer can use to achieve the best possible performance. In this section, we will look at some of the features of modern C++ that can be used to write high-quality code for solving complex problems without compromising performance.

Before we start, we need to make something clear. Just because C++ provides the tools for micro-optimizing your code, that doesn’t mean that you should be using them. Modern compilers are far better at producing optimized machine code than even very experienced programmers writing hand-crafted assembly code. Trust the compiler toolchain to optimize your code and only spend time making micro-optimizations if it is absolutely necessary. Remember, you need to keep the bigger picture in mind, and over-optimizing one part of the code probably means that you are neglecting another.

That being said, it is important to understand that not all code is going to produce optimal performance. We have already seen an example where the C++ code is unlikely to achieve maximum performance with the recursive algorithm for parsing strings. But, as we mentioned in the commentary on that algorithm, the first task is to solve the problem and obtain a correct solution. Then, and only then, should you consider whether the algorithm has the desired performance characteristics.

It is a good idea to keep track of the parts of the code where performance will really matter. For example, any tight loops that perform an operation on (potentially) large sets of data are likely to need to be optimized, but a function that obtains records from a database is not, since this will always be constrained by the connection to the database. This allows you to focus on the most important parts when it comes to optimizing your code.

Another thing we need to address early is the issue of memory management. Do not manage your memory by hand with new and delete – or worse, with malloc and free. This is a recipe for creating memory leaks and invoking undefined behavior. Use standard containers such as std::vector, smart pointers (std::unique_ptr, std::shared_ptr), and other mechanisms provided by the standard template library (or other high-quality libraries such as Boost and Abseil). This is especially true if you make use of multithreading, where it is essential that your memory management is thread-safe.

Building C++ projects with CMake

This is a good point to discuss how we will configure and build our C++ projects throughout this book. CMake is a cross-platform build-system generator that constructs a set of build files (Makefiles, Ninja configurations, or otherwise) from a source file called CMakeLists.txt in the project root. The syntax can be a little frustrating at first, but you will quickly get used to it (if you aren’t already).

Modern CMake organizes code and dependencies into targets, which are usually either static or shared libraries or executables. It has a sophisticated mechanism for finding dependencies with its find_package function, which can then be linked to our targets, providing the necessary include directories and link lines necessary to successfully integrate the functionality of the dependency into our project. CMake also provides various functions for controlling the configuration of the compiler, such as setting the appropriate flags for a particular C++ standard in a portable way. This really takes the pain out of configuring cross-platform builds. A very basic skeleton for a C++ project, CMakeLists.txt, is as follows.

cmake_minimum_required(VERSION 3.30)
project(MyProject)
set(CMAKE_CXX_STANDARD 20)
set(CMAKE_CXX_STANDARD_REQUIRED ON)
add_executable(MyExecutable main.cpp)

The first line specifies the version of CMake that is required to configure the project. (At the time of writing, 3.30 was a fairly recent release of CMake.) The next line declares the project, which is the point at which CMake performs some background tasks such as finding the compiler and checking various settings. The next two lines set the C++ standard and set this standard to be required, which will cause CMake to emit an error if the compiler does not support this standard. Finally, we add an executable, called MyExecutable, which has one source file called main.cpp attached to it. We can link dependencies, external or other targets we declare in the CMake file, using this line:

target_link_libraries(MyExecutable PRIVATE MyDep)

Here, MyDep is the name of a target (either constructed using add_library or via a call to find_package) that should be linked. The PRIVATE specifier declares that the link information does not need to be propagated along with our target. This is sensible for an executable, which cannot be linked by another target, but it might not be appropriate for library targets.

To configure the build system, one uses the cmake executable from the command line or via an integration with your IDE of choice. (CLion has excellent CMake support, and there is a CMake extension of VSCode. Visual Studio also supports CMake projects.) On the command line, one can use the following invocation to configure and build the project in release mode.

cmake -B out/Release -S . -DCMAKE_BUILD_TYPE=Release
cmake --build out/Release --config=Release

The configured build files are placed in the out/Release directory, as specified by the –B argument, and the source file is specified with the –S argument (using ‘.' for the current working directory). The final argument sets the build type to release settings for the configuration. On most build systems, this is sufficient to build in release mode, but some build systems, such as MSBuild, support multiple configurations, in which case the --config=Release argument on the following line becomes necessary.

One of the advantages of CMake is that one can attach several different package managers, such as vcpkg or conan, to make obtaining, finding, and linking dependencies easier. Moreover, CMake is more feature-complete and easier to use than some of the similar tools that exist, such as Bazel and Meson. The documentation is quite readable, and it is extremely flexible.

Throughout the remainder of this book, and in the corresponding code repository, you’ll see many examples of CMake files and how to use them, particularly in Chapter 7 and Chapter 12.

Views, ranges, and algorithms

The C++20 standard brought many features to C++ that had been standard in other languages for many years. These include copy-less memory views (string_view and span), along with ranges and constrained algorithms. These are great improvements over the iterator-based interfaces that existed before, as they allow for cleaner and safer code.

String views and spans can be thought of as ranges in which the elements are stored contiguously in memory. (All the bytes are stored together and in order in a single block with no gaps between them.) String views are immutable in that the elements in the range cannot be modified. (Modifying strings in-place is dangerous because a new UTF-8 character might require more space than the character that it replaces, forcing a new allocation.) Spans provide mutable or immutable access to the block of elements.

A range is an abstraction on top of the usual iterator access to containers. Loosely speaking, a range is any object that exposes a begin and end that allow sequential access to the elements of the container; a far better description can be found at https://en.cppreference.com/w/cpp/ranges. The power of ranges comes from the fact that they can be composed with views, which provide modifications to the underlying iterator range. For example, the enumerate view modifies the range to return a pair of index and value. Combined with a range-based loop, these make for some very simple and easy-to-read code. For example, we could rewrite the more optimized version of the word-finding function from before using this mechanism as follows.

size_t end_of_first_word(string_view s) noexcept {
    int depth = 0;
    for (const auto [position, char] : std::views::enumerate(s)) {
        switch (char) {
            case '[': ++depth; break;
            case ']': --depth;
            default:
                if (depth == 0) {
                    return position;
                }
        }
    }
}

This isn’t substantially different from the previous implementation, but it does make the intent clearer. Now it is very obvious that the position variable should be tracking the current index of iteration. Moreover, this has the added benefit of decontaminating the surrounding scope, since the position is initialized inside the context of the range-based for loop. This is not a problem, but it does help keep code clean.

Templates and concepts

Templates are arguably one of the best features of C++, and also one of the most difficult and frustrating; anyone who has had to debug a template metaprogram bug will understand. The reason they are so powerful is that they allow the coder to write a single piece of code that can apply to many types on demand, without requiring a new implementation for each combination of types that is needed in a given program. There are some downsides to this: template instantiation is expensive for the compiler and very complex, and errors are very difficult to find and debug.

Templates actually form a complete programming language in themselves. They can be used to compute values at compile time, reducing the runtime cost of using those values to effectively zero. A template (class, function, or value) is instantiated by the compiler for each combination of types with which it is used, meaning that the compiler takes the body of the template and replaces the template parameters with the specific types that were provided by the code. For instance, our max_element template function could be instantiated by the following snippet of code. This instantiation is performed recursively, and if at any point in this process the compiler encounters an expression that is not valid, it raises a compiler error. These errors can be very difficult to diagnose because the error could have been caused far away from the first place where it is detected.

Concepts are an extension of the template mechanism that allows the user to declare the exact set of requirements for a template requirement up front. This means the compiler does not need to recursively instantiate the template to find out whether it is valid or not; it just checks whether the concept is valid for the type and emits an error if this is not the case. This leads to better error messages for the coder and potentially improves the speed of compilation. The basic concept for our max_element function might be defined as follows.

template <typename T>
concept OrderableContainer = requires(const T& t) {
    // Has a dependent type called "value_type", which is orderd by <
    std::totally_ordered<T::value_type>;
    // Has a begin and end methods valid on Const T&
    t.begin();
    t.end();
};

This is not a complete description because we do not specify that the begin and end methods should return iterators. Moreover, we don’t check that the value_type is copy constructible. Fortunately, we don’t need to reinvent the wheel here; we can just extend the forward_range concept from the standard library, as shown here.

template <typename T>
concept OrderableContainer = std::input_range<const T>
    && std::totally_ordered<std::range_value_t<const T>>
    && std::copy_constructible<std::range_value_t<const T>>;

This implementation checks that const T is an input_range, meaning that it has begin and end that return iterators that can read values in a forward iteration pattern, and that the value in this input range is ordered. This is actually significantly more general than the one we defined because ranges might be declared in other ways besides having an iterator to the first element and one past the last element. To account for this generalization, we really should make use of the range library rather than using the begin and end methods directly. This has the added benefit of creating cleaner code, as follows.

template <OrderableContainer Container>
std::range_value_t<Container> max_element(const Container& container) {
    auto begin = std::ranges::begin(container);
    const auto end = std::ranges::end(container);
    if (begin == end) {
        throw std::invalid_argument("Container must be non-empty");
    }
    auto max = *begin;
    ++begin;
    for (; begin != end; ++begin) {
        if (max < *begin) {
            max = *begin;
        }
    }
    return max;
}

Notice that we still have to check that the container is not empty. This can only be tested at runtime, whereas concepts are a compile-time construction. The only real difference is using the ranges::begin and ranges::end functions to get the iterators. This is probably overkill for such a simple function, but thinking in terms of concepts can be a great help as you try to formulate abstractions of your problem. Moreover, the more concepts you use, the better experience you will have debugging large, complex bodies of templated code. This covers how to handle data flexibly and efficiently. The next section shows how to handle cases where things go wrong.

Handling errors in C++

You should always account for things that might go wrong when implementing solutions to problems. There are always things that can go wrong: preconditions might be violated, the algorithm might fail to produce an outcome (for instance, if a numerical method fails to converge), data might be ill-formed or in a format that is not supported, there might be imposed limits that are reached (such as limiting the amount of time that can be spent on a single computation). Your implementation should have a mechanism for gracefully handling these kinds of errors that can occur.

It’s worth pointing out the difference between a failure and an error. For instance, if we implement a search algorithm, then this might reasonably fail to find an entry that satisfies the condition. This is a failure, but not an error. An error occurs when the program enters an invalid state or encounters a problem that it cannot handle. Failures should be handled as a routine problem using constructions such as std::optional or returning the end iterator for a failed search. Errors should be propagated to a point where they can be handled gracefully or terminate the application.

For a long time, there were two ways to handle errors in C++.

• We can use the built-in exception mechanism, which has the advantage of being global and, unless an in-flight exception is explicitly caught by a try-except block, will terminate the whole application with a meaningful error message. This is desirable in some cases, but sometimes not. The exception mechanism has benefits, but it is also a fairly expensive way to handle errors. It also causes the compiler to add a large amount of error-handling code around function calls and so on. Exceptions are particularly problematic on API boundaries or when working with remote procedure calls.
• Alternatively, we can use C-style errors, where functions return an integer that is 0 if no errors occurred and a non-zero error code if an error did occur. This is extremely lightweight and makes sense in many applications where a failure should not cause a program to terminate. The disadvantage is that the amount of information that can be conveyed by this mechanism is extremely limited.

Ideally, there should be an alternative that is lightweight, like the C-style error codes, but expressive and flexible, like the exception model. In C++23, the expected template was added to the C++ standard library, which allows one to return a single object that can either contain the valid result of a function call or an unexpected (error) value and is never empty. This has the advantage of permitting a very lightweight error handling mechanism that remains local (unless explicitly propagated), which provides a great deal of flexibility, especially on interface boundaries.

Besides errors, you might also consider adding logging capabilities to your code (though not in places where performance is critical). This can be extremely helpful when tracking down bugs or unexpected behavior once the code leaves the development environment. Remember that any code that is “shipped” or incorporated into a package needs to be maintained by somebody (including future you). Any time you can spend to make this process less arduous is time well spent. Adding logging using a standard logging library such as spdlog or equivalent is a low-effort way of providing a wealth of debugging information to users who cannot simply launch a debugger to see what is going on inside the library.

Testing your code

Even very simple software projects should have tests. Every new feature should add new tests. Every reported bug should be confirmed by adding tests. This is the only way to know that your code is “correct” and performs appropriately. There are several layers of tests that you should include: unit tests, integration tests, and end-to-end tests. A complete suite of tests should contain all three kinds of tests that cover as much of the package as feasibly possible.

1. The first layer contains unit tests, which test small, isolated units of functionality such as single functions and algorithms or a class interface. These are used to provide very fine-grained diagnostics on small parts of the software, aimed at identifying particular components that are not implemented correctly and making sure they run without causing unexpected errors or crashes. These tests tend to be small, quick to run, and relatively numerous. The suite of unit tests is run regularly as part of the development process, as well as when preparing for deployments.
2. The second layer contains integration tests that exercise larger groups of functionality that operate together, such as a collection of algorithms that work in tandem to solve a particular problem (or part thereof). These tend to be larger in scale than unit tests, but still operate on a relatively small scale. These tend to be larger tests that each exercise several different parts of the package together. These tests might take a little more time than unit tests and won’t be run quite as frequently – perhaps only once a new feature is complete, before and as part of the deployment process.
3. The final layer contains end-to-end tests, which test the entire lifetime of a piece of software, and tend to be larger and take longer than unit tests and integration tests. These might only be run when preparing to make a new release of the project, rather than as part of the development cycle. Generally, there are a small number of end-to-end tests that cover the main workflows of the software.

There are several testing harnesses available in C++. Two of the most common are GoogleTest and Catch2. GoogleTest is a very flexible library, is quite easy to set up and use, and is very extensible. Catch2 is a simpler library that is less flexible but easier to set up and use. Catch2 is a header-only library that does not require linking to external runtimes, whereas GoogleTest requires linking to the gtest.(so|dll) library. The tests included with the code for this book use GoogleTest.

Version control

Git (and GitHub) is the de facto standard for maintaining control of source code versions and managing a code base. It is a very effective tool for this task. Even relatively simple software projects should be kept in version control – which doesn’t have to be public or even stored on a server somewhere. This is for a number of reasons. The first is that, at some point, you might need to revert some code to what it was at some point in the past because of mistakes or performance regressions. The second reason, which might not be an issue for very small projects, is sharing your code with a larger team of developers (or even just between your own personal computers).

Services such as GitHub and GitLab provide the ability to run continuous integration testing that can help identify any changes that break existing functionality or otherwise find problems. This also helps to make sure that your code runs on all the different platforms that you support (Windows, Linux, macOS, and various different architectures). No single computer can test all of these configurations on its own. Continuous integration tools make this easy.

This chapter introduced the four components of computational thinking, which form a framework for solving large, complex programming problems. This is just the foundation. To be effective at solving problems, one needs to understand the theory and have a wealth of examples to draw upon. In the following chapters, we will deepen our theoretical knowledge and start to form bridges between the theory of solving problems and the facilities provided by the C++ language. This will help us understand the kinds of patterns and abstractions to look for in our problem-solving. We also discussed some good practices that will speed up the iteration of solutions and allow us to develop correct and efficient solutions to difficult problems quickly. In the next chapter, we will go into more detail about building abstractions in problems and the mechanisms available to us in C++ to facilitate abstract thinking.