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

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;
}

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

#include <iostream> #include <list> // accumulate the sum of values in range [first, last) 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) { while (first != last) { value = value + *first; ++first; } return value; } int main () { float a[] = {1,1,2,3,5,8,13,21,34}; float* end = a+sizeof(a)/sizeof(*a); double d = 0; d = sum (a, end, d); std::cout << "array sum = " << d << '\n'; // now do list d = 0; std::list<float> b = {1,1,2,3,5,8,13,21,34}; d = sum (b.begin(), b.end(), d); std::cout << "list sum = " << d << '\n'; return 0; }

See this example running step-by-step

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).

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>());
}

#include <cstddef> #include <iostream> #include <functional> #include <vector> // accumulate the sum of values in range [first, last) // using the binary operation op 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) { while (first != last) { value = op(value, *first); ++first; } return value; } // version that provides a default operation template <typename InputIt, typename T> T accumulate (InputIt first, InputIt last, T value) { return accumulate(first, last, value, std::plus<T>()); } int main () { std::size_t sum = 0; std::vector<std::size_t> x = {1,1,2,3,5,8,13,21,34}; sum = accumulate (x.begin(), x.end(), sum); std::cout << "vector sum = " << sum << '\n'; std::size_t product = 1; product = accumulate (x.begin(), x.end(), product, std::multiplies<std::size_t>()); std::cout << "vector product = " << product << '\n'; return 0; }

See this example running step-by-step

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

• From CPP Core Guidelines

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

You have attempted of activities on this page