21.2 Recursive Duos

Ru-Brd

Consider the following object definition:

 Duo<int, Duo<char, Duo<bool, double> > > q4; 

The type of q4 is a so-called recursive duo . It is a type instantiated from the Duo template, and the second type argument is itself a Duo as well. We could also use recursion of the first parameter, but in the remainder of this discussion, recursive duo refers only to Duo s with a second template argument that is instantiated from the Duo template.

21.2.1 Number of Fields

It's relatively straightforward to count that q4 collects four values of types int , char , bool , and double respectively. To facilitate the formal counting of the number of fields, we can further partially specialize the Duo template:

  // tuples/duo2.hpp  template <typename A, typename B, typename C>  class Duo<A, Duo<B,C> > {    public:      typedef A        T1;  // type of first field  typedef Duo<B,C> T2;  // type of second field  enum { N = Duo<B,C>::N + 1 };  // number of fields  private:      T1 value1;  // value of first field  T2 value2;  // value of second field  public:  // the other public members are unchanged    }; 

For completeness, let's provide a partial specialization of Duo so that it can degenerate into a nonhomogeneous container holding just one field:

  // tuples/duo6.hpp   // partial specialization for  Duo<>  with only one field  template <typename A>  struct Duo<A,void> {    public:      typedef A T1;  // type of first field  typedef void T2;  // type of second field  enum { N = 1 };  // number of fields  private:      T1 value1;  // value of first field  public:  // constructors  Duo() : value1() {      }      Duo (T1 const & a)       : value1(a) {      }  // field access  T1& v1() {          return value1;      }      T1 const& v1() const {          return value1;      }      void v2() {      }      void v2() const {      }   }; 

Note that the v2() members aren't really meaningful in the partial specialization, but occasionally it is useful to have them for orthogonality.

21.2.2 Type of Fields

A recursive duo is not really handy compared with, say, a Trio or Quartet class that we could write. For example, to access the third value of the q4 object in the previous code, we'd have to use an expression like

 q4.v2().v1() 

This is hardly compact or intuitive. Fortunately, it is possible to write recursive templates that efficiently retrieve the values and types of fields in a recursive duo.

Let's first look at the code for a type function DuoT to retrieve the n th type of a recursive duo (you can find the code in tuples/duo3.hpp ). The generic definition

  // primary template for type of  N  th field of (duo)  T  template <int N, typename T>  class DuoT {    public:      typedef void ResultT;  // in general, the result type is  void  }; 

ensures that the result type is void for non- Duo s. Fairly simple partial specializations take care of retrieving the types from nonrecursive Duo s:

  // specialization for  1  st field of a plain duo  template <typename A, typename B>  class DuoT <1, Duo<A,B> > {    public:      typedef A ResultT;  };  // specialization for  2  nd field of a plain duo  template <typename A, typename B>  class DuoT<2, Duo<A,B> > {    public:      typedef B ResultT;  }; 

With this in place, the n th type of a recursive duo, in general, is the ( n -1 )th type of the second field:

  // specialization for  N  th field of a recursive duo  template <int N, typename A, typename B, typename C>  class DuoT<N, Duo<A, Duo<B,C> > > {    public:      typedef typename DuoT<N-1, Duo<B,C> >::ResultT ResultT;  }; 

However, the request for the first type of a recursive duo ends the recursion:

  // specialization for  1  st field of a recursive duo  template <typename A, typename B, typename C>  class DuoT<1, Duo<A, Duo<B,C> > > {    public:      typedef A ResultT;  }; 

Note that the case for the second type of the recursive duo also needs a partial specialization to avoid ambiguity with the nonrecursive case:

  // specialization for  2  nd field of a recursive duo  template<typename A, typename B, typename C>  class DuoT<2, Duo<A, Duo<B, C> > > {    public:      typedef B ResultT;  }; 

This is certainly not the only way to implement the DuoT template. The interested reader could, for example, try to leverage the IfThenElse template (see Section 15.2.4 on page 272) to achieve an equivalent effect.

21.2.3 Value of Fields

Extracting the n th value (as an lvalue) from a recursive duo is only slightly more complex than extracting the corresponding type. The interface we intend to achieve is the form val< N >( duo ) . However, we need a helper class template DuoValue to implement it because only class templates can be partially specialized, and partial specialization allows us to recur to the desired value more efficiently. Here is how the val() functions delegate their task:

  // tuples/duo5.hpp  #include "typeop.hpp"  // return  N  th value of variable duo  template <int N, typename A, typename B>  inline  typename TypeOp<typename DuoT<N, Duo<A, B> >::ResultT>::RefT  val(Duo<A, B>& d)  {      return DuoValue<N, Duo<A, B> >::get(d);  }  // return  N  th value of constant duo  template <int N, typename A, typename B>  inline  typename TypeOp<typename DuoT<N, Duo<A, B> >::ResultT>::RefConstT  val(Duo<A, B> const& d)  {      return DuoValue<N, Duo<A, B> >::get(d);  } 

The DuoT template already proves itself useful to declare the return type of the val() functions. We also used the TypeOp type function developed in Section 15.2.3 on page 269 to create a reference type reliably, even if the field type is itself already a reference.

The following complete implementation of DuoValue clearly parallels our previous discussion of DuoT (the role of each element of the implementation is discussed next ):

  // tuples/duo4.hpp  #include "typeop.hpp"  // primary template for value of  N  th field of (duo)  T  template <int N, typename T>  class DuoValue {    public:      static void get(T&) {  // in general, we have no value  }      static void get(T const&) {      }  };  // specialization for  1  st field of a plain duo  template <typename A, typename B>  class DuoValue<1, Duo<A, B> > {    public:      static A& get(Duo<A, B> &d) {          return d.v1();      }      static A const& get(Duo<A, B> const &d) {          return d.v1();      }  };  // specialization for  2  nd field of a plain duo  template <typename A, typename B>  class DuoValue<2, Duo<A, B> > {    public:      static B& get(Duo<A, B> &d) {          return d.v2();      }      static B const& get(Duo<A, B> const &d) {          return d.v2();      }  };  // specialization for  N  th field of recursive duo  template <int N, typename A, typename B, typename C>  struct DuoValue<N, Duo<A, Duo<B,C> > > {      static      typename TypeOp<typename DuoT<N-1, Duo<B,C> >::ResultT>::RefT      get(Duo<A, Duo<B,C> > &d) {          return DuoValue<N-1, Duo<B,C> >::get(d.v2());      }      static typename TypeOp<typename DuoT<N-1, Duo<B,C>                            >::ResultT>::RefConstT      get(Duo<A, Duo<B,C> > const &d) {          return DuoValue<N-1, Duo<B,C> >::get(d.v2());      }  };  // specialization for  1  st field of recursive duo  template <typename A, typename B, typename C>  class DuoValue<1, Duo<A, Duo<B,C> > > {    public:      static A& get(Duo<A, Duo<B,C> > &d) {          return d.v1();      }      static A const& get(Duo<A, Duo<B,C> > const &d) {          return d.v1();      }  };  // specialization for  2  nd field of recursive duo  template <typename A, typename B, typename C>  class DuoValue<2, Duo<A, Duo<B,C> > > {    public:      static B& get(Duo<A, Duo<B,C> > &d) {          return d.v2().v1();      }      static B const& get(Duo<A, Duo<B,C> > const &d) {          return d.v2().v1();      }  }; 

As with DuoT , we provide a generic definition of DuoValue that maps to functions that return void . Because function templates can return void expressions, this makes the application of val() to nonduos or out-of-range values of N valid (although useless, but it can simplify the implementation of certain templates):

  // primary template for value of  N  th field of (duo)  T  template <int N, typename T>  class DuoValue {    public:      static void get(T&) {  // in general, we have no value  }      static void get(T const&) {      }  }; 

As before, we first specialize for nonrecursive duos:

  // specialization for  1  st field of a plain duo  template <typename A, typename B>  class DuoValue<1, Duo<A, B> > {    public:      static A& get(Duo<A, B> &d) {          return d.v1();      }      static A const& get(Duo<A, B> const& d) {          return d.v1();      }  };   

Then we specialize for recursive duos (again DuoT comes in handy):

 template <int N, typename A, typename B, typename C>  class DuoValue<N, Duo<A, Duo<B, C> > > {    public:      static      typename TypeOp<typename DuoT<N-1, Duo<B, C> >::ResultT>::RefT      get(Duo<A, Duo<B, C> > &d) {          return DuoValue<N-1, Duo<B, C> >::get(d.v2());      }   };  // specialization for  1  st field of recursive duo  template <typename A, typename B, typename C>  class DuoValue<1, Duo<A, Duo<B, C> > > {    public:      static A& get(Duo<A, Duo<B, C> > &d) {          return d.v1();      }   };  // specialization for  2  nd field of recursive duo  template <typename A, typename B, typename C>  class DuoValue<2, Duo<A, Duo<B, C> > > {    public:      static B& get(Duo<A, Duo<B, C> > &d) {          return d.v2().v1();      }   }; 

The following program shows how to use duos:

  // tuples/duo5.cpp  #include "duo1.hpp"  #include "duo2.hpp"  #include "duo3.hpp"  #include "duo4.hpp"  #include "duo5.hpp"  #include <iostream>  int main()  {  // create and use simple duo  Duo<bool,int> d;      std::cout << d.v1() << std::endl;      std::cout << val<1>(d) << std::endl;  // create and use triple  Duo<bool,Duo<int,float> > t;      val<1>(t) = true;      val<2>(t) = 42;      val<3>(t) = 0.2;      std::cout << val<1>(t) << std::endl;      std::cout << val<2>(t) << std::endl;      std::cout << val<3>(t) << std::endl;  } 

The call of

 val<3>(t) 

ends up in the call of

 t.v2().v2() 

Because the recursion is unwrapped at compile time during the template instantiation process and the functions are simple inline accessors, these facilities end up being quite efficient. A good compiler reduces this to the same code as a simple structure field access.

However, it is still cumbersome to declare and construct recursive Duo objects. The next section addresses this challenge.

Ru-Brd