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>).

Improved const_cast<T>(..) definition in C++

A few days ago I talked about how to define const_cast<T>(..) as a templated function. My solution could not cast the const out of a data-member pointer however, because I did not have the type traits functions needed for the job.

But yesterday I posted code to supply type-traits style functions to manipulate data-member pointers which I can use to improve my implementation of const_cast<T>. This post is a listing of that improved implementation, which is called const_cast_x<T>.

I start with the type-traits template functions.

# include <boost/type_traits.hpp>
using boost::is_same;
using boost::is_pointer;
using boost::is_reference;
using boost::is_member_object_pointer;
using boost::add_const;
using boost::add_volatile;
using boost::add_cv;
using boost::add_pointer;
using boost::add_reference;
using boost::remove_const;
using boost::remove_volatile;
using boost::remove_cv;
using boost::remove_pointer;
using boost::remove_reference;

using boost::mpl::identity;
using boost::mpl::if_;

I also need the following template functions from my previous post.

The improved const_cast_x<T> follows. Most of it is just copied from my earlier post. I have identified the changed parts in code comments, and I have taken out all the BOOST_MPL_ASSERT(..) and other explanatory and testing code in order to keep it brief. There are only two new template functions and two functions that have changed from the earlier version.

// ================================================
// strip_out_cv<T>

// strip_out_member_obj_ptr_cv<T>
// new, not in earlier code listing
template< typename T >
struct strip_out_member_obj_ptr_cv
: if_<
    is_member_object_pointer< T >,
    remove_member_object_pointer_cv< T >,
    identity< T >
  >::type
{ };

// strip_out_cv_no_ref<T>
// no change from earlier code listing
template< typename T, bool IS_PTR = is_pointer< T >::value >
struct strip_out_cv_no_ref
: add_pointer<
    typename strip_out_cv_no_ref<
      // remove_pointer<T> will remove top-level
      // const and volatile if they are present.
      typename remove_pointer<
        T
      >::type
    >::type
  >
{ };

// strip_out_cv_no_ref<T> specialization
// changed from earlier code listing
template< typename T >
struct strip_out_cv_no_ref< T, false >
: strip_out_member_obj_ptr_cv<
    typename remove_cv< T >::type
  >
{ };

// strip_out_cv_maybe_ref<T>
// no change from earlier code listing
template< typename T, bool IS_REF = is_reference< T >::value >
struct strip_out_cv_maybe_ref
: add_reference<
    typename strip_out_cv_no_ref<
      typename remove_reference<
        T
      >::type
    >::type
  >
{ };

// strip_out_cv_maybe_ref<T> specialization
// no change from earlier code listing
template< typename T >
struct strip_out_cv_maybe_ref< T, false >
: strip_out_cv_no_ref< T >
{ };

// strip_out_cv<T>
// no change from earlier code listing
template< typename T >
struct strip_out_cv
: strip_out_cv_maybe_ref< T >
{ };

// ================================================
// load_with_cv<T>

// load_with_member_obj_ptr_cv<T>
// new, not in earlier code listing
template< typename T >
struct load_with_member_obj_ptr_cv
: if_<
    is_member_object_pointer< T >,
    add_member_object_pointer_cv< T >,
    identity< T >
  >::type
{ };

// load_with_cv_no_ref<T>
// no change from earlier code listing
template< typename T, bool IS_PTR = is_pointer< T >::value >
struct load_with_cv_no_ref
: add_cv<
    typename add_pointer<
      typename load_with_cv_no_ref<
        typename remove_pointer<
          T
        >::type
      >::type
    >::type
  >
{ };

// load_with_cv_no_ref<T> specialization
// changed from earlier code listing
template< typename T >
struct load_with_cv_no_ref< T, false >
: add_cv<
    typename load_with_member_obj_ptr_cv< T >::type
  >
{ };

// load_with_cv_maybe_ref<T>
// no change from earlier code listing
template< typename T, bool IS_REF = is_reference< T >::value >
struct load_with_cv_maybe_ref
: add_reference<
    typename load_with_cv_no_ref<
      typename remove_reference<
        T
      >::type
    >::type
  >
{ };

// load_with_cv_maybe_ref<T> specialization
// no change from earlier code listing
template< typename T >
struct load_with_cv_maybe_ref< T, false >
: load_with_cv_no_ref< T >
{ };

// load_with_cv<T>
// no change from earlier code listing
template< typename T >
struct load_with_cv
: load_with_cv_maybe_ref< T >
{ };

// ================================================
// const_cast_x<T>

// const_cast_x<T>
// no change from earlier code listing
template< typename TRG >
inline
TRG
const_cast_x( typename load_with_cv< TRG >::type a)
{
  return (typename strip_out_cv< TRG >::type) a;
}

Finally, here is some code that confirms that this improved const_cast_x<T> now works like const_cast<T> when casting data-member pointers.

// Define type a_class.
class a_class { public: int a_data_member; };

// Define non-const data-member pointer type.
typedef
  int a_class::*
  ptr_non_c_member_obj_type; /* new type name */

// Define const data-member pointer type.
typedef
  const int a_class::*
  ptr_const_member_obj_type; /* new type name */

// Get a pointer to a non-const member object.
ptr_non_c_member_obj_type
  p_non_c_memb =
    & a_class::a_data_member;

// You can assign a pointer to a non-const
// to a pointer to a const member object
// without casting.
ptr_const_member_obj_type
  p_const_memb =
    p_non_c_memb;

// You have to cast to assign a const
// to a non-const member-object pointer.
ptr_non_c_member_obj_type
  p_non_c_memb2 =
    const_cast<
      ptr_non_c_member_obj_type
    >( p_const_memb);

// const_cast_x<T> can also perform
// this cast with the modifications
// described above.
ptr_non_c_member_obj_type
  p_non_c_memb3 =
    const_cast_x<
      ptr_non_c_member_obj_type
    >( p_const_memb);

In closing, let me reiterate that it should be a goal to define const_cast<T> and the other primitive casting functions in C++. If the casts cannot be expressed as functions then we have found an expressive weakness in C++. And the functional definitions will give us an exact definition for these casts based on the C-style cast.

← Previous PageNext Page →