Boost logo

Boost :

From: Paul Mensonides (pmenso57_at_[hidden])
Date: 2006-09-01 07:10:02

Larry Evans wrote:
> On 08/31/2006 04:05 PM, Paul Mensonides wrote:

> > Given the above, you could solve (i.e. avoid) the combinatorial
> > problem by linearizing the input.
> Paul, could explain what's meant by "linearizing the input"? I'm
> unfamiliar with that phrase :(

Bad wording on my part. What I meant was converting the problem from
combinatorial to linear complexity (in relation to the number of
required template functions) by modifying the input in such a way that
the combinatorial problem is avoided. The rules that we have now for
overloading and template argument deduction disallow the following:

template<class T> void f(T&);

int main(void) {
return 0;

The problem here is that the T cannot be deduced as "const T" which
would allow the binding of a temporary to a reference. However, if the
argument is *already* a reference to const--instead of a temporary--then
the T will be bound to (e.g.) const int. For example:

int main(void) {
f((const int&)123);
return 0;

This one isn't a problem. The T will bind to const int and we avoid the
temporary problem.

What this means is that we can make the problem linear by restricting
the input. We don't need every possible combination of cv-qualifiers on
various parameters, such as (ignoring volatile):

template<class T0, class T1> void f(T0&, T1&);
template<class T0, class T1> void f(T0&, const T1&);
template<class T0, class T1> void f(const T0&, T1&);
template<class T0, class T1> void f(const T0&, const T1&);

Instead, we only need

template<class T0, class T1> void f(T0&, T1&);

iff the arguments are guaranteed not to be temporaries--namely because
the T0 and T1 in the parameter types will be deduced as cv-qualified as

Given the above, we need a way to cause each argument to preserve it's
cv-qualification, yet have temporaries be "promoted" to reference to
const. We can do that with overloading similar to what we were doing
with the combinatorial overloads--but this time it isn't combinatorial
because it is only with one argument at a time--it is linear, but along
a different axis (namely cv-qualifications as opposed to arity). Simple
way to accomplish that is with identity functions for every possible

template<class T> T& identity(T&);
template<class T> const T& identity(const T&);
template<class T> volatile T& identity(volatile T&);
template<class T> const volatile T& identity(const volatile T&);

If the identity function is applied to a temporary, it has the same
effect as the c-style cast used above:

int main(void) {
return 0;

The advantages of using something like identity are that we don't have
to manually try to deduce the type in order to do the cast and that
every other kind of argument passes through preserving cv-qualification.

Ultimately then, we can avoid the combinatorial forwarding problem by
simply applying identity to each argument before the argument gets the
our function(s). E.g.

template<class T0, class T1> void g(T0&, T1&);

int main(void) {
int x = 0;
const int y = 0;
g(identity(x), identity(y));
g(identity(123), identity(x));
// etc.
return 0;

Though this works, it is obviously not a complete solution because it is
flagrantly intrusive on the client code. However, the problem is solved
successfully avoided if we can find a way to automatically add the
identity calls to each argument. That can be done with a macro interface
instead of a function.

The macro interface won't be perfect. You have the usual all-caps
library-prefixed macro name, and without variadic macros (C99 + C++0x)
you have to specify either the number of arguments or use a different
invocation syntax. E.g.

G(2)(x, y)
G(2)(123, x)



With variadics, you can make it...

G(x, y)
G(123, x)

...and the interface ultimately becomes something like:

smart_ptr<T>::MAKE_SMART_PTR(x, y)
smart_ptr<T>::MAKE_SMART_PTR(123, x)

I don't know if that is better than just dealing with the combinatorial
problem (for a low maximum arity) or not. However, it is better, IMO,
than having to actually specify the signature at the call site.

> I'm afraid I don't understand. Could you provide some code, maybe
> for just 2 to 3 parameters, which is like the ctor_template_test.cpp
> code in the vault. IOW, show:

> Or could you provide some other code or sketch of
> code to make it a little clearer?

Say you have a smart_ptr implemented something like:

template<class T> class smart_ptr {
struct data {
data(void) : rc(1), x() { }
template<class T0> data(T0& p0) : rc(1), x(p0) { }
template<class T0, class T1> data(T0& p0, T1& p1) : rc(1), x(p0, p1) { }
template<class T0, class T1, class T2> data(T0& p0, T1& p1, T2& p2) :
rc(1), x(p0, p1, p2) { }
// etc.
unsigned long rc;
T x;
} * p_;
smart_ptr(data* p) : p_(p) { };
// ...
static smart_ptr make(void) { return new data(); }
template<class T0> static smart_ptr make(T0& p0) { return new data(p0); }
template<class T0> static smart_ptr make(T0& p0, T1& p1) { return new
data(p0, p1); }
template<class T0> static smart_ptr make(T0& p0, T1& p1, T2& p2) {
return new data(p0, p1, p2); }
// etc.

template<class T> inline T& identity(T& x) { return x; }
template<class T> inline const T& identity(const T& x) { return x; }
template<class T> inline volatile T& identity(volatile T& x) { return x; }
template<class T> inline const volatile T& identity(const volatile T& x)
{ return x; }


#define MAKE_SMART_PTR_0() make()
#define MAKE_SMART_PTR_1(a) make(identity(a))
#define MAKE_SMART_PTR_2(a, b) make(identity(a), identity(b))
#define MAKE_SMART_PTR_3(a, b, c) make(identity(a), identity(b),
// etc.

Usage becomes:

smart_ptr<XYZ> p = smart_ptr<XYZ>::MAKE_SMART_PTR(x, y, z);

Another way that you could do it is will chained invocations that each
take one parameter:

smart_ptr<XYZ> p = smart_ptr<XYZ>::make(x)(y)(z);

This last is doable, but would be less efficient.

Of course, the real solution is language support. Rvalue references,
AFAICT, take the problem from a combinatorial function of arity and
cv-qualification to just a linear function of arity. Variadic templates
(if specified in the right way) + rvalue references take the problem
from a linear function of arity to a constant function--that returns two
(nullary and non-nullary).

Paul Mensonides

Boost list run by bdawes at, gregod at, cpdaniel at, john at