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(int array[], int n) {
  int sum = 0;
  for (int i = 0; i < n; ++i ) {
    sum += array[i];
  }
  return sum;
}

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 STL style supports both data structures.

Like find, we define a pair of iterators. first and last. The iterator type should support the requirements of InputIterator.

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

The value must be a regular type and the dereferenced iterator must be convertible to the value type.

The function signature becomes:

template <typename InputIt, typename T>
// requires: InputIt is convertible to T when dereferenced
//        && InputIt is EqualityComparable
//        && T is Regular
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.

 1#include <iostream>
 2#include <list>
 3
 4// accumulate the sum of values in range [first, last)
 5template <typename InputIt, typename T>
 6// requires: InputIt is convertible to T when dereferenced
 7//        && InputIt is EqualityComparable
 8//        && T is Regular
 9T sum (InputIt first, InputIt last, T value) {
10  while (first != last) {
11    value = value + *first;
12    ++first;
13  }
14  return value;
15}
16
17int main () {
18  float a[]  = {1,1,2,3,5,8,13,21,34};
19  float* end = a+sizeof(a)/sizeof(*a);
20  double d   = 0;
21
22  d = sum (a, end, d);
23  std::cout << "array sum  = " << d << '\n';
24
25  // now do list
26  d = 0;
27  std::list<float> b = {1,1,2,3,5,8,13,21,34};
28
29  d = sum (b.begin(), b.end(), d);
30  std::cout << "list sum  = " << d << '\n';
31  return 0;
32}

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 function pointer (or equivalent).

Example

The function signature becomes:

template <typename InputIt, typename T, typename BinaryOp>
// requires: InputIt is convertible to T when dereferenced
//        && InputIt is EqualityComparable
//        && T is Regular
T accumulate (InputIt first, 
              InputIt last, 
              T value,
              BinaryOp op) {

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

  value = op(value, *first);

This could be addition: operator+, but can now support any binary operation that the type T supports.

A default operation can be provided with a supporting template that calls accumulate with plus.

template <typename InputIt, typename T>
T accumulate (InputIt first, InputIt last, T value) {
  return accumulate(first, last, value, std::plus<T>());
}

Run It

 1#include <cstddef>
 2#include <iostream>
 3#include <functional>
 4#include <vector>
 5
 6// accumulate the sum of values in range [first, last)
 7// using the binary operation op
 8template <typename InputIt, typename T, typename BinaryOp>
 9// requires: InputIt is convertible to T when dereferenced
10//        && InputIt is EqualityComparable
11//        && T is Regular
12T accumulate (InputIt first,
13              InputIt last,
14              T value,
15              BinaryOp op) {
16  while (first != last) {
17    value = op(value, *first);
18    ++first;
19  }
20  return value;
21}
22
23// version that provides a default operation
24template <typename InputIt, typename T>
25T accumulate (InputIt first, InputIt last, T value) {
26  return accumulate(first, last, value, std::plus<T>());
27}
28
29int main () {
30  std::size_t sum = 0;
31  std::vector<std::size_t> x = {1,1,2,3,5,8,13,21,34};
32  sum = accumulate (x.begin(), x.end(), sum);
33  std::cout << "vector sum  = " << sum << '\n';
34
35  std::size_t product = 1;
36  product = accumulate (x.begin(), x.end(), product, std::multiplies<std::size_t>());
37  std::cout << "vector product  = " << product << '\n';
38  return 0;
39}

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

The parameter passed through BinaryOp op must be a valid type.

A function can take a pointer or a type as a parameter. Function objects passed as parameters must satisfy the requirements of function. Lambda expressions, function objects, and functions pointers are all acceptable. The STL has a large collection of operator types that can be passed to functions.

More to Explore