c++stltemplate-specializationgeneric-programmingsgi

Whether to choose an overload of template function or a partial specialization of a functor(function object)


The following is an excerpt of STL implementation of g++ (the sgi version of STL). I want to know why they use partial specialization instead of function overload.

template <class InputIterator, class OutputIterator>
struct __copy_dispatch
{
  OutputIterator operator()(InputIterator first, InputIterator last,
                            OutputIterator result) {
    return __copy(first, last, result, iterator_category(first));
  }
};

//If the inputiterator and the outputiterator is all type T
//This is a partial specialization of the generalized version
template <class T>
struct __copy_dispatch<T*, T*>//-----------------------(1)
{
  T* operator()(T* first, T* last, T* result) {
    typedef typename __type_traits<T>::has_trivial_assignment_operator t; 
    return __copy_t(first, last, result, t());
  }
};

//Strictly speaking this is a partial specialization of the last template function
template <class T>
struct __copy_dispatch<const T*, T*>//-----------------(2)
{
  T* operator()(const T* first, const T* last, T* result) {
    typedef typename __type_traits<T>::has_trivial_assignment_operator t; 
    return __copy_t(first, last, result, t());
  }
};


//The generalized version of copy
template <class InputIterator, class OutputIterator>
inline OutputIterator copy(InputIterator first, InputIterator last,
                           OutputIterator result)
{
  return __copy_dispatch<InputIterator,OutputIterator>()(first, last, result);
}

//A overload version
inline char* copy(const char* first, const char* last, char* result) {
  memmove(result, first, last - first);
  return result + (last - first);
}

What if I use an overload version like:

#include <iostream>

using namespace std;


template <class InputIterator, class OutputIterator>
OutputIterator copy_dispatch(InputIterator first, InputIterator last,
                            OutputIterator result) {
    cout << "now in first" << endl;
    return result;
}
template <class T>
T* copy_dispatch(T* first, T* last, T* result) {
    cout << "now in second" << endl;
    return 0;
}
template <class T>
T* copy_dispatch(const T* first, const T* last, T* result) {
    cout << "now in third" << endl;
    return 0;
}

int main( void ) {
    int a[]={1,2,3,4,5,6};
    double b[] = {1.0,2.0,3.0,4.0,5.0,6.0};
    int c[]={0,0,0,0,0,0};
    int const d[]={0,0,0,0,0,0};

    copy_dispatch(a,a+6, b);
    copy_dispatch(a, a+6, c);
    copy_dispatch(d, d+6, c);

}

The output is:

now in first
now in second
now in third

Seems that it also works fine?

So is there any further reason to use a functor class with partial specialization instead of function overload

UPDATES

Here are some other excerpts from sgi implementation of STL:

//sgi 4.5
template<bool>
struct _Destroy_aux
{
  template<typename _ForwardIterator>
    static void
    __destroy(_ForwardIterator __first, _ForwardIterator __last)
    {
      for (; __first != __last; ++__first)
        std::_Destroy(&*__first);
    }
};
 
template<>
struct _Destroy_aux<true>
{
  template<typename _ForwardIterator>
    static void
    __destroy(_ForwardIterator, _ForwardIterator) { }
 
};

//in an old version of sgi 2.9 this is implemented with function overload
template <class ForwardIterator>
inline void
__destroy_aux(ForwardIterator first, ForwardIterator last, __false_type) {
  for ( ; first < last; ++first)
    destroy(&*first);
}
 
template <class ForwardIterator> 
inline void __destroy_aux(ForwardIterator, ForwardIterator, __true_type) {}
 
template <class ForwardIterator, class T>
inline void __destroy(ForwardIterator first, ForwardIterator last, T*) {
  typedef typename __type_traits<T>::has_trivial_destructor trivial_destructor;
  __destroy_aux(first, last, trivial_destructor());

Solution

  • Function template specializations do not participate in overload resolution, and class templates cannot deduce their arguments. This leads to the irregular pattern of function template overloads and ordinary functions as proxies for partial and explicit specializations.

    To combine the best of both worlds, most generic code does what you showed in your question

    //The generalized version of copy
    template <class InputIterator, class OutputIterator>
    inline OutputIterator copy(InputIterator first, InputIterator last,
                               OutputIterator result)
    {
      return __copy_dispatch<InputIterator,OutputIterator>()(first, last, result);
    }
    

    The top-level function template has its arguments deduced (which helps users write compact code), and the inner class template is specialized for the various special cases (that helps the compiler enable optimizations). The top-level function wrapper around the inner-level function object is inlined by every decent compiler, so there is no overhead.

    UPDATE: As you notice yourself, technically, you can achieve the same effects by replacing partial class template specialization with function template overloading, and explicit class template specialization with an ordinary function (instead of the allowed explicit function template specialization, which, as explained in Sutter's column, would not participate in overload resolution).

    Because the function template delegating to a class template function object behaves more regularly for both partial and explicit specializations, it is less subtle for library writers and users alike to maintain, or modify when required. It's the keep it simple principle.