Introduction:

Last week we started a journey. Over the course of several articles, we'll be looking at first simple, then advanced, techniques for code reuse. We'll be mostly identifying code-reuse as it applies to running all or some of the same code on different types, but the answers may surprise you: some of the solutions may not involve templates; for others, we'll be dragging out inheritance, but there won't be an "Is-A" relationship at play in the interface, nor any runtime hit. While in this first article things are probably going to seem pretty simple, you should expect things to ramp up quickly; brace yourselves.

Last week I gave you all 4 questions to ponder. Today we answer them.

Q: Why is it beneficial to sometimes have the same function/struct name do different things depending on their parameters? For example:

assert(abs(-5) == 5); //calling abs with an int
assert(abs(-2.3) == 2.3); //calling abs with a double

A:
1) Absolute value is a concept that is not inherently dependent on type. It makes sense to ask for the absolute value of both an int and a double, maybe even your user-defined Matrix class. It should not be limited to any of these types.

2) Our users don't want to have to remember different function names for use with different types. User code should be insulated from such distractions. If you've ever needed to get the absolute value of a floating-point number in C (ewwwe, C), you might be familiar with fabs, or "floating-point abs". This is ugly at best, and at worst, hangs users out to dry when their custom types need an absolute value function.

3) Having functions with different names for different types doesn't scale. You'll exhaust all meaningful names pretty quickly, but more importantly, find that it's easy to forget to add a new one when you add a new type. Say your language/compiler decides to add a new 128-bit integer type to it, they shouldn't have to remember to write an abs-style function too.

Q: What techniques allow us to create such differences? How can I write code so that calling a function foo(5) may produce different results than calling foo("hello")?

A:
1) Templates. [Basic] templates are best used when your function performs a single conceptual action that is implemented the same way over different types, as in our absolute value function. Here's what that would look like [1] [2]:

template<typename T> T abs(const T& value) {
  return value >= 0 ? value : -value;
}

What follows until the second solution to this question is a review of how templates work. Feel free to skim or skip the next 3 paragraphs, but if this is not your strong-suit, the analogies might prove helpful.

About templating: The template keyword says that we'll be varying the implementation on some compile-time parameters, specified as comma separated values between the < and > symbols. The typename T says that one of those compile-time parameters will be a type, like int, or double, or some user-defined type, Foo. Furthermore, typename T also says we will refer to this parameter, via an alias, T. The compiler will stamp out a copy of the implementation for each type T you invoke the function with, replacing "T" with the appropriate type.

Type deduction vs. manually specifying arguments: If I call the function as: abs(5), T is automatically deduced as int, because that's what you passed in at the call site, and so the compiler makes a version of the code where it sees int instead of T. I can also manually specify the template arguments as in: abs<int>(5.3), which says, you must use the version of abs that is templated over int, that is, where all occurrences of T are treated as occurrences of int. In this case, because 5.3 is not an int, the compiler will try to perform an implicit conversion and succeed via truncation (if it failed, as would be the case between strings and ints, you'd get a compiler error). Anything that is not manually specified, the compiler will attempt to deduce from the call-site context; if it's not possible to deduce the unspecified arguments, you'll get an error.

Duck typing: There's a saying, "If it looks like a duck, walks like a duck, quacks like a duck, then it is a duck". This is the approach to templates in C++. You can instantiate (compile with a particular type) my absolute value function template up there with any type for which there would be no compiler errors. Because an int has a negation operator and therefore "looks like a duck", it works. Because a string does not implement the negation operator, trying to invoke abs(string{"hi"}) will result in a compiler error.

2) Overloading. Overloading is best used when you want to do different conceptual implementations of a function depending on type. By contrast, sometimes you do want to perform the same conceptual task, but in different ways, say to optimize a particular case. Maybe the same conceptual task is being done, but the implementation just has to be fundamentally different from one type to the next, as is the case for C++ STL's to_string function. Other times, you might use different overloads to perform tasks that are entirely conceptually distinct. With overloading you have total flexibility to do whatever you like for each type.

A technical definition: Overloading is when you create functions with the same name that differ either in the number of, ordering of, or types of parameters (ignoring the names and only looking at types).

For example, imagine a function "get the Nth element of my container", I might have an overload for vector<int> and an overload for list<int>:

int getNthElement(const vector<int>& container, size_t n) {
  return container[n];
}

int getNthElement(const list<int>& container, size_t n) {
  auto itr = cbegin(container);
  for (auto i = 0u; i < n; ++i) {
    ++itr;
  }
  return *itr;
}

Why? Because I want my function to work with multiple containers, but to be fast when it can be. In a vector I can get to any element in O(1) time, in a list, O(N). I could template the code and have both containers use the O(N) implementation I used on the list<int>, and it would work, but that would make the vector code unnecessarily slow.

A notable difference: If there is no overload of my function for a particular type, I cannot use that type to call it (unless there's an implicit conversion to a type used in one of the overloads). In other words, I cannot call getNthElement(deque<int>{1, 2, 3, 4 ,5}, 3);. It just won't compile; There's no matching overload. With a templated solution that looked like the implementation I used for list<int>, it would accept a deque<int> too, without extra work (I could even make it work over more than just ints!).

3) Bonus: Both! Templates and overloading, together! There's no reason we can't have our cake and eat it too. We can solve the problem I described in the previous paragraph so that everybody wins. We'll make it so that I can call getNthElement on all of the STL containers, but also ensure that it's optimized/fast for vector. Here's what that looks like:

template<typename Container>
const typename Container::value_type& getNthElement(const Container& container, size_t n) {
  auto itr = cbegin(container);
  for (auto i = 0u; i < n; ++i) {
    ++itr;
  }
  return *itr;
}

template<typename T>
const T& getNthElement(const vector<T>& container, size_t n) {
  return container[n];
}

Let's break that down:

The first overload is the one that works over all STL containers. All STL containers present the forward iterator interface necessary to call that code successfully (including vector). I templated over the Container we will be looking at, implicitly including the type of the elements inside the container (now our function works with more than just ints! Hooray! Reuse!).

The second overload specifies precisely what container is being used: it takes a vector. It's still templated because we would like it to work over a vector of anything; there's no conceptual difference between getting the third element of a vector<int> and a vector<string>, so why write different code? The vector's overload does an optimized/fast implementation.

Overload preference: A more specialized (specific) overload is always preferred by the compiler. So if I try to call getNthElement(vector<int>{1, 2, 3, 4 ,5}, 3);, even though both overloads would match, the one templated over only the element type would match better.

Still imperfect: You might notice that although we can call this with deque now (getNthElement(deque<int>{1, 2, 3, 4 ,5}, 3);), that would invoke the slower implementation, and yet, it's actually possible to write an O(1) implementation for deques too! I leave it as an exercise for the reader to fix this problem for deque using only the techniques shown in this article. Solving this problem more generally is the subject of the next article in the series. As is often best in an interview scenario, I recommend coming up with a "not perfect, but working" solution before trying to boil down to 2 overloads, or even 1 (both of which I expect are beyond the skill level of most readers thus far). Feel free to post your answers below!

Q: For each technique that you identify, in what ways is the code allowed to vary? Is it possible for me to sneak in some optimization code for a particular case when I use one technique vs. another?

A:
1) In [basic] templates, the only things that are allowed to vary in your implementation are the types. The code is the same; it just gets "stamped out" with different types filling in the blanks. With what we've seen so far, having optimizations for certain cases/types is not possible. We’ll explore what it takes to have variable implementations in future articles on advanced template techniques.

2) In each overload of a function you have total freedom. You can perform completely different actions or do entirely different conceptual tasks. There are no limitations on how different the functions can be. Because we can vary anything, we can optimize for any type we like.

Q: Do the techniques you've identified work equally well for functions and structs?

A:
No. You cannot overload a struct (or class). The language simply doesn't allow you to overload here. As for why: just think about what that would look like. Would it mean differentiating based on parameters to constructors? If so, how can I have different constructors that use the same implementation (vector, for instance, has several constructors)? It just doesn't make a lot of sense, so, no, you cannot overload structs. No worries, we'll explore techniques that give us the same freedom with structs that overloading does for functions a bit later in this series.

Good news: Templating does work equally well with structs:

template<typename T> struct Foo {
  Foo(const T& value) : value_{value} {}
  void print() { cout << value_ << endl; }
private:
  T value_;
};

Our Foo struct will take any type, store a copy inside, and facilitate printing it whenever we like.

Recap:

Reusing the same names for functions is a great way to talk about a conceptual action. This insulates users from type differences and any optimizations we might add for specific cases.

From a different perspective, we've answered a couple of fundamental questions you might want to ask yourself when programming:
Q: How can I reuse the same implementation code with different types?
A: Templates! The implementation is consistent, we just plug-in different types into the same conceptual code.

Q: How can I use the same code to invoke different fundamental implementations selected by type?
A: Overloading! You have the power and flexibility to implement functions as differently as you like, depending on the types of the parameters.

We learned how to write code that accepts any type that "quacks like a duck" (templating). We also learned how to optimize implementations for the types that can be faster (overloading). We even looked at combining these two things to get the best of both worlds.

Lastly, we highlighted some of the limitations of each technique, some of which we will be able to overcome in future articles, some, which we cannot.

Footnotes:

[1] Perhaps the implementation of abs that first comes to mind is absValue = absValue >= 0 ? value : value * -1. As it happens, this is more complicated than it needs to be: we're invoking multiplication, which may not make sense (and thus, not be implemented) in the general case for user-defined types. Leveraging the negation operator instead makes our code more general in this subtle way.

[2] Especially after looking at the implementations I provide, you might ask "Why do I even care that abs can be called for a particular type"? I'd remind you that 1) abs is not the only function for which we seek code reuse; not all functions have a trivial implementation. 2) Names are exceedingly important in maintainable code. Having abs be a named action makes it more clear what's going on and actually enables other forms of code reuse in templated code.