Metaprogramming

####Question 1: Given the following code:

template<class Source, class Destination>
struct is_non_narrowing_conversion
{
  static const bool value =
       std::is_convertible<Source, Destination>::value
    && std::is_integral<Source>::value
    && std::is_integral<Destination>::value
    && sizeof(Destination) >= sizeof(Source);
};

What is the result of calling is_non_narrowing_conversion<std::uint32_t, std::uint16_t>::value? And is_non_narrowing_conversion<std::uint16_t, std::uint32_t>::value?

####Answer 1: false when converting uint32_t to uint16_t and true when they're reversed. Note that this isn't like a normal function -- you don't start the program and have it count the number of bits in Destination and Source. Rather, the compiler knows such things and replaces the large expression initializing value with true or false, whichever it determines. Such a compile-time function is called a metafunction. [^1]

---

####Exercise/Question 2: Suppose we have the following point type:

template <typename T>
class Pt2
{
public:
  //constructor

  T x,y;
};

and we desire the following usage:

  Pt2<std::uint16_t> p1;
  Pt2<std::uint32_t> p2 = p1;//#1: Implicitly broaden
  Pt2<std::uint16_t> p3 = static_cast<Pt2<std::uint16_t> >(p2);//#2: Explicitly narrow
  Pt2<std::uint16_t> p4 = p2;//#3: ERROR - can't implicitly narrow

What type of constructor should we give Pt2?

####Answer 2: There are really two options for constructors here: implicit and explicit. Here's what an implicit constructor would look like:

template <typename U>
Pt2(const Pt2<U>& other) : x(other.x), y(other.y) {}

Plugging it into our use cases above will result in #1 compiling and running fine and #3 failing to compile, as desired. However, it will not permit #2, as the conversion x(other.x) will generate a compiler error. We can try casting to eliminate the error:

template <typename U>
Pt2(const Pt2<U>& other) : x(static_cast<T>(other.x)), y(static_cast<T>(other.y)) {}

But that will result in #1, #2 and #3 all compiling, allowing potentially unsafe implicit conversions between point types. In short, we're not "doing as the ints do."[^2] There's probably wisdom in only casting the underlying coordinates when an explicit conversion is requested:

template <typename U>
explicit Pt2(const Pt2<U>& other) : x(static_cast<T>(other.x)), y(static_cast<T>(other.y)) {}

This works for #2 and #3, but now doesn't permit #1 to work -- all conversions must be explicit.

---

####Exercise: What we really want is to have both an implicit and an explicit constructor, but the following won't work due to calling ambiguities:

template <typename U>
Pt2(const Pt2<U>& other) : x(other.x), y(other.y) {}

template <typename U>
explicit Pt2(const Pt2<U>& other) : x(static_cast<T>(other.x)), y(static_cast<T>(other.y)) {}

There are cases where the compiler may call either constructor. Rather than choosing arbitrarily, it errors out of compilation. What we really need is to provide hints to the compiler, telling it to provide the implicit constructor when the conversion is non-narrowing, and to provide the explicit constructor when it is. As luck has it, we can use std::enable_if together with our is_non_narrowing_conversion metafunction to do exactly that.

template <typename U>
Pt2(const Pt2<U>& other, typename std::enable_if<is_non_narrowing_conversion<U,T>::value>::type* = NULL) : x(other.x), y(other.y) {}

template <typename U>
explicit Pt2(const Pt2<U>& other, typename std::enable_if<!is_non_narrowing_conversion<U,T>::value>::type* = NULL) : x(static_cast<T>(other.x)), y(static_cast<T>(other.y)) {}

We now get exactly what we desired: #1 and #2 compile fine, but #3 fails to compile. We were able to use metaprogramming to provide a syntax which mimics built-ins -- resulting in more natural-looking code.[^3]

---

####Exercise: Consider the following iterators:

template <typename Iterator>
class verbose_strided_iterator
{
public:
  typedef typename std::iterator_traits<Iterator>::value_type value_type;
  typedef typename std::iterator_traits<Iterator>::reference reference;
  typedef typename std::iterator_traits<Iterator>::pointer pointer;
  //It must be random access, verbose_strided_iterator is merely forward.
  typedef typename std::iterator_traits<Iterator>::iterator_category iterator_category;
  typedef typename std::iterator_traits<Iterator>::difference_type difference_type;

  explicit verbose_strided_iterator(Iterator iterator, difference_type step)
    : iterator_(iterator), step_(step)
  {}

  void operator++()
  { iterator_ += step_; }

  verbose_strided_iterator<Iterator> operator++(int)
  {
    auto to_return = *this;
    this->operator++();
    return to_return;
  }

  reference operator*() const
  { return *iterator_; }

  friend bool operator==(const verbose_strided_iterator<Iterator>& lhs,
                         const verbose_strided_iterator<Iterator>& rhs)
  { return lhs.iterator_ == rhs.iterator_; }

  friend bool operator!=(const verbose_strided_iterator<Iterator>& lhs,
                         const verbose_strided_iterator<Iterator>& rhs)
  { return lhs.iterator_ != rhs.iterator_; }

private:
  Iterator iterator_;
  difference_type step_;
};//end verbose_strided_iterator

template <typename Iterator>
class verbose_reverse_iterator
{
public:
  typedef typename std::iterator_traits<Iterator>::value_type value_type;
  typedef typename std::iterator_traits<Iterator>::reference reference;
  typedef typename std::iterator_traits<Iterator>::pointer pointer;
  //It must be bidirectional, verbose_reverse_iterator is merely forward.
  typedef typename std::iterator_traits<Iterator>::iterator_category iterator_category;
  typedef typename std::iterator_traits<Iterator>::difference_type difference_type;

  explicit verbose_reverse_iterator(Iterator iterator)
    : iterator_(iterator)
  {}

  void operator++()
  { --iterator_; }

  verbose_reverse_iterator<Iterator> operator++(int)
  {
    auto to_return = *this;
    this->operator++();
    return to_return;
  }

  reference operator*() const
  {
    auto to_return = iterator_;
    --to_return;
    return *to_return;
  }

  friend bool operator==(const verbose_reverse_iterator<Iterator>& lhs,
                         const verbose_reverse_iterator<Iterator>& rhs)
  { return lhs.iterator_ == rhs.iterator_; }

  friend bool operator!=(const verbose_reverse_iterator<Iterator>& lhs,
                         const verbose_reverse_iterator<Iterator>& rhs)
  { return lhs.iterator_ != rhs.iterator_; }

private:
  Iterator iterator_;
};//end verbose_reverse_iterator

These don't implement a large interface (like they would for categories like random access), but there's still plenty that needs to be done for each. Furthermore, most of the code could be shared between the strided and reverse iterators. For a programmer comfortable in the world of inheritance-based, dynamic polymorphism, it's most natural to create a base class from which more minimal iterators inherit.

template <typename Iterator>
class virtual_iterator_helper
{
public:
  typedef typename std::iterator_traits<Iterator>::value_type value_type;
  typedef typename std::iterator_traits<Iterator>::reference reference;
  typedef typename std::iterator_traits<Iterator>::pointer pointer;
  //It must be bidirectional, verbose_reverse_iterator is merely forward.
  typedef typename std::iterator_traits<Iterator>::iterator_category iterator_category;
  typedef typename std::iterator_traits<Iterator>::difference_type difference_type;

  explicit virtual_iterator_helper(Iterator iterator)
    : iterator_(iterator)
  {}

  //Allow inheritance -- see previous training.
  virtual ~virtual_iterator_helper() {}

  void operator++()
  { increment(iterator_); }

  //No post-increment operator here.

  reference operator*() const
  { return dereference(iterator_); }

  friend bool operator==(const virtual_iterator_helper<Iterator>& lhs,
                         const virtual_iterator_helper<Iterator>& rhs)
  { return lhs.iterator_ == rhs.iterator_; }

  friend bool operator!=(const virtual_iterator_helper<Iterator>& lhs,
                         const virtual_iterator_helper<Iterator>& rhs)
  { return lhs.iterator_ != rhs.iterator_; }

private:
  virtual void increment(Iterator& it) = 0;
  virtual reference dereference(Iterator it) const = 0;

  Iterator iterator_;
};

And it could be reused as shown:

template <typename Iterator>
class virtual_strided_iterator : public virtual_iterator_helper<Iterator>
{
  typedef virtual_iterator_helper<Iterator> super_t;
public:
  explicit virtual_strided_iterator(Iterator iterator, typename super_t::difference_type step)
    : super_t(iterator), step_(step) {}

  virtual_strided_iterator<Iterator> operator++(int)
  {
    auto to_return = *this;
    this->operator++();
    return to_return;
  }

private:
  virtual void increment(Iterator& it)
  { it += step_; }
  virtual typename super_t::reference dereference(Iterator it) const
  { return *it; }

  typename super_t::difference_type step_;
};
template <typename Iterator>
class virtual_reverse_iterator : public virtual_iterator_helper<Iterator>
{
  typedef virtual_iterator_helper<Iterator> super_t;
public:
  explicit virtual_reverse_iterator(Iterator iterator) : super_t(iterator) {}

  virtual_reverse_iterator<Iterator> operator++(int)
  {
    auto to_return = *this;
    this->operator++();
    return to_return;
  }

private:
  virtual void increment(Iterator& it)
  { --it; }
  virtual typename super_t::reference dereference(Iterator it) const
  {
    --it;
    return *it;
  }
};

Now, that definitely reduces the some of the tedious boilerplate. It's far from perfect, however. For instance, it's awkward that we have to provide the post-increment operator ourselves since it's supposed to return a copy of the most-derived type. The same would be true for other functions which should return the derived class, including +=, -= and post-decrement. We'll discuss other problems when we answer

---

####Question 3: Compare performance between the verbose and virtual versions. In many cases, concern about the overhead of virtual function calls is overblown. Is it in this case? ####Answer 3: In this case it's much slower to make a virtual function call. The average run took between 3.9 and 6.9 times longer to execute with our virtual_iterator_helper class. Now, sometimes it's reasonable to accept such overhead in exchange for other benefits. virtual functions allow decoupling, which could allow the actual iterator type to be unknown to the algorithm, and the algorithm implementation to be hidden from the caller. In this instance, however, we see no such benefit: the standard algorithms' implementations are visible to the caller (on purpose, for performance reasons), and we're not trying to hide our derived classes' types. [^4]

A 5x slowdown is likely untenable for those wishing to use our iterators. Users will likely use for-loops to recreate algorithms instead. To avoid that, we'll attempt to create a solution which sacrifices the faux-decoupling to regain performance, while still reducing the syntactic burden of writing iterators.

---

Let's try solving the issue with needing to write our own post-increment first. It turns out that its solution is the germ of an idea we can use to improve performance.

We'll restate the problem. Post-increment must return a copy of the most-derived type, however, using virtual_iterator_helper we have no way of knowing what that is. Now virtual_iterator_helper does know the underlying iterator type, since we passed it in as a template parameter:

template <typename Iterator> class virtual_iterator_helper
//Usage:
template <typename Iterator> virtual_reverse_iterator
  : public virtual_iterator_helper<Iterator>

Let's try passing in the most-derived type instead:

template <typename Derived> class crtp_iterator_helper
//Usage:
template <typename Iterator> crtp_reverse_iterator
  : public crtp_iterator_helper<crtp_reverse_iterator<Iterator> >

The previous might look strange -- you might wonder if it's even legal. Rest assured it is -- it even has a name: the Curiously Recurring Template Pattern (CRTP) [^5]. Since we now have access to the most derived type, we can write that operator now:

template <typename Derived> class crtp_iterator_helper {
  ...
  Derived operator++(int) {
    auto to_return = static_cast<Derived>(*this);
    increment(iterator_);
    return to_return;
  }
  ...
  virtual void increment(Iterator iterator) = 0;

  Iterator iterator_;
};

Passing in the derived type means we can say goodbye to the unneeded decoupling benefits, but we can use that tighter coupling to improve performance. As noted above, the performance killer is the use of virtual functions. It means an extra pointer indirection for every call, and it prevents some very useful optimizations. We can remove any need for virtual methods by directly calling derived-class methods:

template <typename Derived> class crtp_iterator_helper {
  ...
  Derived operator++(int) {
    auto to_return = static_cast<Derived>(*this);
    static_cast<Derived&>(*this).increment(iterator_);
    return to_return;
  }
  ...
  //We don't need this anymore -- the derived class should just provide it.
  //virtual void increment(Iterator iterator) = 0;

  Iterator iterator_;
};

With a couple more small adjustments[^6], here's the completed class:

template <typename Derived> class crtp_iterator_helper;
template <template <typename> class Derived, typename Iterator>
class crtp_iterator_helper<Derived<Iterator> >
{
public:
  typedef typename std::iterator_traits<Iterator>::value_type value_type;
  typedef typename std::iterator_traits<Iterator>::reference reference;
  typedef typename std::iterator_traits<Iterator>::pointer pointer;
  //It must be bidirectional, verbose_reverse_iterator is merely forward.
  typedef typename std::iterator_traits<Iterator>::iterator_category iterator_category;
  typedef typename std::iterator_traits<Iterator>::difference_type difference_type;

  explicit crtp_iterator_helper(Iterator iterator)
    : iterator_(iterator)
  {}

  void operator++()
  { static_cast<Derived<Iterator>&>(*this).increment(iterator_); }

  Derived<Iterator> operator++(int) {
    auto to_return = static_cast<Derived<Iterator> >(*this);
    static_cast<Derived<Iterator>&>(*this).increment(iterator_);
    return to_return;
  }

  reference operator*() const
 { return static_cast<const Derived<Iterator>&>(*this).dereference(iterator_); }

  friend bool operator==(const Derived<Iterator>& lhs, const Derived<Iterator>& rhs)
  { return lhs.iterator_ == rhs.iterator_; }

  friend bool operator!=(const Derived<Iterator>& lhs, const Derived<Iterator>& rhs)
  { return lhs.iterator_ != rhs.iterator_; }

protected:
  //Allow inheritance of non-Liskov substitutible class (google it).
  ~crtp_iterator_helper() {}

private:
  Iterator iterator_;
};

And here's how we can use it:

template <typename Iterator>
class crtp_strided_iterator : public crtp_iterator_helper<crtp_strided_iterator<Iterator> > {
  typedef crtp_iterator_helper<crtp_strided_iterator<Iterator> > super_t;
public:
  explicit crtp_strided_iterator(Iterator iterator, typename super_t::difference_type step)
    : super_t(iterator), step_(step) {}

  void increment(Iterator& it) { it += step_; }

  typename super_t::reference dereference(Iterator it) const { return *it; }

private:
  typename super_t::difference_type step_;
};
template <typename Iterator>
class crtp_reverse_iterator : public crtp_iterator_helper<crtp_reverse_iterator<Iterator> > {
  typedef crtp_iterator_helper<crtp_reverse_iterator<Iterator> > super_t;
public:
  explicit crtp_reverse_iterator(Iterator iterator) : crtp_iterator_helper(iterator) {}

  void increment(Iterator& it) { --it; }

  typename super_t::reference dereference(Iterator it) const {
    --it;
    return *it;
  }
};

---

####Question 4a: How does the performance between this and the verbose version compare?

####Answer 4a: Performance is much better than it was. In my timings, there was no runtime difference between the two versions.

---

####Question 4b: Are there downsides to using CRTP versus traditional inheritance?

####Answer 4b: In this instance, CRTP seems to have been the ideal solution -- we were able to simplify usage of the class and improve performance. However, consider the following scenario:

struct B {
  void call_foo() const { foo(); }
private:
  virtual void foo() const = 0;
};
struct D1 : public B {
  ...
private:
  virtual void foo() const { ... }
};
struct D2 : public B {
  ...
private:
  virtual void foo() const { ... }
};
std::vector<std::unique_ptr<B>> vec{std::make_unique<D1>(), std::make_unique<D2>()};

Suppose an over-zealous programmer, concerned about the overhead of calling foo through a virtual function, decided to employ CRTP:

template <typename Derived> struct B {
  void call_foo() const { static_cast<const Derived&>(*this).foo(); }
};
struct D1 : public B<D1> {
  void foo() const { ... }
};
struct D2 : public B<D2> {
  void foo() const { ... }
};

How would we describe the list of derived objects?

std::vector<std::unique_ptr<B>> vec{std::make_unique<D1>(), std::make_unique<D2>()};

won't work, since B is no longer a type -- it's a class template. Obviously we can't use B<D1> nor B<D2> either, since that won't work with half the objects we put in the list.

This shows that we increase our coupling when we use CRTP -- we trade abstraction for performance. So, when should we use it? It has been my experience that most code in large C++ applications would benefit more from looser coupling than from very slight performance improvements -- especially since most code isn't critical path.[^7] The guideline is simple: Don't use CRTP unless the problem is amenable to the tighter coupling and measurements indicate that you need the performance boost.

---

####Notes: [^1] See C++ Template Metaprogramming section 2.2

[^2] See Effective C++ Item 18.

[^3] I learned this technique from the quantity type of the Boost.Units library

[^4] If you ever do need to hide the type of the iterator/range, see boost's any_range.

[^5] The term was coined by Jim Coplien. For more details, see wikipedia.

[^6] You'll note that I actually define a template specialization which expects a single template argument representing the underlying iterator. A slightly more verbose, but more general approach wouldn't require the derived class to be templatized on an iterator type. The Boost.Iterator library doesn't require this, and supports a much more general set of features than our toy example here.

[^7] A fun made-up metric I've heard is that 80% of users' time is spent executing 20% of the code.