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