How do type_traits work?

If you have used Boost's type_traits header (or what's in C++ standard now) you might have wondered as to how these could have been implemented. If you haven't, type traits are like a jacket to any type that provide meta information about them without actually modifying the type/class itself. I will dig into the type_traits header of Boost to see how its done.

To demonstrate how it's used, lets assume you are writing a generic algorithm that works on a range of iterators. But your assumption it that it is an iterator to a numeric type, because you do a lot of numeric operation on them. So, here is how you write it.

<br /> template <typename Iterator><br /> typename iterator_traits<Iterator>::value_type total(Iterator begin_, Iterator end_)<br /> {<br />         //Check if the type this function is parameterized on is an arithmetic type.<br />         // If not we throw a compiler error.<br />         BOOST_STATIC_ASSERT(( typename is_arithmetic<typename iterator_traits<Iterator>::value_type>::value ));<br /> <br /> ..... rest of the code..... <br /> }<br />

This should throw a compiler error if any non-arithmetic type is passed to total(). Let's look at how is_arithmetic is implemented so as to see how it identifies arithmetic types from others.

Let's go down to: /usr/include/boost/type_traits.cpp. It includes a lot of internal headers from /usr/include/boost/ which have the same name as the trait class they provide.

If you go down to /usr/include/boost/type_traits/is_arithmetic.hpp

You see a lot of arcane pre-processor stuff, but the key thing to observe is:

<br /> ::boost::detail::is_arithmetic_impl<T>::value<br />

You might notice all internal details in Boost goes into an internal namespace.

So, is_arithmetic_impl<T> is another internal type trait class, which is wrapped around by the one we use.

It looks as follows:

<br /> template< typename T ><br /> struct is_arithmetic_impl<br /> {<br />     BOOST_STATIC_CONSTANT(bool, value =<br />         (::boost::type_traits::ice_or<<br />             ::boost::is_integral<T>::value,<br />             ::boost::is_float<T>::value<br />         >::value));<br /> };<br />

This structure again wraps around more type traits is_integral, is_float and does a compile time logical OR of the results. They mean that an arithmetic type should be integral or one of the float types.

Let's explore is_integral.hpp. It provides a traits class that returns a type true when parametrized on  intergal types and false for any other type. Basically, it tells whether a type is integral or not.

Again if you skim through all the pre-processor magic to come down to what they are implementing you see a set of declarations:

<br /> BOOST_TT_AUX_BOOL_TRAIT_DEF1(is_integral,T,false)<br />

followed by:

<br /> BOOST_TT_AUX_BOOL_TRAIT_CV_SPEC1(is_integral,unsigned char,true)<br /> BOOST_TT_AUX_BOOL_TRAIT_CV_SPEC1(is_integral,unsigned short,true)<br /> BOOST_TT_AUX_BOOL_TRAIT_CV_SPEC1(is_integral,unsigned int,true)<br /> BOOST_TT_AUX_BOOL_TRAIT_CV_SPEC1(is_integral,unsigned long,true)<br />

and many more other integral types.

If you look for what BOOST_TT_AUX_BOOL_TRAIT_CV_SPEC1 macro expands to in boost/type_traits/detail/bool_trait_def.hpp, it looks as follows:


<br /> #define BOOST_TT_AUX_BOOL_TRAIT_DEF1(trait,T,C) \<br /> template< typename T > struct trait \<br />     BOOST_TT_AUX_BOOL_C_BASE(C) \<br /> { \<br />     BOOST_TT_AUX_BOOL_TRAIT_VALUE_DECL(C) \<br />     BOOST_MPL_AUX_LAMBDA_SUPPORT(1,trait,(T)) \<br /> }; \<br />



To explain this in simple terms, all what's being done here is explicit template specialization


You can think of is_integral to be implemented as follows in simple terms:

<br /> template <typename T><br /> struct is_integral<br /> {<br />         enum{value=false};<br /> };<br /> <br /> template <><br /> struct is_integral<int><br /> {<br />         enum {value=true};<br /> };<br /> <br /> template <><br /> struct is_integral<long><br /> {<br />         enum {value = true};<br /> };<br />

.... and so on for each integral type. So, the value is going to be true for each type they specialize on, but false for all other types..

Why std::distance and std::advance?

Why use STL advance and distance given in <iterator> rather than hand crafting that code? The simple answers are:

• Why hand craft it when its already given to you?
• It can be more bug free than an average programmer's code.
• Why get into the nitty-gritties? You may rather want to concentrate on the problem at hand.

If all these aren't reason enough for you, here is the clincher: EFFICIENCY!

Let's look at each of them one by one.

std::distance()

Let's assume you are writing a generic function that takes in two iterators as the parameter and works on the range between them. If you are a beginner, your function would look something like this:

template <typename Iterator> foo(Iterator begin_, Iteraror end_)
{
      size_t dist = 0;

      while(begin_ !=   end_)
      {
            ++dist;
            ++begin_;
      }

      //Use dist in the rest of the code
      ...............
}

The time complexity of such an operation is O(n) for all categories of iterators passed to you.

If you are an advanced programmer and want to make a decision based on the iterator category, you will have to write helper functions overloaded on the different iterator categories and do a random access subtraction between the two iterators if it is a random access iterator. If not, you will iterate linearly through the range until the end. Something like...

template <typename Iterator>
typename iterator_traits<Iterator>::difference_type __mydistance(Iterator begin_, Iterator end_, random_access_iterator_tag)
{
        return end_ - begin_;
}

template <typename Iterator>
typename iterator_traits<Iterator>::difference_type __mydistance(Iterator begin_, Iterator end_, bidirectional_iterator_tag)
{
        typename iterator_traits<Iterator>::difference_type dist = 0;
        while(begin_ != end_)
        {
                ++begin_;
                ++dist;
        }

        return dist;
}


template <typename Iterator>
typename iterator_traits<Iterator>::difference_type mydistance(Iterator begin_, Iterator end_)
{

        return  __mydistance(begin_, end_, iterator_traits<Iterator>::iterator_category);

}


If your code looks something like the above, this is what std::distance gives you already.

If you go down to where the function is defined:
/usr/include/c++/4.4.2/bits/stl_iterator_base_funcs.h

It looks as follows:


template<typename _InputIterator>
    inline typename iterator_traits<_InputIterator>::difference_type
    distance(_InputIterator __first, _InputIterator __last)
    {
      // concept requirements -- taken care of in __distance
      return std::__distance(__first, __last,
                             std::__iterator_category(__first));
    }
If you observe, it calls std::__distance, a function for internal use, and passes the iterator category as the last parameter. This is called tagged dispatch. If you scroll around that file, you will notice multiple overloaded  __distance functions for different iterator categories.


The __distance function accepting random_access_iterator_tag is implemented as:
return __last - __first;

The __distance function accepting input_iterator_tag is implemented as:
      while (__first != __last)
        {
          ++__first;
          ++__n;
        }
      return __n;

How does boost::bind work?

If you are not already familiar with Boost::bind you may want to explore: http://www.boost.org/doc/libs/1_44_0/libs/bind/bind.html

To understand how bind works, I would write a simple example binder first and then start digging into boost::bind.

struct placeholder{};
placeholder _1;

template
struct mybinder_t
{
A ma;
T* mt;
R (T::*fn) (A);
R operator() ( )
{
return (mt->*fn)(ma);
}
};

template
mybinder_t mybind(R (T::*f)(A), T* t, A a, placeholder p)
{
mybinder_t tmp;
tmp.fn = f;
tmp.ma = a;
tmp.mt = t;

return tmp;
}


class IsItEvenObj
{
public:
bool is_even(int i)
{
return (i%2 == 0);
}
};

int main()
{
IsItEvenObj obj;
  mybinder_t<bool, IsItEvenObj, int> is_5_even = mybind(&IsItEvenObj::is_even, &obj, 5, _1);

cout << boolalpha ; cout << is_5_even() << endl; } 

When you used bind the first time,  you might have wondered what _1, _2 etc meant. These are placeholder variables of type boost::arg. So, you can declare variables with different names if you want. Boost bind uses placeholders as declare in /usr/include/boost/bind/placeholders.hpp. 


They are declared as follows: 

boost::arg<1> _1;
boost::arg<2> _2; 
boost::arg<3> _3;
boost::arg<4> _4;
boost::arg<5> _5;
boost::arg<6> _6;
boost::arg<7> _7;
boost::arg<8> _8;
boost::arg<9> _9;
There are 9 placeholders because bind supports upto 9 parameters to be bound. But what do these placeholders do? Let's dig into what boost::arg does. 

It is defined in /usr/include/boost/bind/arg.hpp It looks like: 

template< int I > struct arg
{     
arg()     {     }     
template< class T > arg( T const & /* t */ )     
 {
        // static assert I == is_placeholder<T>::value         
        typedef char T_must_be_placeholder[ I == is_placeholder<T>::value? 1: -1 ];
  } 
}; 


To be honest there is nothing much in there. And that is the fact, placeholders are only dummy variables. They are only there to help bind pick up the right overload. (I will explain what this means below) Having actually told what placeholders are, let's look into bind itself.

Let's go into /usr/include/boost/bind/bind.hpp. 

The first thing to note is:

// bind
#ifndef BOOST_BIND
#define BOOST_BIND bind
#endif 

So, bind is BOOST_BIND in here. Now let's look at the bind function itself. This is how boost::bind actually looks:

template<class R, class F>
    _bi::bind_t<R, F, _bi::list0>
    BOOST_BIND(F f)
{
    typedef _bi::list0 list_type;
    return _bi::bind_t<R, F, list_type> (f, list_type());
}

template<class R, class F, class A1>
    _bi::bind_t<R, F, typename _bi::list_av_1<A1>::type>
    BOOST_BIND(F f, A1 a1)
{
    typedef typename _bi::list_av_1<A1>::type list_type;
    return _bi::bind_t<R, F, list_type> (f, list_type(a1));
}

template<class R, class F, class A1, class A2>
    _bi::bind_t<R, F, typename _bi::list_av_2<A1, A2>::type>
    BOOST_BIND(F f, A1 a1, A2 a2)
{
    typedef typename _bi::list_av_2<A1, A2>::type list_type;
    return _bi::bind_t<R, F, list_type> (f, list_type(a1, a2));
}

So on upto 9 overloads:

template<class R, class F, class A1, class A2, class A3, class A4, class A5, class A6, class A7, class A8, class A9>
    _bi::bind_t<R, F, typename _bi::list_av_9<A1, A2, A3, A4, A5, A6, A7, A8, A9>::type>
    BOOST_BIND(F f, A1 a1, A2 a2, A3 a3, A4 a4, A5 a5, A6 a6, A7 a7, A8 a8, A9 a9)
{
    typedef typename _bi::list_av_9<A1, A2, A3, A4, A5, A6, A7, A8, A9>::type list_type;
    return _bi::bind_t<R, F, list_type>(f, list_type(a1, a2, a3, a4, a5, a6, a7, a8, a9));
}