Partial template specialization of free functions - best practices

Question

As most C++ programmers should know, partial template specialization of free functions is disallowed. For example, the following is illegal C++:

template <class T, int N>
T mul(const T& x) { return x * N; }

template <class T>
T mul<T, 0>(const T& x) { return T(0); }

// error: function template partial specialization ‘mul<T, 0>’ is not allowed

However, partial template specialization of classes/structs is allowed, and can be exploited to mimic the functionality of partial template specialization of free functions. For example, the target objective in the last example can be achieved by using:

template <class T, int N>
struct mul_impl
{
    static T fun(const T& x) { return x * N; }
};

template <class T>
struct mul_impl<T, 0>
{
    static T fun(const T& x) { return T(0); }
};

template <class T, int N>
T mul(const T& x)
{
    return mul_impl<T, N>::fun(x);
}

It's more bulky and less concise, but it gets the job done -- and as far as users of mul are concerned, they get the desired partial specialization.

---

My questions is: when writing templated free functions (that are intended to be used by others), should you automatically delegate the implementation to a static method function of a class, so that users of your library may implement partial specializations at will, or do you just write the templated function the normal way, and live with the fact that people won't be able to specialize them?

Rash

I think it depends. In your case you call it like fun<U, N>(u), so you cannot overload (N does not appear anyhere in the parameter). But i think if "overloading" is possible, it's the preferred way. Excellent example is std::swap or std::begin or std::end (where the latter two are C++0x functions). Notice that Sutter's article was written 9 years ago. Not sure whether he still recommends to do it the "delegate to class" way. And i think it doesn't scale nicely: Won't work with ADL - you will have to fiddle with all sort of namespaces and specialize their templates. No nice – Mutt

Answer 1

As litb says, ADL is superior where it can work, which is basically whenever the template parameters can be deduced from the call parameters:

#include <iostream>

namespace arithmetic {
    template <class T, class S>
    T mul(const T& x, const S& y) { return x * y; }
}

namespace ns {
    class Identity {};

    // this is how we write a special mul
    template <class T>
    T mul(const T& x, const Identity&) {
        std::cout << "ADL works!\n";
        return x;
    }

    // this is just for illustration, so that the default mul compiles
    int operator*(int x, const Identity&) {
        std::cout << "No ADL!\n";
        return x;
    }
}

int main() {
    using arithmetic::mul;
    std::cout << mul(3, ns::Identity()) << "\n";
    std::cout << arithmetic::mul(5, ns::Identity());
}

Output:

ADL works!
3
No ADL!
5

Overloading+ADL achieves what you would have achieved by partially specializing the function template arithmetic::mul for S = ns::Identity. But it does rely on the caller to call it in a way which allows ADL, which is why you never call std::swap explicitly.

So the question is, what do you expect users of your library to have to partially specialize your function templates for? If they're going to specialize them for types (as is normally the case with algorithm templates), use ADL. If they're going to specialize them for integer template parameters, as in your example, then I guess you have to delegate to a class. But I don't normally expect a third party to define what multiplication by 3 should do - my library will do all the integers. I could reasonably expect a third party to define what multiplication by an octonion will do.

Come to think of it, exponentiation might have been a better example for me to use, since my arithmetic::mul is confusingly similar to operator*, so there's no actual need to specialize mul in my example. Then I'd specialize/ADL-overload for the first parameter, since "Identity to the power of anything is Identity". Hopefully you get the idea, though.

I think there is a downside to ADL - it effectively flattens namespaces. If I want to use ADL to "implement" both arithmetic::sub and sandwich::sub for my class, then I could be in trouble. I don't know what the experts have to say about that.

By which I mean:

namespace arithmetic {
    // subtraction, returns the difference of lhs and rhs
    template<typename T>
    const T sub(const T&lhs, const T&rhs) { return lhs - rhs; }
}

namespace sandwich {
    // sandwich factory, returns a baguette containing lhs and rhs
    template<typename SandwichFilling>
    const Baguette sub(const SandwichFilling&lhs, const SandwichFilling&rhs) { 
      // does something or other 
    }
}

Now, I have a type ns::HeapOfHam. I want to take advantage of std::swap-style ADL to write my own implementation of arithmetic::sub:

namespace ns {
    HeapOfHam sub(const HeapOfHam &lhs, const HeapOfHam &rhs) {
        assert(lhs.size >= rhs.size && "No such thing as negative ham!");
        return HeapOfHam(lhs.size - rhs.size);
    }
}

I also want to take advantage of std::swap-style ADL to write my own implementation of sandwich::sub:

namespace ns {
    const sandwich::Baguette sub(const HeapOfHam &lhs, const HeapOfHam &rhs) {
        // create a baguette, and put *two* heaps of ham in it, more efficiently
        // than the default implementation could because of some special
        // property of heaps of ham.
    }
}

Hang on a minute. I can't do that, can I? Two different functions in different namespaces with the same parameters and different return types: not usually a problem, that's what namespaces are for. But I can't ADL-ify them both. Possibly I'm missing something really obvious.

Btw, in this case I could just fully specialize each of arithmetic::sub and sandwich::sub. Callers would using one or the other, and get the right function. The original question talks about partial specialization, though, so can we pretend that specialization is not an option, without me actually making HeapOfHam a class template?

Dappled

Not sure about the sub issue for flattened namespaces. I think one would have the same problem if sub would be a member function. What would the operand of those two subs be? If sandwich: I can't imagine how we could arithmetically sub a sandwich, so a sandwich defined in arithmetic seems unlikely. If MyInt: Since implicit conversions are effectively not considered (if sandwich has a (MyInt) (for the number of cheese plates?) ctor and we call sub(a, b), we won't find sub in sandwich of course), i doesn't look like a problem at first. I would be glad if you elaborated on this. – Mutt

@litb: I don't quite follow you, so I'll edit and we'll see if we're talking about the same thing. – Dappled

@lit: done. If you don't know the answer, maybe I'll ask a question. – Dappled

@Steve ah i see now. I think you should go with adding a question about this, it's interesting. I think one way to tackle this is to ask whether it's a case for ADL at all. I see ADL as some kind of interface to a class: A heap of ham will be concerned subbing a baguette - which does not sound like it should be part of the heap of ham's interface. While things like swapping two hams or getting the size of a ham would be fine candidates for interface functions of a heap of ham. – Mutt

@litb: I'll try to come up with a better example, then. Supposing that "swap" were ambiguous in English, and as well as meaning "exchange two values" (std::swap), it also meant "perform a convolution of two objects" (calculus::swap). I'd have the same problem that I can't ADL-overload both for HeapOfHam. If there's no solution then maybe namespaces other than std shouldn't use this trick for overloading algorithms, for fear of name conflict. That leaves delegation to a class, as in the questioner's code. – Dappled

Maybe a technique for ADL for factories is to pass an identity object, like: sub(identity<KindOfSub>(), part1, part2), that way ADL will search in namespaces of KindOfSub and of part1 and part2. So for factories, the first parameter designates the type of what to create. Different kind of subs could have different kind of techniques of making the sandwich, and the factory would be disambiguated from pure operational functions of part1 and part2 by the first identity parameter. – Mutt

Thinking more, this may just be the same problem as member function names. If Concept1 defines an allowed expression requiring a member function renuberate(void), and Concept2 also defines a member function renuberate(void) which does something different, then it is not possible for HeapOfHam to implement both concepts. This is worse if the author of HeapOfHam has never heard of namespace calculus. He implements non-member swap meaning std::swap, but someone does using calculus::swap; swap(heap,heap);, thinking to get at worst the default implementation of calculus::swap. Wrong. – Dappled

So, it's obviously wrong for calculus to define a function "swap" where types are expected to use this technique, because everybody knows that std::swap exists and would conflict. But if the ambiguous verb isn't in namespace std, but in two unrelated libraries that both can be used with my class, I'm stuck. With delegation to a class, I wouldn't be stuck, I'd just implement two class partial specializations. – Dappled

Answer 2

If you are writing a library to be use elsewhere or by other people do the struct/class thing. It is more code but the users of your library (possibly a future you!) will thank you. IF this is one use code, the loss of partial specialization will not hurt you.

Dependence