C++ Core Guidelines: Programming at Compile Time with Type-Traits (The Second)

This is a cross-post from www.ModernesCpp.com.

The type-traits library supports type checks, type comparisons, and type modifications at compile time. Right! Today, I write about type modifications at compile time.

The Type-Traits Library

It may sound strange, but type modification is the domain of template metaprogramming and, therefore, for the type-traits library.

Type Modifications

Maybe, you are curious about what is possible at compile time. A lot! Here are the most exciting metafunctions:

// const-volatile modifications:
remove_const;
remove_volatile;
remove_cv;
add_const;
add_volatile;
add_cv;
   
// reference modifications:
remove_reference;
add_lvalue_reference;
add_rvalue_reference;

// sign modifications:
make_signed;
make_unsigned;
 
// pointer modifications:
remove_pointer;
add_pointer;
 
// other transformations:
decay;
enable_if;
conditional;
common_type;
underlying_type;

 To get an int from int or const int, you have to ask for the type with ::type.

int main(){

    
    std::is_same<int, std::remove_const<int>::type>::value;        // true
    std::is_same<int, std::remove_const<const int>::type>::value;  // true
  
}

Since C++14, you can just use _t to get the type such as for std::remove_const_t:

int main(){
    
    std::is_same<int, std::remove_const_t<int>>::value;        // true
    std::is_same<int, std::remove_const_t<const int>>::value;  // true
}

To get an idea of how useful this metafunctions from the type-traits library are, here a few use-cases. Here is std::move in one line.

• remove_reference: std::move and std::forward uses this function to remove the reference from its argument.

static_cast<std::remove_reference<decltype(arg)>::type&&>(arg);

• decay: std::thread applies std::decay to its arguments. Their usage includes the function f which a thread executes on its arguments args. Decay means that implicit conversions from array-to-pointer, function-to-pointer is performed and const/volatile qualifiers and references are removed.

std::invoke(decay_copy(std::forward<Function>(f)), 
            decay_copy(std::forward<Args>(args))...);

• enable_if: std::enable_if is a convenient way to use SFINAE. SFINAE stands for Substitution Failure Is Not An Error and applies during overload resolution of a function template. It means when substituting the template parameter fails, the specialisation is discarded from the overload set but cause no compiler error. std::enable_if is heavily used in std::tuple.
• conditional: std::conditional is the ternary operator at compile time.
• common_type: std::common_type determines the common type of a group of types.
• underlying_type: std::underlying_type determines the type of an enum.

Maybe, you are not convinced about the benefit of the type traits library. Let me end my story to the type-traits with there main goals: correctness and optimisation.

Correctness

Correctness means on one hand that you can use the type-traits libraries to implement concepts such as Integral, SignedIntegral, and UnsignedIntegral.

template <class T>
concept bool Integral() {
    return is_integral<T>::value;
}

template <class T>
concept bool SignedIntegral() {
    return Integral<T>() && is_signed<T>::value;
}

template <class T>
concept bool UnsignedIntegral() {
    return Integral<T>() && !SignedIntegral<T>();
} 

But it also means, that you can use them to make your algorithm safer. I used in my previous post More and More Safe the functions std::is_integral, std::conditional, std::common_type, and std::enable_if from the type-traits library to make the generic gcd algorithm successively safer.

To get a better idea of the post More and More Safe , here is the starting point of my generic gcd algorithm.

// gcd.cpp

#include <iostream>

template<typename T>
T gcd(T a, T b){
  if( b == 0 ){ return a; }
  else{
    return gcd(b, a % b);
  }
}

int main(){

  std::cout << std::endl;

  std::cout << "gcd(100, 10)= " <<  gcd(100, 10)  << std::endl;
  std::cout << "gcd(100, 33)= " << gcd(100, 33) << std::endl;
  std::cout << "gcd(100, 0)= " << gcd(100, 0)  << std::endl;

  std::cout << gcd(3.5, 4.0)<< std::endl;         // (1)
  std::cout << gcd("100", "10") << std::endl;     // (2)

  std::cout << gcd(100, 10L) << std::endl;        // (3)

  std::cout << std::endl;

} 

The output of the program shows two issues.

First, the usage of double (line 1) and the C-String (line 2) fails in the modulo operator. Second, the usage of an integer and a long (line 3) should work. Both issues can be elegantly solved with the type-traits library.

The type-traits is not only about correctness it's also about optimisation.

Optimisation

The key idea of the type-traits library is quite straightforward. The compiler analysis the used types and makes based on this analysis decision which code should run. In case of the algorithm std::copy, std::fill, or std::equal of the standard template library this means that the algorithm is applied to each element of the range one-by-one or on the entire memory. In the second case, C functions such as memcmp, memset, memcpy, or memmove are used which makes the algorithm faster. The small difference between memcpy and memmove is that memmove can deal with overlapping memory areas.

The following three code snippets from the GCC 6 implementation make one point clear: The checks of the type-traits library help to generate more optimised code.

// fill  
// Specialization: for char types we can use memset.                   
template<typename _Tp>
  inline typename
  __gnu_cxx::__enable_if<__is_byte<_Tp>::__value, void>::__type         // (1)
  __fill_a(_Tp* __first, _Tp* __last, const _Tp& __c)
  {
    const _Tp __tmp = __c;
    if (const size_t __len = __last - __first)
    __builtin_memset(__first, static_cast<unsigned char>(__tmp), __len);
  }

// copy

template<bool _IsMove, typename _II, typename _OI>
  inline _OI
  __copy_move_a(_II __first, _II __last, _OI __result)
  {
    typedef typename iterator_traits<_II>::value_type _ValueTypeI;
    typedef typename iterator_traits<_OI>::value_type _ValueTypeO;
    typedef typename iterator_traits<_II>::iterator_category _Category;
    const bool __simple = (__is_trivial(_ValueTypeI)                   // (2)
                           && __is_pointer<_II>::__value
                           && __is_pointer<_OI>::__value
                           && __are_same<_ValueTypeI, _ValueTypeO>::__value);

    return std::__copy_move<_IsMove, __simple,
  }

// lexicographical_compare

template<typename _II1, typename _II2>
  inline bool
  __lexicographical_compare_aux(_II1 __first1, _II1 __last1,
				  _II2 __first2, _II2 __last2)
  {
    typedef typename iterator_traits<_II1>::value_type _ValueType1;
    typedef typename iterator_traits<_II2>::value_type _ValueType2;
    const bool __simple =                                              // (3)
      (__is_byte<_ValueType1>::__value && __is_byte<_ValueType2>::__value
       && !__gnu_cxx::__numeric_traits<_ValueType1>::__is_signed
       && !__gnu_cxx::__numeric_traits<_ValueType2>::__is_signed
       && __is_pointer<_II1>::__value
       && __is_pointer<_II2>::__value);

  return std::__lexicographical_compare<__simple>::__lc(__first1, __last1,
                                                        __first2, __last2);
  }

The lines 1, 2, and 3 show that the type-traits library is used to generate more optimised code. My post Type-Traits: Performance Matters gives you more insight and has performance numbers with GCC and MSVC.

What's next?

With constexpr programming at compile time escapes its expert niche and becomes a mainstream technique. constexpr is programming at compile time with the typical C++-Syntax.