|
|
9.4. Structure SelectionYou already know how to use metafunctions to affect the types of individual class members:
template <class T>
struct X
{
static int m1 = metafunction1<T>::type::value;
typedef typename metafunction2<T>::type m2;
int m4(typename metafunction3<T>::type p);
...
};
In this example, metaprograms are computing the value of m1, the type m2, and the parameter type of m4. Suppose, however, that we wanted to control whether m2 is present at all in a given specialization of X? The approach used above allows us to manage the details of a given class member, but fundamental structural changes to the class demand a more powerful technique. Structure selection involves pushing the variable part of the class structure into public base classes or base class templates and using a metaprogram to choose among them. To see how it works, let's fix a problem in compose_fg, which is currently defined to be:
template <class R, class F, class G>
class compose_fg
{
public:
compose_fg(F const& f, G const& g)
: f(f), g(g)
{}
template <class T>
R operator()(T const& x) const
{
return f(g(x));
}
private:
F f;
G g;
};
You may be wondering what sort of problem there could possibly be: compose_fg is almost so simple that we can see its correctness at a glance. Furthermore, it works! The problem isn't one of correctness, but of efficiency. In our earlier example, we generated an object of type:
compose_fg<float,std::negate<float>,float(*)(float)>
so F is std::negate<float>. In most implementations, std::negate's only member is its function-call operator:
T operator()(const T& x) const { return -x; }
In other words, it is an empty class. The C++ standard, though, says that every one of compose_fg's data members must occupy at least one byte. In a typical class layout scheme,[3] its first byte will be devoted to f, even though specializations of negate have no data members. There will follow a few bytes of padding (say three), as required to reach the appropriate memory alignment for a function pointer, and the memory for g (say four bytes) would follow thereafter, yielding an object of eight bytes. If we could do away with the storage for f altogether, the size would drop to four bytes. If G also turned out to be an empty class, the total size of the compose_fg object could, theoretically, be as small as one byte. We can't do better than that; the rules say even an empty class must have nonzero size.
One way to eliminate storage for empty classes might be to detect them (using the boost::is_empty type trait described in Chapter 2), and simply omit the corresponding data members. There are a few problems with that approach, however.
Fortunately, there's a better solution. Compilers may implement an Empty Base Optimization (EBO), which allows an empty base class to be placed at the same address as any other subobject, as long as no two distinct subobjects of the same type share an address. For example,
compose_fg<float,std::negate<float>,float(*)(float)>
might have had ideal size if compose_fg had been written this way:
template <class R, class F, class G>
class compose_fg : F // if empty, F may overlap with g
{
public:
typedef R result_type;
compose_fg(F const& f, G const& g)
: F(f), g(g) // initialize base with f
{}
template <class T>
R operator()(T const& x) const
{
F const& f = *this; // retrieve F subobject
return f(g(x));
}
private:
G g;
};
Naturally, we can't use that structure for all compose_fg specializations: If F were a function pointer, we'd get a compilation error because function pointers aren't legal base classes. Furthermore, we don't want to use that structure in all cases: When G is empty but F is not, we want to derive compose_fg<R,F,G> from G instead. The need for structural variation points to structure selection as the technique of choice. The first step in applying structure selection is to delegate control over the variable part of the class structure. In this case, the way F and G are stored varies, so we can write:
// base class template to be defined later
template <class F, bool F_empty, class G, bool G_empty>
class storage;
template <class R, class F, class G>
class compose_fg
: storage<
F,boost::is_empty<F>::value
, G,boost::is_empty<G>::value
>{
typedef
storage<
F,boost::is_empty<F>::value
, G,boost::is_empty<G>::value
> base;
public:
compose_fg(F const& f, G const& g)
: base(f, g)
{}
template <class T>
R operator()(T const& x) const
{
F const& f = this->get_f();
G const& g = this->get_g();
return f(g(x));
}
};
Now we only need to write storage so that it has the right structure for each of four combinations of F_empty and G_empty, and exposes access to the stored F and G via get_f and get_g members:[4]
template <class F, class G>
class storage<F,false,G,false> // neither F nor G is empty
{
protected:
storage(F const& f, G const& g)
: f(f), g(g)
{}
F const& get_f() { return f; }
G const& get_g() { return g; }
private:
F f;
G g;
};
template <class F, class G>
class storage<F,false,G,true> // G is empty
: private G
{
protected:
storage(F const& f, G const& g)
: G(g), f(f)
{}
F const& get_f() { return f; }
G const& get_g() { return *this; }
private:
F f;
};
template <class F, class G>
class storage<F,true,G,false> // F is empty
: private F
{
protected:
storage(F const& f, G const& g)
: F(f), g(g)
{}
F const& get_f() { return *this; }
G const& get_g() { return g; }
private:
G g;
};
template <class F, class G>
class storage<F,true,G,true> // F and G are both empty
: private F, private G
{
protected:
storage(F const& f, G const& g)
: F(f), G(g)
{}
F const& get_f() { return *this; }
G const& get_g() { return *this; }
};
Since the EBO is optional, there are no guarantees that any of this will make a difference. That said, by selecting among different bases, we've at least given the compiler the opportunity to optimize away the storage for empty subobjects, and most of them will take advantage of it (see the exercises for more information). You might also want to look at the Boost compressed_pair template [CDHM01], which implements a generalization of the EBO pattern we've used here. |
|
|