[boost] abs and swap -or- overloading vs. specialization.

From: Dave Abrahams (abrahams_at_[hidden])
Date: 1999-12-29 20:59:03

In generic programs, there are two ways to allow users to customize 
behaviors of called functions for their own types:

1. We can use overloading and rely on Koenig lookup to help select specific
implementations.
2. We can supply a function template and rely on the user to specialize it
for her own types.

Option 1 is intrusive. In a sense, we "claim" the name of the function we
are using in all namespaces.

For example, a generic function F which wants to use abs() on one of its
template arguments T "reserves" the functions abs(U) (where T is convertible
to U) in the namespace in which T is defined. The user must implement abs()
with the semantics expected by F. Furthermore, there had better not be a
version of abs(U2) (where T is convertible to U2) in F's namespace, or we
risk an ambiguity.

Option 2 is less intrusive, but it takes more work from both library
implementors and users. For example, to use std::swap() effectively, we must
remember to explicitly qualify references to swap with std::.

Why not just rely on Koenig lookup, you ask? See above: we have then
"reserved" the name swap() in the user's namespace. If the user had written
a function called swap() with unrelated semantics and was unlucky enough to
have the generic function compile, the problem might only show up at
runtime. To avoid the potential problems with Koenig lookup, we must
explicitly qualify our uses of swap with std:: (extra work for us).

Shouldn't we use the specialization in the user's namespace? Well, the user
can't specialize std::swap in their own namespace (the language rules
prevent it). This is where the extra work for the user occurs: she must
close her own namespace(s), open namespace std, and specialize there.

I've included a program below that you can use to experiment with this.

I'm not absolutely sure what the policy ought to be for generic code, though
I lean toward the high-labor, low-intrusiveness approach (option 2).

I think it's an open question whether option 2 can be applied effectively in
cases where there isn't a generalizable implementation for the function
(e.g., how would you write an abs that works for unsigned?) On the other
hand, the idea that there is a generalizable implementation might be an
illusion: how do you write swap for a class derived from boost::noncopyable?

// ---- A snippet of std -------
namespace std_ {
    // abs is just an overloaded function.
    int abs(int);

    // There's an abs template function for complex.
    template <class T>
    struct complex {};
    template <class T>
    complex<T> abs(complex<T> x) { return x; }

    // Here's the generalized swap.
    template <class T>
    void swap(T& a, T& b) { T tmp = b; b = a; a = tmp; }
}

// ------ A library (e.g. boost) --------
namespace lib {

    // template function
    template <class T>
    void g(T) {}

    // Note that this function REQUIRES that an abs has been
    // defined by the user for all user-defined Xs. In contrast,
    // it can use the generalized swap in std_:: for all Assignable
    // Xs (it also requires that X is assignable).
    template <class X>
    X f(X x, X& y)
    {
        // bring in std_::abs so that overloads for built-in types
        // (and std_::complex) will be found.
        using std_::abs;

        // Use Koenig lookup to select the right abs. Note that we
        // must ADVERTISE to the user that we depend on her to
        // overload abs properly in her own namespace.
        y = abs(x);

        // swap is a template function in std_. It might get specialized
        // (in std_::) by the user for her own types. We don't have
        // to advertise that we are using it, only that X must fulfill
        // its requirements (Assignable).
        std_::swap(x, y);

        // similarly, g is a template function in lib. It gets
        // specialized (in lib::) by the user.
        lib::g(x);
        return x;
    }
}

// ------- User Code --------
namespace user {
    struct X {};
    // Provide abs for X.
    X abs(X);

    // This function is unrelated to lib::g(). The user thought she
    // was safe because it's in a separate namespace. She's only safe
    // because we write qualified lib::g() in lib::f().
    template <class T>
    void g(T) {}
}

namespace std_ {
    // specialize std_::swap for user::X.
    template <>
    void swap(const user::X&, const user::X&) {} // all X's identical!
}

namespace lib {
    // specialize lib::g for user::X.
    template <>
    void g(user::X) {}
}

namespace user {
    int z1 = 0, z2 = 3;
    int z = lib::f(z1, z2);

    X x1, x2;
    X y = lib::f(x1, x2);
}