[boost] more empty_member fun

From: Howard Hinnant (hinnant_at_[hidden])
Date: 1999-11-30 20:07:05

Ever since the empty_member thread started, I've been frustrated that I 
can't optimize function objects with this technique because they might be 
ordinary function pointers, and you can't derive from a function pointer.

Here's a concrete example:  A SortedVec that takes both an allocator, and 
a comparison object to sort by:

#include <memory>
#include <functional>

template <class T, class Compare = std::less<T>, class Allocator = 
std::allocator<T> >
class SortedVec
{
public:
        typedef unsigned long size_type;
        SortedVec(const Compare& comp = Compare(), const Allocator& a = 
Allocator())
                : comp_(comp, 0), alloc_(a, 0) {}
private:
        T* data_;
        empty_member<Compare, size_type> comp_;  // member = size
                size_type& sz()       {return comp_.member;}
                size_type  sz() const {return comp_.member;}
        empty_member<Allocator, size_type> alloc_;  // member = capacity
                size_type& cap()       {return alloc_.member;}
                size_type  cap() const {return alloc_.member;}
};

Here I've wishfully optimized the Compare object with empty_member.  99% 
of the time this will work well.  Most people if they don't use 
std::less, will use another function object.  But someone will try:

bool
comp(int x, int y)
{
        return x > y;
}

typedef bool (*Comp)(int, int);

#include <iostream>

int main()
{
        SortedVec<int> a;
        SortedVec<int, Comp> b(comp);
        std::cout << sizeof(a) << '\n' << sizeof(b) << '\n';
}

The SortedVec<int, Comp> won't compile because of the empty member 
optimization.  Really irritating!

How about specializing empty_member so that the first member can be 
either a class or a pod?  We would need to use a type_traits class (or 
something) to determine if the first member is a pod or not.  For 
purposes of discussion, I've lumped this into call_traits because it was 
handy, but that's not where I think it should go.

Might look something like:

    template<typename PossiblyEmptyBase, typename NonEmptyMember,
         bool FirstPod = call_traits<T1>::is_pod>
    struct empty_member;

    template<typename PossiblyEmptyBase, typename NonEmptyMember>
    struct empty_member< PossiblyEmptyBase, NonEmptyMember, true >
       : public PossiblyEmptyBase
    {
        typedef PossiblyEmptyBase base_type;
        typedef NonEmptyMember member_type;

        NonEmptyMember member;
        ...
    };

    template<typename PossiblyEmptyBase, typename NonEmptyMember>
    struct empty_member< PossiblyEmptyBase, NonEmptyMember, false >
       : public PossiblyEmptyBase
    {
        typedef PossiblyEmptyBase base_type;
        typedef NonEmptyMember member_type;

        PossiblyEmptyBase pem;
        NonEmptyMember member;
        ...
    };

Heck, while we're at it, why not make both first and second members 
possibly zero-sized.  This might look a little more like a souped 
up/specialized std::pair.  Here's a complete working example:

------------cut here------------

template< typename T > struct call_traits
{
    typedef const T & type;
    static const bool is_pod = false;
    enum { by_value = false };
};

template< typename T >
struct call_traits< T* >
{
        typedef T * const type;
    static const bool is_pod = true;
        enum { by_value = true };
};

template< typename T >
struct call_traits< T& >
{
        typedef T & type;
    static const bool is_pod = true;
        enum { by_value = false };
};

template< typename T, int sz >
struct call_traits< T[sz] >
{
        typedef T * const type;
    static const bool is_pod = true;
        enum { by_value = true };
};

template<>
struct call_traits< int >
{
        typedef int const type;
    static const bool is_pod = true;
        enum { by_value = true };
};

template<>
struct call_traits< unsigned long >
{
        typedef  unsigned long const type;
    static const bool is_pod = true;
        enum { by_value = true };
};

template<typename T1, typename T2,
        bool FirstPod = call_traits<T1>::is_pod,
        bool SecondPod = call_traits<T2>::is_pod> struct empty_member;

template<typename T1, typename T2>
struct empty_member<T1, T2, false, false>
        : private T1
{
        typedef T1 first_type;
        typedef T2 second_type;

    empty_member() {}

        empty_member( typename call_traits<first_type>::type x,
                      typename call_traits<second_type>::type y )
                : first_type(x), second_(y) {}

        // To avoid ambiguity, do not use the single argument constructors
        // if there is any possibility PossiblyEmptyBase and NonEmptyMember
        // could be the same class.
        explicit empty_member( typename call_traits<first_type>::type x )
                : first_type(x) {}

        explicit empty_member( typename call_traits<second_type>::type y )
                : second_(y) {}

        first_type&       first()       { return *this; }
        const first_type& first() const { return *this; }

        second_type&       second()       { return second_; }
        const second_type& second() const { return second_; }

private:
        second_type second_;
};

template<typename T1, typename T2>
struct empty_member<T1, T2, false, true>
        : private T1
{
        typedef T1 first_type;
        typedef T2 second_type;

    empty_member() {}

        empty_member( typename call_traits<first_type>::type x,
                      typename call_traits<second_type>::type y )
                : first_type(x), second_(y) {}

        // To avoid ambiguity, do not use the single argument constructors
        // if there is any possibility PossiblyEmptyBase and NonEmptyMember
        // could be the same class.
        explicit empty_member( typename call_traits<first_type>::type x )
                : first_type(x) {}

        explicit empty_member( typename call_traits<second_type>::type y )
                : second_(y) {}

        first_type&       first()       { return *this; }
        const first_type& first() const { return *this; }

        second_type&       second()       { return second_; }
        const second_type& second() const { return second_; }

private:
        second_type second_;
};

template<typename T1, typename T2>
struct empty_member<T1, T2, true, false>
        : private T2
{
        typedef T1 first_type;
        typedef T2 second_type;

    empty_member() {}

        empty_member( typename call_traits<first_type>::type x,
                      typename call_traits<second_type>::type y )
                : first_(x), second_type(y) {}

        // To avoid ambiguity, do not use the single argument constructors
        // if there is any possibility PossiblyEmptyBase and NonEmptyMember
        // could be the same class.
        explicit empty_member( typename call_traits<first_type>::type x )
                : first_(x) {}

        explicit empty_member( typename call_traits<second_type>::type y )
                : second_type(y) {}

        first_type&       first()       { return first_; }
        const first_type& first() const { return first_; }

        second_type&       second()       { return *this; }
        const second_type& second() const { return *this; }

private:
        first_type first_;
};

template<typename T1, typename T2>
struct empty_member<T1, T2, true, true>
{
        typedef T1 first_type;
        typedef T2 second_type;

    empty_member() {}

        empty_member( typename call_traits<first_type>::type x,
                      typename call_traits<second_type>::type y )
                : first_(x), second_(y) {}

        // To avoid ambiguity, do not use the single argument constructors
        // if there is any possibility PossiblyEmptyBase and NonEmptyMember
        // could be the same class.
        explicit empty_member( typename call_traits<first_type>::type x )
                : first_(x) {}

        explicit empty_member( typename call_traits<second_type>::type y )
                : second_(y) {}

        first_type&       first()       { return first_; }
        const first_type& first() const { return first_; }

        second_type&       second()       { return second_; }
        const second_type& second() const { return second_; }

private:
        first_type first_;
        second_type second_;
};

#include <memory>
#include <functional>

template <class T, class Compare = std::less<T>, class Allocator = 
std::allocator<T> >
class SortedVec
{
public:
        typedef unsigned long size_type;
        SortedVec(const Compare& comp = Compare(), const Allocator& a = 
Allocator())
                : comp_(comp, 0), alloc_(a, 0) {}

        size_type size() const {return sz();}
private:
        T* data_;
        empty_member<Compare, size_type> comp_;  // member = size
                Compare&       Comp()       {return comp_.first();}
                const Compare& Comp() const {return comp_.first();}
                size_type& sz()       {return comp_.second();}
                size_type  sz() const {return comp_.second();}
        empty_member<Allocator, size_type> alloc_;  // member = capacity
                Allocator&       Alloc()       {return alloc_.first();}
                const Allocator& Alloc() const {return alloc_.first();}
                size_type& cap()       {return alloc_.second();}
                size_type  cap() const {return alloc_.second();}
};

bool
comp(int x, int y)
{
        return x > y;
}

typedef bool (*Comp)(int, int);

struct A {};
struct B {};

#include <iostream>

int main()
{
        SortedVec<int, Comp> a(comp);
        SortedVec<int> b;
        std::cout  << "sizeof(a) = " << sizeof(a) << "\nsizeof(b) = " << 
sizeof(b) << '\n';
        std::cout << "a.size() = " << a.size() << '\n';
        empty_member<A, B> c;
        std::cout << "sizeof(c) = " << sizeof(c) << '\n';
}

------------finish cut here------------

This prints out (on my system):

sizeof(a) = 16
sizeof(b) = 12
a.size() = 0
sizeof(c) = 1

I haven't double checked everything, so there may be bugs above.  And 
there may be better ways of implementing parts of it.  But I think the 
basic idea would be a valuable addition to empty_member.

-Howard