Variadic tuple<..> — clever vs obvious

I mentioned in my previous post how the tuple<..> template class will be defined with variadic template parameters in the future.

template< typename ... TYPEs > class tuple;

How do you define the body of a template like that? The implementation described in N2080 (see section A.1 on page 10) essentially defines tuple as a recursive series of base classes, where tuple<A,B,C> inherits from tuple<B,C> which in turn inherits from tuple<C>. In this implementation, tuple<A,B,C> only has to provide a member for type A, while tuple<B,C> provides the member for B and tuple<C> provides the member for type C.

  // Based on implementation in N2080
  template< typename ... TYPEs >
  class
tuple;

  // Specialization for empty tuple
  template< >
  class
tuple< >
  { };

  // Specialization for non-empty tuples
  template< typename Head, typename ... Tail >
  class
tuple< Head, Tail ... >
  : private tuple< Tail ... >
  { protected:
      Head m_head;

    /* .. etc .. */
  };

This is truly a beautiful solution, elegant and clever. It’s too bad the types end up in reverse order, which will matter in C++0x when tuple becomes a POD type. The restrictions on POD are loosening in C++0x, partly to make them work with tuple.

The above implementation would mean you’d have to reverse the values in an initialization list.

// Reverse the values in the initialization list.
tuple< double, char > my_tuple = { 'A', 3.2345 };

Probably the nicest way to solve the reverse problem is to make Head variadic instead of Tail.

/* .. as above .. */

  // Specialization for non-empty tuples
  template< typename ... Head, typename Tail >
  class
tuple< Head ..., Tail >
  : private tuple< Head ... >
  { protected:
      Tail m_tail;

    /* .. etc .. */
  };

I’m pretty sure that will work — I’ll check it when I get a compliant C++ compiler. This solution should be obvious, but people like me are used to thinking of a list as a single-link chain of cons cells, where car is Head and cdr is Tail. The pattern matching in Erlang also encourages <Head,Tail…> thinking instead of <Head…,Tail>.

The current Boost (1_37) implementation solves this problem by making the tail a member variable instead of a supertype. It’s a little more complicated than that — Boost cannot use variadic template params of course. And Boost uses the boost::tuples::details::cons struct to implement the recursive typelist. But it boils down to a head member var followed by tail.

Another possibility is to work from a reversed typelist.

# include <boost/mpl/assert.hpp>
# include <boost/mpl/list.hpp>
# include <boost/mpl/reverse.hpp>
# include <boost/mpl/front.hpp>
# include <boost/mpl/pop_front.hpp>
# include <boost/type_traits/is_same.hpp>

namespace mpl = boost::mpl;
using boost::is_same;

  typedef
  mpl::list< int, float, double >::type
typelist;

  typedef
  mpl::reverse< typelist >::type
reversed_typelist;

  typedef
  mpl::front< reversed_typelist >::type
head_reversed;

  typedef
  mpl::pop_front< reversed_typelist >::type
tail_reversed;

  typedef
  mpl::front< tail_reversed >::type
second_reversed;

BOOST_MPL_ASSERT( (is_same< head_reversed, double >));
BOOST_MPL_ASSERT( (is_same< second_reversed, float >));

But at this point I have to confess that as much as I love clever recursive solutions, what I really want is a dumb iterating solution. After all, the operator is an iterator of sorts. It expands a packed term into a sequence of resolved terms. I was naively hoping that something like this would work.

/* This is probably illegal */

  template< typename ... TYPEs > 
  class 
tuple
  {
    protected:
      TYPEs ... values;

    /* .. etc .. */
  };

I just feel this is clearly expressed, even if it’s not flashingly brilliant.

But I’m pretty sure only generates comma-separated lists. So it can be used in template and function parameter lists, and to generate a comma-separated list of expressions. But it won’t work in the situation above. Don’t quote me on this however — I haven’t messed with gcc4.3 in experimental C++0x mode yet.

Using templates to define an array class with constructors

In my last post I talked about the DEFINE_CLASS_ARRAY(..) preprocessing macro that defines a array-like classs able to invoke constructors on the array elements. In this post I’ll show another way to define array-like classes that use the constructors, this time using templates.

In C++ primitive arrays the elements are initialized either with an initializer list, with the default (no arg) constructor, or with the copy constructor. And you can only use an initializer list and copy constructor under special circumstances. The psuedo-arrays defined in this and the last posts show how you might get around this limitation and use other constructors.

As usual, start with the headers.

# include <boost/static_assert.hpp>
# include <boost/throw_exception.hpp>

First we’ll define the base class array_with_ctor_class_info<T,N> that makes commom typedefs and statics available from the array-wrapper classes. This class has no data members and so adds nothing to the size of the derived classes. Without this base class we would repeat these definitions in the main template definition and in the two template specializations below.

// Forward declaration
template< typename VALUE_T, std::size_t SIZE >
class array_with_ctor;

// Class info for array_with_ctor<T,N>.
// This has no data members and will add no
// size when used as a base type.
template< typename VALUE_T, std::size_t SIZE >
class array_with_ctor_class_info
{
  // value_type
  public:
      typedef VALUE_T
    value_type;

  // size_type
  // static_size
  // get_size( )
  // get_max_size( )
  public:
      typedef std::size_t
    size_type;

      static
      size_type const
    static_size
      = SIZE;

      static
      size_type
    get_size( )
      throw( )
      { return static_size; }

      static
      size_type
    get_max_size( )
      throw( )
      { return static_size; }

  // empty_type
  // is_empty( )
  public:
      // Like the terminator of a list (nil).
      typedef array_with_ctor< value_type, 0 >
    empty_type;

      static
      bool
    is_empty( )
      throw( )
      { return size( ) == 0; }

      static
      empty_type /* not const */
    empty_inst;

      // empty_type is a class with no non-static data
      // members, so it doesn't matter if this inst
      // is exposed as a non-const.
      static
      empty_type &
    get_empty_inst( )
      throw( )
      { return empty_inst; }

  // rest_type
  // has_rest( )
  public:
      typedef array_with_ctor
              <  value_type
               , (static_size == 0) ? 0 : (static_size - 1)
              >
    rest_type;

      static
      bool
    has_rest( )
      throw( )
      { return size( ) > 0; }

  // Bounds checking
  public:
      static
      void
    check_bounds_maybe_throw( size_type i)
      /* throw( std::out_of_range) */
      { if ( i >= size( ) ) {
          throw
            std::out_of_range(
              "index out of range");
      } }

      static
      void
    check_bounds_assert( size_type i)
      throw( )
      { BOOST_ASSERT( i < size( )); }
};

Now we define array_with_ctor<T,N>, the psuedo-array class. We define it like a Lisp-style list, with two data members (think car and cdr). The first data member (called first_) holds the first element in the array, and the other data member (rest_) is an array_with_ctor<T,N-1> or an array of all the remaining elements. So this class is recursively defined.

Remember this is a bare-bones class. You’d add lots of methods if you were adding this to a library. This is just a brief illustration of the recursive constructors and accessors.

I present this in a very narrow style because this blog has a narrow page. I’d probably opt for a wider style in an .hpp file, matching the style of the rest of the project. Consistency is something to strive for. But this is just a demo, and I don’t have to be consistent, so I’ll just use a style that looks good here.

// BODY cannot have a comma in it unless it is surrounded
// by parentheses. Curly braces are not enough.
# define DECLARE_CONST_AND_NORMAL( RETURN_T, HEADER, BODY) \
    RETURN_T HEADER BODY \
    const RETURN_T HEADER const BODY

// array_with_ctor< VALUE_T, SIZE >
// Specializations for SIZEs 1 and 0 follow.
template< typename VALUE_T, std::size_t SIZE >
class array_with_ctor
: public array_with_ctor_class_info< VALUE_T, SIZE >
{
  // Constructors
  // Any of these can throw an error if value_type throws an
  // error during construction.
  public:
      // Default ctor
      // Assumes value_type has a default ctor.
    array_with_ctor( )
      /* inherits throw from value_type ctor */
      : first_( )
      , rest_( )
      { }

      // Copy constructor (and more)
      // Assumes value_type has a copy ctor.
      // Works when copying from an array with a different size.
      // Does not work when ALT_SIZE is zero.
      template< typename ALT_VALUE_T, size_type ALT_SIZE >
    array_with_ctor(
        const array_with_ctor< ALT_VALUE_T, ALT_SIZE >& src)
      /* inherits throw from value_type ctor */
      : first_( src.get_first( ))
      , rest_( src.get_rest( ))
      { }

      // Specialization of above template copy ctor
      // When src array is smaller, the last element is
      // repeated.
      template< typename ALT_VALUE_T >
    array_with_ctor(
        const array_with_ctor< ALT_VALUE_T, 1 >& src)
      /* inherits throw from value_type ctor */
      : first_( src.get_first( ))
      , rest_( src)
      { }

      // One-param template ctor
      // Repeatedly invokes value_type ctor.
      // Sets all elements to the same value.
      template< typename INIT_T >
    array_with_ctor( INIT_T const & init)
      /* inherits throw from value_type ctor */
      : first_( init)
      , rest_( init)
      { }

  // Array-like access:
  //   operator [ i ] - does not check bounds
  //   get_at( i)     - throws if out-of-bounds
  //   get_at_no_checking( i)
  public:
      DECLARE_CONST_AND_NORMAL(
      value_type & ,
    operator []( size_type i) ,
      throw( )
      { return get_at_no_checking( i); }
      )

      DECLARE_CONST_AND_NORMAL(
      value_type & ,
    get_at( size_type i) ,
      /* throw( std::out_of_range) */
      { check_bounds_maybe_throw( i);
        return get_at_no_checking( i);
      }
      )

      DECLARE_CONST_AND_NORMAL(
      value_type & ,
    get_at_no_checking( size_type i) ,
      throw( )
      { check_bounds_assert( i);
        // Get like this is a raw array.
        return *((& get_first( )) + i);

        // We could define this recursively instead,
        // although it is much slower.
        //
        //   return (0 == i) ?
        //     get_first( ) :
        //     get_rest( ).get_at( i - 1);
      }
      )

  // Low-level access:
  //   array<T,N>.get_first( ) -> T&
  //   array<T,N>.get_rest( )  -> array<T,N-1>&
  public:
      DECLARE_CONST_AND_NORMAL(
      value_type & ,
    get_first( ) ,
      throw( )
      { return first_; }
      )

      DECLARE_CONST_AND_NORMAL(
      rest_type & ,
    get_rest( ) ,
      throw( )
      { return rest_; }
      )

  // Private data members
  private:
    value_type first_;
    rest_type  rest_ ;
};

Notice that we define the constructors recursively, but we choose not to define get_at_no_checking(..) recursively and instead treat the entire class like an array to do an address calculation. To get the 20th element recursively would require 20 nested function calls, which we can avoid by acting like a primitive array. Constructing an array of 20 elements also requires 20 nested calls, but this is harder to avoid.

Here’s the specialization for array_with_ctor_class_info<T,1>, which is the class at the end of the chain. The rest_ data member and all its uses have been removed.

// Specialization with SIZE == 1.
template< typename VALUE_T >
class array_with_ctor< VALUE_T, 1 >
: public array_with_ctor_class_info< VALUE_T, 1 >
{
  // Constructors
  // Any of these can throw an error if value_type throws an
  // error during construction.
  public:
      // Default ctor
      // Assumes value_type has a default ctor.
    array_with_ctor( )
      : first_( )
      { }

      // Copy constructor (and more)
      // Assumes value_type has a copy ctor.
      // Works when copying from an array with a different size.
      // Does not work when ALT_SIZE is zero (compiler
      // will complain).
      template< typename ALT_VALUE_T, size_type ALT_SIZE >
    array_with_ctor(
        const array_with_ctor< ALT_VALUE_T, ALT_SIZE >& src)
      : first_( src.get_first( ))
      { }

      // One-param template ctor
      template< typename INIT_T >
    array_with_ctor( INIT_T const & init)
      : first_( init)
      { }

  // Array-like access:
  //   operator [ i ] - does not check bounds
  //   get_at( i)     - throws if out-of-bounds
  //   get_at_no_checking( i)
  public:
      DECLARE_CONST_AND_NORMAL(
      value_type & ,
    operator []( size_type i) ,
      throw( )
      { return get_at_no_checking( i); }
      )

      DECLARE_CONST_AND_NORMAL(
      value_type & ,
    get_at( size_type i) ,
      /* throw( std::out_of_range) */
      { check_bounds_maybe_throw( i);
        return get_at_no_checking( i);
      }
      )

      DECLARE_CONST_AND_NORMAL(
      value_type & ,
    get_at_no_checking( size_type i) ,
      throw( )
      { check_bounds_assert( i);
        BOOST_ASSERT( i == 0);
        return get_first( );
      }
      )

  // Low-level access:
  //   array<T,N>.get_first( ) -> T&
  //   array<T,N>.get_rest( )  -> array<T,N-1>&
  public:
      DECLARE_CONST_AND_NORMAL(
      value_type & ,
    get_first( ) ,
      throw( )
      { return first_; }
      )

	  // This is not necessary.
	  // This could be static.
      DECLARE_CONST_AND_NORMAL(
      rest_type & ,
    get_rest( ) ,
      throw( )
      { return get_empty_inst( ); }
      )

  // Private data members
  private:
    value_type first_;
};

And here is the specialization for array_with_ctor_class_info<T,0>. This class is probably not necessary. It is not part of the definition of the other array_with_ctor_class_info<T,N>s, and would never be needed if we got rid of array_with_ctor_class_info<T,1>::get_rest(). But I include it here because is a little like the nil symbol/empty-list in Lisp.

// Specialization with SIZE == 0.
template< typename VALUE_T >
class array_with_ctor< VALUE_T, 0 >
: public array_with_ctor_class_info< VALUE_T, 0 >
{
  // Constructors
  //   Default ctor - auto-generated
  //   Copy ctor - auto-generated

  // We could define get_rest( ) to return *this.
};

Here are some tests to make sure our arrays are the same size as primitive arrays. This is evidence that these arrays also have the same memory layout as primitive arrays or boost::array<T,N>, but I should write some tests to prove that since it is assumed in get_at_no_checking(..).

BOOST_STATIC_ASSERT(
    sizeof( array_with_ctor< char, 10 > ) ==
    sizeof( char[ 10 ] ));

BOOST_STATIC_ASSERT(
    sizeof( array_with_ctor< double, 44 > ) ==
    sizeof( double[ 44 ] ));

BOOST_STATIC_ASSERT(
    sizeof(
      array_with_ctor<
        array_with_ctor< int, 5 >, 3 >
    ) ==
    sizeof( int[ 3 ][ 5 ] ));

And here are a few simple examples of these array-like classes in use.

const
array_with_ctor< short, 10 > ten_const_shorts( -5);

array_with_ctor< long, 10 > ten_longs     = ten_const_shorts;
array_with_ctor< long,  5 > five_longs    = ten_const_shorts;
array_with_ctor< long, 15 > fifteen_longs = ten_const_shorts;

// This is as deep as my msvc++ setup will go.
const array_with_ctor< long, 498 > huge = five_longs;

Because these classes are defined recursively they should not be used for large arrays. Indeed, my compiler chokes on any array with more than 498 elements. And the recursive constructor for a 498 element array nests 498 times, so it is slow, and it uses a lot of runtime stack (assuming tail-recursion is not flattened into a loop). The destructor nests just as deeply.

But this class works fine for small arrays. We should probably define constructors with up to about 10 parameters so you can construct arrays of up to 10 elements with different values. This is hard to do with C-style varargs (#include <cstdarg>) but will be easier with the variadic parameters coming in C++0x.

    ... how a variadic constructor might look ...

      // The last arg might be another array.
      template< typename INIT_T, typename... REST_T>
    array_with_ctor( const INIT_T& init, REST_T... rest)
      : first_( init)
      , rest_( rest...)
      { }

      // For the last arg.
      template< typename INIT_T >
    array_with_ctor( const INIT_T& init)
      : first_( init)
      , rest_( init )
      { }

And there you have it, an array-like class that does not use primitive C++ arrays and allows the elements to be ctor’ed.

If you are looking for an array to use in your own code, remember array_with_ctor<T,N> is not complete. It does not provide STL-like typedefs and iterators, and some of the naming is non-STL (is_empty() instead of empty(), etc). You’re probably better off using boost::array<T,N>, which works for huge arrays and initializer lists but has no ctors. The array_with_ctor<T,N> class would be OK for small lists where you need the constructor methods.

One thing I would like in the Boost (or Std) library is a fixed-sized std::vector< T, AllocT> that does not allocate memory. The fixed_vector<T,N>::max_size( ) method would return N (constant), but size() could be changed just like in the normal std::vector< T, AllocT>. The fixed-size memory would be uninitialized bytes, and the elements would be constructed/destructed on demand. Other classes, like fixed_stack<T,N>, fixed_queue<T,N> and fixed_circular_buffer<T,N> could be defined using fixed_vector<T,N>, maybe as adaptor classes (like std::stack< T, std::vector<T> > uses std::vector<T>).

Using BOOST_PP_.. macros to define an array class with constructors

Sometimes when programming you just want an array of values, and you want to be able to construct the individual elements of the array, which isn’t easy with a raw array.

You could use std::tr1::tuple<..>, or even std::pair<..> as your “array”, although it will have to be small (tuples are limited to 10 values). Or you could work with uninitialized bytes and invoke the constructors explicitly with new( pvoid_raw_memory) type( ctor_params) or std::uninitialized_fill_n(..) or allocator<type>.construct(..).

You cannot use boost::array<..> if you want to use the element constructors. boost::array<..> has no constructors (besides the auto-generated copy and default ctors). This design choice was made so boost::array<..> objects can be initialized with the plain-old-data (pod) initializer lists.

You could define a quick class with a bunch of repeated elements that works like an array. Templates and macros make this job easier. This article shows how you can an array-like class with macros.

I’m going to use the Boost Preprocessor BOOST_PP_.. macros to declare repetitious parts of the class.

# include <boost/static_assert.hpp>

# include <boost/preprocessor/cat.hpp>
# include <boost/preprocessor/repetition/repeat.hpp>
# include <boost/preprocessor/repetition/enum.hpp>
# include <boost/preprocessor/repetition/enum_binary_params.hpp>
# include <boost/preprocessor/facilities/intercept.hpp>

These headers give us the tools to define the macro DEFINE_CLASS_ARRAY(..) which declares a class that acts like a fixed-size array except it has a constructor that takes as many args as the array is big. So an array with 57 elements will have a constructor function with 57 parameters.

# define PRINT_CLASS_ARRAY_INIT_ELEM_( Z, N, D)     \
    BOOST_PP_CAT( _, N) ( BOOST_PP_CAT( init, N) )

# define PRINT_CLASS_ARRAY_MEMBER_DECL_( Z, N, D)   \
    element_type BOOST_PP_CAT( _, N) ;

# define DEFINE_CLASS_ARRAY(                        \
    CLASS_NAME,                                     \
    ELEM_COUNT,                                     \
    ELEM_TYPE,                                      \
    PARAM_TYPE,                                     \
    DEFAULT_VALUE                                   \
)                                                   \
    class CLASS_NAME                                \
    {                                               \
      public:                                       \
        typedef ELEM_TYPE element_type;             \
                                                    \
        CLASS_NAME                                  \
        ( BOOST_PP_ENUM_BINARY_PARAMS( ELEM_COUNT   \
           , PARAM_TYPE init                        \
           , = DEFAULT_VALUE BOOST_PP_INTERCEPT     \
        ) )                                         \
          : BOOST_PP_ENUM( ELEM_COUNT               \
             , PRINT_CLASS_ARRAY_INIT_ELEM_         \
             , ~                                    \
            )                                       \
          { }                                       \
                                                    \
      public:                                       \
        BOOST_PP_REPEAT( ELEM_COUNT                 \
         , PRINT_CLASS_ARRAY_MEMBER_DECL_           \
         , ~                                        \
        )                                           \
    } /* end of macro DEFINE_CLASS_ARRAY(..)       */

Here is how you might use the above macro to define a class that acts like an array of 5 integers.

// Define the class 
DEFINE_CLASS_ARRAY(
    five_ints_class, 5, int, const int&, 3);

// Same size as an array of 5 ints.
BOOST_STATIC_ASSERT(
    sizeof( five_ints_class) == sizeof( int[ 5 ]));

five_ints_class five_ints_0;
five_ints_class five_ints_1( 0);

five_ints_class five_ints_2( 0, 1);
five_ints_class five_ints_3( 0, 1, 2);

five_ints_class five_ints_4( 0, 1, 2, 3);
five_ints_class five_ints_5( 0, 1, 2, 3, 4);

// Too many args:
// five_ints_class five_ints_6( 0, 1, 2, 3, 4, 5);

// Cannot init with pod because it has a ctor:
// five_ints_class from_pod = { 1,2,3,4,5 };

This is just a quick hack and could be improved to (partly) mimic a standard container with additional typedefs, operators, methods, and associated iterators.

These array classes have no virtuals, no supertype, and no members besides the array elements. The resulting class is the same size as a raw array, and you could cautiously cast between the two types.

This defines classes with ctors that have default parameter values, but you could easily leave the defaults off. Or you could define the constructor as a template method and get rid of PARAM_TYPE from the macro. Or you could assume PARAM_TYPE is const ELEM_TYPE&.

Next Page →