17.3. Refactoring to Algorithms

The primary objective of refactoring is to improve code. Those improvements might take many forms. In this section we are going to focus on refactoring a pair of functions that at first glance do not appear to be doing the same thing. However, we will see the similarities and how refactoring is accomplished, step-by-step.

Given two functions, each sums the values provided.

The first function adds all of the integers in a raw array:

int sum(const int array[], std::size_t n) {
  int total = 0;
  for (int i = 0; i < n; ++i ) {
    total += array[i];
  }
  return total;
}

The second adds all of the elements in a simple, home-grown linked list.

// create a simple node in a linked list
struct node {
  int value = 0;
  node* next = nullptr;
};

int sum(node* first) {
  int s = 0;
  while (first) {        // first not false or zero
    s += first->value;
    first = first->next;
  }
  return s;
}

How can we generalize and combine these two functions into one? We can rewrite both functions in a form of pseudo-code.

// we need a generic type 'T'
T sum(/* data */ )                   // somehow parameterize this
{
  T s = 0;
  while (/* not at end */ ) {        // loop through all elements
    s = s + /* get value */;         // compute sum
    /* get next data element */;
  }
  return s;
}

We need several generic operations on data:

• Determine if we are not at end of data

• Get value

• Get next element

Example

The standard library algorithm style supports both data structures.

Like find, we define a pair of iterators. first and last. The iterator type should satisfy the C++20 std::input_iterator concept.

A separate template parameter for the initial sum finishes the signature.

The accumulator type must be movable and assignable from the result of the operation. The operation must be invocable with the accumulator and a dereferenced iterator.

The function signature becomes:

template <std::input_iterator InputIt, class T>
requires std::movable<T>
      && requires(T value, std::iter_reference_t<InputIt> element) {
           { value + element } -> std::convertible_to<T>;
         }
T sum(InputIt first, InputIt last, T value) {

The main loop checks whether we should continue and accumulates the sum:

while (first != last) {
  value = value + *first;
  ++first;

Run It

And we can use this algorithm with either a raw array or a linked list.

#include <concepts>
#include <iostream>
#include <iterator>
#include <list>

// accumulate the sum of values in range [first, last)
template <std::input_iterator InputIt, class T>
requires std::movable<T>
      && requires(T value, std::iter_reference_t<InputIt> element) {
           { value + element } -> std::convertible_to<T>;
         }
T sum(InputIt first, InputIt last, T value) {
  while (first != last) {
    value = value + *first;
    ++first;
  }
  return value;
}

int main() {
  float values[] = {1, 1, 2, 3, 5, 8, 13, 21, 34};
  float* end = values + sizeof(values) / sizeof(*values);
  double total = sum(values, end, 0.0);
  std::cout << "array sum = " << total << '\n';

  std::list<float> linked_values = {1, 1, 2, 3, 5, 8, 13, 21, 34};
  total = sum(linked_values.begin(), linked_values.end(), 0.0);
  std::cout << "list sum = " << total << '\n';
}

17.3.1. Removing a final assumption

Can we make sum even more generic?

Sum still has a hard-coded assumption that addition (the operator+ function) is the operation that we always want to perform.

Might we want to perform any binary operation on a sequence? If yes, then we can add one more template parameter allowing callers to pass in a callable object such as a function pointer, lambda, or function object.

Example

The function signature becomes:

template <std::input_iterator InputIt, class T, class BinaryOp>
requires std::movable<T>
      && std::invocable<BinaryOp&, T, std::iter_reference_t<InputIt>>
      && std::assignable_from<
           T&, std::invoke_result_t<
                 BinaryOp&, T, std::iter_reference_t<InputIt>>>
T my_accumulate(InputIt first,
                InputIt last,
                T value,
                BinaryOp op) {

The main loop replaces the explicit + with a call to a provided binary operator:

  value = std::invoke(op, std::move(value), *first);

This could be addition, represented by std::plus<>, but can now support any binary operation that satisfies the callable requirements.

A default operation can be provided with an overload that calls my_accumulate with plus.

template <std::input_iterator InputIt, class T>
requires std::movable<T>
      && std::invocable<
           std::plus<>&, T, std::iter_reference_t<InputIt>>
      && std::assignable_from<
           T&, std::invoke_result_t<
                 std::plus<>&, T, std::iter_reference_t<InputIt>>>
T my_accumulate(InputIt first, InputIt last, T value) {
  return my_accumulate(first, last, std::move(value), std::plus<>{});
}

Run It

#include <concepts>
#include <cstddef>
#include <functional>
#include <iostream>
#include <iterator>
#include <type_traits>
#include <utility>
#include <vector>

// using
template <std::input_iterator InputIt, class T, class BinaryOp>
requires std::movable<T>
      && std::invocable<BinaryOp&, T, std::iter_reference_t<InputIt>>
      && std::assignable_from<
           T&, std::invoke_result_t<
                 BinaryOp&, T, std::iter_reference_t<InputIt>>>
T my_accumulate(InputIt first,
                InputIt last,
                T value,
                BinaryOp op) {
  while (first != last) {
    value = std::invoke(op, std::move(value), *first);
    ++first;
  }
  return value;
}

// default operation
template <std::input_iterator InputIt, class T>
requires std::movable<T>
      && std::invocable<
           std::plus<>&, T, std::iter_reference_t<InputIt>>
      && std::assignable_from<
           T&, std::invoke_result_t<
                 std::plus<>&, T, std::iter_reference_t<InputIt>>>
T my_accumulate(InputIt first, InputIt last, T value) {
  return my_accumulate(first, last, std::move(value), std::plus<>{});
}

int main() {
  std::size_t sum = 0;
  std::vector<std::size_t> values = {1, 1, 2, 3, 5, 8, 13, 21, 34};
  sum = my_accumulate(values.begin(), values.end(), sum);
  std::cout << "vector sum = " << sum << '\n';

  std::size_t product = 1;
  product = my_accumulate(values.begin(), values.end(), product,
                          std::multiplies<std::size_t>{});
  std::cout << "vector product = " << product << '\n';
}

Note that we did not pass + or * to a function. The symbol + is not a type.

The template parameter BinaryOp names the type of the callable object, and the parameter op is an object of that type. The object must satisfy the C++20 std::invocable concept for the accumulator and element types.

Lambda expressions, function objects, and function pointers are all acceptable callables. The standard library provides a large collection of function objects such as std::plus and std::multiplies.

---

More to Explore

• T.2 Use templates to express algorithms that apply to many argument types

• std::accumulate

• std::input_iterator

• std::invocable

• std::plus