5

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());
1
  • 1
    After some more thought, I updated my answer. Technically, you can do it in 2 ways, as you discovered yourself. I don't think there is any technical difference (i.e. I could not come up with an example where one approach would select a different function than the other approach.) However, delegation of a function template to a class template function object is more regular and easier to maintain. That's the best reason that I could come up with anyway :-) Aug 17, 2013 at 17:51

3 Answers 3

3
+50

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.

6
  • The question was about overloaded function templates, not function template specializations.
    – aschepler
    Jun 21, 2013 at 12:24
  • My question is actually about the inner class template, Can I just use function overload like in the second excerpt of code, and if I can, why it is not used in the STL implementation.
    – Joey.Z
    Jun 21, 2013 at 12:24
  • Your code works in this particular case. But as the linked article about function template specialization shows, in general it is full of very subtle surprises. Experienced programmers like the implementers of the g++ Standard Library try to avoid this by delegating to a class template that they can partially specialize. Jun 21, 2013 at 12:30
  • @TemplateRex Yes, I am reading that, it's a good reference. up!
    – Joey.Z
    Jun 21, 2013 at 12:45
  • @aschepler the point is doing it the g++ way is idiomatic, and while the proposed overloads would work in this case, you could easily get into function specialization territory if another developer down the road decided to add one "just to take care of the special case of int*" e.g. Jun 21, 2013 at 12:52
2

This is mostly a matter of preference. Any compile-time dispatching for a function call that can be done with class template partial specializations, you could also do with function template overloads, and vice versa. In fact, the Standard defines the partial ordering on class template partial specializations by referring to the partial ordering on overloaded function templates (14.5.5.2).

That said, sometimes you want a compile-time choice to control something other than or more than just which single function to call. Class templates can have any number of member functions and member typedefs, not just the one function. And prior to C++11's constexpr, a static class member was by far the best way to set up a constant expression dependent on template parameters, so that its specializations can be used as template parameters, array bounds, and so on.

0

I would add a case your solution has "problem"

template <class T> void foo(T t) { std::cout << "foo<T>" << std::endl; }   // (a)
template <class T> void foo(T* t) { std::cout << "foo<T*>" << std::endl; } // (b)

void bar() {
    int i = 0;

    foo(i);          // call (a) f<int>(int)
    foo(&i);         // call (b) f<int>(int*)
    foo<int*>(&i);   // call (a) f<int*>(int*) and not (b)
}

So in your case if I call

copy_dispatch<char*, char*>

I don't get the specialization as it is in the STL.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.