Type Inference: Auto and Decltype

When a language supports type inference, it is often presented as just a convenient way to not have to explicitly write out types. “The compiler already knows the type—why should the programmer have to write it out?” Indeed, this point of view is important. Oftentimes, the type is just visual clutter, as demonstrated by the definition and usage of c_v_s_iter in Example 5-1, which is written in a pre-C​+​+11 style.

#include <algorithm>
#include <iostream>
#include <string>
#include <vector>

// trivial implementation of the unix uniq utility
// read lines from stdin
// write sorted unique lines to stdout
int main(int argc, char** argv) {
  using std::vector; using std::string; using std::sort;
  using std::unique; using std::cin; using std::cout;

  vector<string> lines;
  while (cin) {
    lines.emplace_back();
    getline(cin, lines.back());
  };

  sort(lines.begin(), lines.end());

  typedef typename vector<string>::const_iterator c_v_s_iter;
  c_v_s_iter const last = unique(lines.begin(), lines.end());
  lines.resize(last - lines.begin()); // keep only the result of
                                      // unique

  for (c_v_s_iter i = lines.begin(), e = lines.end(); i < e; ++i) {
    cout << (*i) << '
';
  }
}

If this doesn’t seem like a big deal, it’s because it isn’t—in this case. Still, it breaks the flow of reading code because of completely unnecessary complications. One’s mind wonders if the equivalent Python would be easier to read.

We can do better with a modern style.

  sort(begin(lines), end(lines));
  auto const last = unique(begin(lines), end(lines));
  lines.resize(last - begin(lines)); // keep only the result of
                                     // unique

  for (auto const& line : lines) {
    cout << line << '
';
  }

Once code becomes more complex, overflowing the programmer’s working memory, one is grateful for the absence of unnecessary symbols.

However, type inference does not merely make things easier. In some cases, it takes code from unthinkable¹ to obvious. For example, let’s implement it with boost::range.

  sort(begin(lines), end(lines));
  for (auto const& line : lines | uniqued) {
    cout << line << '
';
  }

The type uniqued returns is intractable at the least (especially over multiple pipes of filtered, sliced, etc.), and moreover, the programmer really does not care about what the iterator type is. The only relevant fact is that dereferencing it yields a string.² The code therefore expresses intent without extraneous detail and without losing a sliver of performance.

The addition of type inference does more than give the programmer another tool for writing programs faster. It also fundamentally destroyed the last remnants of the notion that type annotations are there for the compiler. Instead, the types one actually writes out are a layer of assertions that the programmer instructs the compiler to check, and clues to the reader. Writing auto means that the type is unimportant; only its behavior, as defined by its usage, is important. Writing the type out explicitly means the type has to be exactly what it says. Put another way: types are henceforth always intentional, never circumstantial.

Put this way, it is trivial to recognize the missing element in this scenario: auto means any type, and writing the type out explicitly means exactly this type, or a type convertible to it. There is no way, however, to constrain the type only partially. The family of solutions to this problem are called concepts in C​+​+, but so far, the committee has not reached consensus on important details of this feature. Getting it right the first time is important, as is not breaking existing code, and so concepts have been left out of the standard so far. The search for the ideal solution continues.

How Move Semantics Support Value-Semantic and Functional Programming

In the previous chapter, we indirectly explored the beautiful world of procedural programming: std::sort and std::unique are algorithms that mutate state passed to them. While this makes them wonderful building blocks for procedural programs, they do not compose well with a more functional style of programming.³

In C​+​+, writing in a functional style often came with a price of a mandatory copy of a parameter.⁴ Consider the implementation of sorted and uniqued as functions.

template <typename Container>
Container sorted(Container x) {
  std::sort(begin(x), end(x));
  return x;
}

template <typename Container>
Container uniqued(Container x) {
  x.resize(std::unique(begin(x), end(x)) - begin(x));
  return x;
}

In classic C​+​+, the natural way of getting a vector of unique lines uniqued(sorted(lines)) results in two (or three) expensive copies: first, lines is copied to become sorted’s parameter, and then the return value of sorted is copied to become uniqued’s parameter. Finally, the return value of uniqued is copied into a variable in the local scope, should one choose to store it.

In C​+​+​1​1, the two return values are moved instead⁵—in the case of vector, only pointers to the internal structure are copied. The rationale for moving return values instead of copying is that we know that the very next thing that happens to the returned temporary object is destruction. This well-chosen mechanism enabled us to get rid of two copies. But what about the first copy of lines? We get rid of it using std::move, which instructs the compiler to treat its parameter as if it were an unnamed temporary.

  lines = uniqued(sorted(std::move(lines)));

In the snippet, there are no copies at all. As a final step, the result is moved back into lines.⁶ This is just as efficient as the procedural version, while the functions, as implemented, supply all of the advantages of reasoning about code that come with a pure-functional style.

The ranged for loop is as easy to write as it would be in Python, but without performance loss.

  for (auto const& line : uniqued(sorted(std::move(lines)))) {
    cout << line << '
';
  }

No More Output Parameters

One of the problems classic C​+​+ inherited from C is that functions only return a single value. While one could have, in fact, returned a std::pair, boost::tuple, or other type defined simply to hold multiple values, it was not commonly done in practice, in part because returning large objects tended to be expensive if not done correctly,⁷ and in part because returning objects just to unpack them in several following lines is rather verbose.

The alternative was to use output parameters. One would create the objects that would become a function’s return value before calling the function, and then pass references to them to the function, which would assign values to them.

This is very efficient in execution, but not in programmer productivity. The output parameters are indistinguishable from the input parameters of the function when one is reading code, necessitating a thorough knowledge of exactly what the function does to its parameters in order to reason about code. Output parameters, consequently, were recognized as detracting from clarity.

The new tuple library, aided by move semantics to stay fast and lean, allows for much improvement. Consider the case where one wants to calculate some statistics of a sequence of numbers. We chose length, minimum and maximum, with the average and variance left as an exercise for the reader.

template <typename ConstInputIterator,
          typename MinMaxType =
              iterator_value_type<ConstInputIterator>>
auto lenminmax(ConstInputIterator first, ConstInputIterator last)
    -> std::tuple<size_t, MinMaxType, MinMaxType> {
  if (first == last) { return {0, 0, 0}; }
  size_t count{1};
  auto minimum(*first);
  auto maximum(minimum); // only evaluate *first once
  while (++first != last) {
    ++count;
    auto const value = *first;
    if (value < minimum) {
      minimum = value;
    } else if (maximum < value) {
      maximum = value;
    }
  }
  return {count, minimum, maximum};
}

The function returns three values, is as efficient as can be, and does not mutate any external state.

The following example shows how to use it:

  vector<int const> samples{5, 3, 6, 2, 4, 8, 9, 12, 3};
  int min, max;
  tie(ignore, min, max) = lenminmax(samples.begin(), samples.end());

  cout << "minimum: " << min << "
"
       << "maximum: " << max << "
";

Notice how we used tie to assign to min and max and ignore the length.

There is one more thing to consider: how did we discover the type of the tuple that lenminmax returns? We seem to use the magical iterator_value_type to infer the type the iterator returns.⁸ Logically, the type of minimum and maximum is whatever type the iterator’s reference is: the type of *first.

We can get that type with decltype(*first). Still, that’s not quite right, because *first returns a reference, and we need a value type. Fortunately, there is a way to get rid of references in types: std::remove_reference<T>::type. We just need to supply the type, which makes std::remove_reference<decltype(*first)>::type. This is quite a mouthful, so we would be better served if we could make a type alias for it. However, in the type alias, we cannot use "first" because the name is not defined outside of the function. Still, we need some kind of value inside the decltype to dereference. Again, the standard library has what we need: declval<T>(). declval<T>() gives us a fictional reference to use inside decltype in place of first. The result is in the next example.

template <typename T>
using iterator_value_type = typename std::remove_reference<
                              decltype(*std::declval<T>())>::type;

Now, we can just use it everywhere, like in the definition of the lenminmax function.

Inner Functions with Lambdas

Sometimes, an algorithm requires an action to always be performed in a particular way. Measurement is often such a thing. For instance, every time one writes into an output iterator, one must increment it (see push in the next example).

Merge sort is an algorithm that sorts a sequence of items by first splitting it into already sorted subsequences⁹ and then merging them two by two into successively longer sequences, until only one is left. The merge algorithm works by comparing the heads of both input sequences and moving the smaller one to the end of the output sequence. It repeats this process until both input sequences have been consumed.

This is conceptually very simple. When writing the merge routine, it very quickly crystallizes that we shall have to write two nearly identical pieces of code — one for when the head of the first sequence is to be moved, and one for the second sequence. However, with an inner function (advance), we can write this piece of code once, and just call it twice, with the roles of both sequences reversed.

template <typename InputIterator1, typename InputIterator2,
          typename OutputIterator>
auto move_merge(InputIterator1 first1, InputIterator1 last1,
                InputIterator2 first2, InputIterator2 last2,
                OutputIterator&& out) -> OutputIterator {
  using std::move; using std::forward;

  auto drain = [&out](auto& first, auto& last){
    return move(first, last, forward<OutputIterator>(out));
  };
  auto push = [&out](auto& value) { *out = move(value); ++out; };
  auto advance = [&](auto& first_a, auto& last_a, auto& value_a,
                     auto& first_b, auto& last_b, auto& value_b) {
    push(value_a);
    if (++first_a != last_a) {
      value_a = move(*first_a);
      return true;
    } else { // the sequence has ended. Drain the other one.
      push(value_b);
      out = drain(++first_b, last_b);
      return false;
    }
  };

  if      (first1 == last1) { return drain(first2, last2); }
  else if (first2 == last2) { return drain(first1, last1); }
  auto value1(move(*first1));
  auto value2(move(*first2));
  for (bool not_done = true; not_done;) {
    if (value2 < value1) {
      not_done = advance(first2, last2, value2,
                         first1, last1, value1);
    } else {
      not_done = advance(first1, last1, value1,
                         first2, last2, value2);
    }
  }
  return out;
}

Also notice that we were able to give the part of the algorithm that drains the final remaining sequence into the output sequence a name, even though the actual implementation is only one line. Every part of the algorithm reads cleanly.

This is also a great example of the difference in style between inner functions and regular functions. This much mutation, in-out parameters, etc., are extremely poor style when designing function signatures, because the implementation might be far from the point of use. In most contexts, in-out parameters cause higher cognitive load for the programmer, making bugs and slowdowns more probable.

However, inner functions are not public, and their implementation is close at hand—it is in the same scope! Here, in-out parameters do not cause higher cognitive load. Instead, they help us understand that the algorithm has the same structure for both branches after the comparison and make sure that it is in fact the same both times.

We defined drain in order to omit the rather cumbersome forwarding syntax from the call of move in order to make the names of the sequence iterators stand out better where it is called.

The purpose of push is that output iterators have to be incremented every time they are dereferenced, and some such iterators are rather heavy to copy. In order to be able to use pre-increment, two lines are needed.

Finally, advance is the meat of the algorithm. The reason for its definition is the aforementioned fact that, after we compare the heads of sequences and thus determine which head to move, moving one head looks exactly the same as moving the other.

Lambdas as a Scope with a Return Value

Lambda expressions can also be directly evaluated, finally allowing for some logic in initializing references and variables that are not default-constructible because they hold resources. Let’s take a look at a very simple implementation of a multithreaded producer-consumer queue.

For performance in using synchronized data structures, one should release a lock as soon as possible. At (1) in the next example, the element is returned as soon as it has been popped off the queue; the function then ends, the lock is released, and the element is processed afterward.

  deque<int> queue;
  bool done = false;
  mutex queue_mutex;
  condition_variable queue_changed;

  thread producer([&]{
    for (int i = 0; i < 1000; ++i) {
      {
        unique_lock<mutex> lock{queue_mutex};
        queue.push_back(i);
      }
      // one must release the lock before notifying
      queue_changed.notify_all();
    } // end for
    {
      unique_lock<mutex> lock{queue_mutex};
      done = true;
    }
    queue_changed.notify_all();
  });
  thread consumer([&]{
    while (true) {
      auto maybe_data = [&]()->boost::optional<int>{ // (1)
        unique_lock<mutex> lock{queue_mutex};
        queue_changed.wait(lock,
                           [&]{return done || !queue.empty();});
        if (!queue.empty()) {
          auto data = move(queue[0]);
          queue.pop_front();
          return boost::make_optional(move(data));
        }
        return {};
      }(); // release lock
      // do stuff with data!
      if (maybe_data) { std::cout << *maybe_data << '
'; }
      else { break; }
    }
  });
  producer.join();
  consumer.join();

Most often, you will want to encapsulate this logic into a class, but it is exceedingly hard to design general queuing interfaces that are nevertheless fast in all scenarios. Sometimes, an ad hoc approach is exactly what is needed, such as in a book, where the limit is a page. Without the gratuitous use of lambda functions, this code would be longer and less clear.