D
Daniel Lidström
Hi!
I previously posted a flyweight template class, and asked for suggestions
on how to improve it (see
http://groups.google.com/group/microsoft.public.vc.language/browse_thread/thread/ccf2c8eff4b0043d).
Now I present a new version, with some improvements. Tom Widmer had some
useful comments that I have incorporated in the new design. I have also
used some ideas from the flyweight library that is about to enter boost.
The boost version is very complex, using template meta programming and
allows all kinds of customization. The version I have designed is usable
right away, and can be used on compilers such as VC6 and eVC4 (with the
help of STLport).
First of all, the flyweight design pattern is useful when you have a large
number of small objects, that are very likely to have the same value. In
that case it is possible to share the representation between instances.
This class attempts to solve this problem in a generic way. For example, I
experienced a problem where I had many empty std::strings, each of which
takes up 28 bytes when using VC7.1. Using the flyweight class it is only
necessary to have one empty string.
Now to the improvements. This flyweight template by default uses a hashed
container to store values. This container can now be changed (with not much
trouble) if you desire. The default behaviour when values are no longer
referenced in the factory is to remove them, sort of a simple garbage
collection. This happens automatically but can be changed for your factory.
The flyweight template class is templated on the value and factory:
template<class value, class factory>
class flyweight;
value: default constructible, streamable (if you use it),
copy-constructible, comparable and hashable (by default).
factory: see below
Let me show some sample usages:
// We are going to make this class a flyweight
struct Person
{
Person(const std::string& s1, const std::string& s2)
: firstName(s1), lastName(s2) {}
std::string firstName, lastName;
// default behaviour: equality comparable
bool operator==(const Person& right) const
{
return firstName==right.firstName && lastName==right.lastName;
}
};
// default behavour: we need to be able to hash Person instances
std::size_t hash_value(const Person& person)
{
std::size_t h = 0;
// boost::hash is very good
boost::hash_combine(h, person.firstName);
boost::hash_combine(h, person.lastName);
return h;
}
Here's some sample test cases using the above class and flyweight:
void flyweight_test::test_1()
{
GFL::flyweight<Person> fw1(Person("Daniel", "Lidstrom"));
GFL::flyweight<Person> fw2(Person("Bjarne", "Stroustrup"));
CPPUNIT_ASSERT(fw1!=fw2);
GFL::flyweight<Person> fw3(Person("Daniel", "Lidstrom"));
CPPUNIT_ASSERT(fw1==fw3);
}
Here's an other sample that tries to maximize the size of the factory:
int main()
{
srand(0);
typedef GFL::flyweight<std::string> fwstring;
const int N = 100000;
std::vector<fwstring> vec(N, fwstring());
// create some flyweights
for( int i=0; i<N; i++ )
{
// create a string with some random characters
std::string str;
str += 'a' + rand()%8;
str += 'a' + rand()%8;
str += 'a' + rand()%8;
str += 'a' + rand()%8;
str += 'a' + rand()%8;
vec = fwstring(str);
}
std::cin.get();
}
The flyweight template uses some simple tricks to allow changes to the
wrapped value. It does this by using an internal class that acts as a
postfix operator-> wrapper. This allows changing the flyweight using the ->
operator:
GFL::flyweight<Person> fw(Person("Daniel", "Lidstrom"));
fw->firstName = "Bjarne";
As I mentioned in the beginning, it is possible to change the default
requirements of the value stored in the flyweight. If you dislike computing
hash values, you can use a std::set-based factory. Here's a sample:
template<class value, class less>
struct ordered_factory
{
typedef ordered_factory this_type;
typedef GFL::refcounted_value<const value> entry_type;
typedef GFL::refcounted_handle<entry_type, this_type> handle_type;
typedef std::set<entry_type, less> Map;
typedef typename Map::const_iterator const_iterator;
static void erase(const handle_type& h)
{
const entry_type& entry = h.get();
get_map().erase(entry);
}
static const entry_type& insert(const value& v)
{
entry_type et(v);
Map& m = get_map();
const_iterator it = m.find(et);
if( it==m.end() )
return *m.insert(et).first;
else
return *it;
}
private:
static Map& get_map()
{
static Map theMap;
return theMap;
}
};
The requirement of the factory is that it has the entry_type and value_type
definitions. The handle_type has to be convertible to entry_type with a
get() member, and the entry_type has to be convertible to the value type
with a get() member.
Here's a sample with the ordered_factory:
// this factory requires Person to be less than comparable
struct ltPerson
{
template<class PersonEntry>
bool operator()(const PersonEntry& pe1, const PersonEntry& pe2) const
{
const Person& left = pe1.get();
const Person& right = pe2.get();
return std::make_pair(left.firstName, left.lastName)
< std::make_pair(right.firstName, right.lastName);
}
};
void flyweight_test::test_3()
{
typedef GFL::flyweight<Person, ordered_factory<Person, ltPerson> >
Person_fw;
Person_fw fw1(Person("Daniel", "Lidstrom"));
Person_fw fw2(Person("Bjarne", "Stroustrup"));
CPPUNIT_ASSERT(fw1!=fw2);
Person_fw fw3(Person("Daniel", "Lidstrom"));
CPPUNIT_ASSERT(fw1==fw3);
}
Now to the real deal. Here's the flyweight.h header, in all its glory:
//! @file flyweight.h
//! flyweight design pattern.
//! @author Daniel Lidstrom <[email protected]>
//! @date 2007-11-16 11:20
//! @ingroup GFL
//!
#if !defined(__FLYWEIGHT_H__20071116T1120)
#define __FLYWEIGHT_H__20071116T1120
#include <boost/functional/hash.hpp> // hash
#if defined(_MSC_VER) && _MSC_VER>=1300
#include <hash_map> // hash_multimap
namespace GFLUtils = stdext;
#elif defined(STLPORT)
#include <hash_map>
namespace GFLUtils = std;
#elif defined(__GNUC__)
//#include <tr1/unordered_map> // use this if you can
#include <ext/hash_map>
namespace GFLUtils = __gnu_cxx;
#endif
namespace GFL
{
using boost::hash_value;
//! Used to hash and compare flyweights.
template<class T>
struct flyweight_traits
{
//!
//! Compare two flyweights.
//!
static bool equal(const T& left, const T& right)
{
return left == right;
}
//!
//! Compute the hash of a flyweight.
//!
static std::size_t hash(const T& t)
{
return hash_value(t);
}
};
//!
//! Used to store reference counted value types in the factory.
//!
template<class value>
class refcounted_value
{
public:
explicit refcounted_value(const value& v)
: m_value(v), ref(0)
{}
refcounted_value(const refcounted_value& right)
: m_value(right.m_value), ref(0)
{}
refcounted_value& operator=(const refcounted_value& right)
{
m_value = right.m_value;
return *this;
}
const value& get() const
{
return m_value;
}
long count() const
{
return ref;
}
void add_ref() const
{
++ref;
}
bool release() const
{
return (--ref==0);
}
private:
value m_value;
mutable long ref;
};
//!
//! Used as a handle to reference counted values in the factory.
//! This class calls upon the tracking_helper to manage the lifetime
//! of the reference counted value.
//!
template<class handle, class tracking_helper>
class refcounted_handle
{
public:
explicit refcounted_handle(const handle& h)
: m_handle(&h)
{
m_handle->add_ref();
}
refcounted_handle(const refcounted_handle& right)
: m_handle(right.m_handle)
{
m_handle->add_ref();
}
refcounted_handle& operator=(const refcounted_handle& x)
{
refcounted_handle tmp(x);
std::swap(m_handle, tmp.m_handle);
return *this;
}
~refcounted_handle()
{
if( m_handle->release() )
{
tracking_helper::erase(*this);
}
}
const handle& get() const
{
return *m_handle;
}
private:
const handle* m_handle;
};
//!
//! The default factory type. Stores values in a hash map.
//! Reference counting assures values are removed when
//! they are no longer referenced.
//!
template<class value, class traits=flyweight_traits<value> >
class hashed_factory
{
public:
typedef hashed_factory this_type;
typedef refcounted_value<const value> entry_type;
typedef refcounted_handle<entry_type, this_type> handle_type;
typedef GFLUtils::hash_multimap<std::size_t, entry_type> Map;
typedef typename Map::const_iterator const_iterator;
static handle_type insert(const value& v)
{
std::size_t hashv = traits::hash(v);
return handle_type(insert(v, hashv));
}
static void erase(const handle_type& h)
{
const entry_type& entry = h.get();
get_map().erase(traits::hash(entry.get()));
}
private:
static Map& get_map()
{
static Map theMap;
return theMap;
}
static const entry_type& insert(const value& v, std::size_t hashv)
{
const entry_type* ret = 0;
std:
air<const_iterator, const_iterator> p
= get_map().equal_range(hashv);
for( const_iterator it=p.first; !ret && it!=p.second; ++it )
{
const entry_type& found_value = it->second;
if( traits::equal(found_value.get(), v) )
{
ret = &found_value;
}
}
// if we didn't find a previous fly, insert a new
if( !ret )
{
ret = &get_map().insert(std::make_pair(hashv, v))->second;
}
return *ret;
}
};
//!
//! @author Daniel Lidstrom <[email protected]>
//! @date 2007-11-16 11:20
//! @ingroup GFL
//! flyweight design pattern. Allows you to easily create flyweight
//! classes.
//!
template<class fl, class factory=hashed_factory<fl> >
class flyweight
{
public:
typedef fl value_type;
typedef factory factory_type;
typedef typename factory_type::handle_type handle_type;
//!
//! Default constructor.
//!
flyweight()
: value(factory_type::insert(value_type()))
{ }
//!
//! Destructor.
//!
~flyweight()
{}
//!
//! Constructor.
//!
//! @param value_type value_type object (will be copied)
//!
flyweight(const value_type& fly)
: value(factory_type::insert(fly))
{ }
//!
//! Assignment operator.
//!
flyweight& operator=(const value_type& v)
{
return operator=(flyweight(v));
}
//!
//! Swap contents of two flyweights.
//!
void swap(flyweight& right)
{
std::swap(right.value, value);
}
//!
//! Equality comparison. Two flyweights are considered equal
//! if their internal pointers are equal.
//!
friend bool operator==(const flyweight& left, const flyweight& right)
{
return &left.get() == &right.get();
}
friend bool operator!=(const flyweight& left, const flyweight& right)
{
return !(left==right);
}
//!
//! Output stream operator.
//!
template<class Stream>
Stream& StreamOut(Stream& stream) const
{
stream << get();
return stream;
}
//!
//! Input stream operator.
//!
template<class Stream>
Stream& StreamIn(Stream& stream)
{
value_type f;
stream >> f;
operator=(flyweight(f));
return stream;
}
//!
//! Accessor.
//!
//! @return value_type
//!
const value_type& get() const
{
return value.get().get();
}
//!
//! Internal class used to allow changing of
//! a flyweight using the -> operator.
//!
class value_proxy
{
flyweight& mflyweight;
value_type value;
public:
value_proxy(flyweight& f)
: mflyweight(f),
value(f.value.get().get())
{}
// Exceptions are not allowed to propagate from destructors,
// is a requirement for using the standard library containers.
// That is very likely *not* a requirement for value_proxy.
// However, if an exception is thrown during an operation
// of the fly, this destructor must *not* throw. If that
// happens we are throwing during exception handling which
// leads to abort.
~value_proxy()
{
try
{
mflyweight = value;
}
catch(...)
{}
}
value_type* operator->()
{
return &value;
}
};
friend class value_proxy;
//!
//! Provides an easy way to access member functions of the fly.
//!
const value_type* operator->() const
{
return &value.get().get();
}
//!
//! Non-const version.
//!
value_proxy operator->()
{
return value_proxy(*this);
}
//!
//! Automatic conversion.
//!
operator const value_type&() const
{
return get();
}
private:
handle_type value;
};
}
template<class Ostream, class fl, class tr>
Ostream& operator<<(Ostream& os, const GFL::flyweight<fl, tr>& f)
{
return f.StreamOut(os);
}
template<class Istream, class fl, class tr>
Istream& operator>>(Istream& is, GFL::flyweight<fl, tr>& f)
{
return f.StreamIn(is);
}
#endif
I will gratefully accept any comments or (constructive) critizism you might
have. This piece of code owes a lot to Joaquin Lopes Munez (author of the
soon-to-be boost library). Thanks Joaquin!
P.S. Follow-up set to microsoft.public.vc.language because I can only post
through Microsoft's news server.
I previously posted a flyweight template class, and asked for suggestions
on how to improve it (see
http://groups.google.com/group/microsoft.public.vc.language/browse_thread/thread/ccf2c8eff4b0043d).
Now I present a new version, with some improvements. Tom Widmer had some
useful comments that I have incorporated in the new design. I have also
used some ideas from the flyweight library that is about to enter boost.
The boost version is very complex, using template meta programming and
allows all kinds of customization. The version I have designed is usable
right away, and can be used on compilers such as VC6 and eVC4 (with the
help of STLport).
First of all, the flyweight design pattern is useful when you have a large
number of small objects, that are very likely to have the same value. In
that case it is possible to share the representation between instances.
This class attempts to solve this problem in a generic way. For example, I
experienced a problem where I had many empty std::strings, each of which
takes up 28 bytes when using VC7.1. Using the flyweight class it is only
necessary to have one empty string.
Now to the improvements. This flyweight template by default uses a hashed
container to store values. This container can now be changed (with not much
trouble) if you desire. The default behaviour when values are no longer
referenced in the factory is to remove them, sort of a simple garbage
collection. This happens automatically but can be changed for your factory.
The flyweight template class is templated on the value and factory:
template<class value, class factory>
class flyweight;
value: default constructible, streamable (if you use it),
copy-constructible, comparable and hashable (by default).
factory: see below
Let me show some sample usages:
// We are going to make this class a flyweight
struct Person
{
Person(const std::string& s1, const std::string& s2)
: firstName(s1), lastName(s2) {}
std::string firstName, lastName;
// default behaviour: equality comparable
bool operator==(const Person& right) const
{
return firstName==right.firstName && lastName==right.lastName;
}
};
// default behavour: we need to be able to hash Person instances
std::size_t hash_value(const Person& person)
{
std::size_t h = 0;
// boost::hash is very good
boost::hash_combine(h, person.firstName);
boost::hash_combine(h, person.lastName);
return h;
}
Here's some sample test cases using the above class and flyweight:
void flyweight_test::test_1()
{
GFL::flyweight<Person> fw1(Person("Daniel", "Lidstrom"));
GFL::flyweight<Person> fw2(Person("Bjarne", "Stroustrup"));
CPPUNIT_ASSERT(fw1!=fw2);
GFL::flyweight<Person> fw3(Person("Daniel", "Lidstrom"));
CPPUNIT_ASSERT(fw1==fw3);
}
Here's an other sample that tries to maximize the size of the factory:
int main()
{
srand(0);
typedef GFL::flyweight<std::string> fwstring;
const int N = 100000;
std::vector<fwstring> vec(N, fwstring());
// create some flyweights
for( int i=0; i<N; i++ )
{
// create a string with some random characters
std::string str;
str += 'a' + rand()%8;
str += 'a' + rand()%8;
str += 'a' + rand()%8;
str += 'a' + rand()%8;
str += 'a' + rand()%8;
vec = fwstring(str);
}
std::cin.get();
}
The flyweight template uses some simple tricks to allow changes to the
wrapped value. It does this by using an internal class that acts as a
postfix operator-> wrapper. This allows changing the flyweight using the ->
operator:
GFL::flyweight<Person> fw(Person("Daniel", "Lidstrom"));
fw->firstName = "Bjarne";
As I mentioned in the beginning, it is possible to change the default
requirements of the value stored in the flyweight. If you dislike computing
hash values, you can use a std::set-based factory. Here's a sample:
template<class value, class less>
struct ordered_factory
{
typedef ordered_factory this_type;
typedef GFL::refcounted_value<const value> entry_type;
typedef GFL::refcounted_handle<entry_type, this_type> handle_type;
typedef std::set<entry_type, less> Map;
typedef typename Map::const_iterator const_iterator;
static void erase(const handle_type& h)
{
const entry_type& entry = h.get();
get_map().erase(entry);
}
static const entry_type& insert(const value& v)
{
entry_type et(v);
Map& m = get_map();
const_iterator it = m.find(et);
if( it==m.end() )
return *m.insert(et).first;
else
return *it;
}
private:
static Map& get_map()
{
static Map theMap;
return theMap;
}
};
The requirement of the factory is that it has the entry_type and value_type
definitions. The handle_type has to be convertible to entry_type with a
get() member, and the entry_type has to be convertible to the value type
with a get() member.
Here's a sample with the ordered_factory:
// this factory requires Person to be less than comparable
struct ltPerson
{
template<class PersonEntry>
bool operator()(const PersonEntry& pe1, const PersonEntry& pe2) const
{
const Person& left = pe1.get();
const Person& right = pe2.get();
return std::make_pair(left.firstName, left.lastName)
< std::make_pair(right.firstName, right.lastName);
}
};
void flyweight_test::test_3()
{
typedef GFL::flyweight<Person, ordered_factory<Person, ltPerson> >
Person_fw;
Person_fw fw1(Person("Daniel", "Lidstrom"));
Person_fw fw2(Person("Bjarne", "Stroustrup"));
CPPUNIT_ASSERT(fw1!=fw2);
Person_fw fw3(Person("Daniel", "Lidstrom"));
CPPUNIT_ASSERT(fw1==fw3);
}
Now to the real deal. Here's the flyweight.h header, in all its glory:
//! @file flyweight.h
//! flyweight design pattern.
//! @author Daniel Lidstrom <[email protected]>
//! @date 2007-11-16 11:20
//! @ingroup GFL
//!
#if !defined(__FLYWEIGHT_H__20071116T1120)
#define __FLYWEIGHT_H__20071116T1120
#include <boost/functional/hash.hpp> // hash
#if defined(_MSC_VER) && _MSC_VER>=1300
#include <hash_map> // hash_multimap
namespace GFLUtils = stdext;
#elif defined(STLPORT)
#include <hash_map>
namespace GFLUtils = std;
#elif defined(__GNUC__)
//#include <tr1/unordered_map> // use this if you can
#include <ext/hash_map>
namespace GFLUtils = __gnu_cxx;
#endif
namespace GFL
{
using boost::hash_value;
//! Used to hash and compare flyweights.
template<class T>
struct flyweight_traits
{
//!
//! Compare two flyweights.
//!
static bool equal(const T& left, const T& right)
{
return left == right;
}
//!
//! Compute the hash of a flyweight.
//!
static std::size_t hash(const T& t)
{
return hash_value(t);
}
};
//!
//! Used to store reference counted value types in the factory.
//!
template<class value>
class refcounted_value
{
public:
explicit refcounted_value(const value& v)
: m_value(v), ref(0)
{}
refcounted_value(const refcounted_value& right)
: m_value(right.m_value), ref(0)
{}
refcounted_value& operator=(const refcounted_value& right)
{
m_value = right.m_value;
return *this;
}
const value& get() const
{
return m_value;
}
long count() const
{
return ref;
}
void add_ref() const
{
++ref;
}
bool release() const
{
return (--ref==0);
}
private:
value m_value;
mutable long ref;
};
//!
//! Used as a handle to reference counted values in the factory.
//! This class calls upon the tracking_helper to manage the lifetime
//! of the reference counted value.
//!
template<class handle, class tracking_helper>
class refcounted_handle
{
public:
explicit refcounted_handle(const handle& h)
: m_handle(&h)
{
m_handle->add_ref();
}
refcounted_handle(const refcounted_handle& right)
: m_handle(right.m_handle)
{
m_handle->add_ref();
}
refcounted_handle& operator=(const refcounted_handle& x)
{
refcounted_handle tmp(x);
std::swap(m_handle, tmp.m_handle);
return *this;
}
~refcounted_handle()
{
if( m_handle->release() )
{
tracking_helper::erase(*this);
}
}
const handle& get() const
{
return *m_handle;
}
private:
const handle* m_handle;
};
//!
//! The default factory type. Stores values in a hash map.
//! Reference counting assures values are removed when
//! they are no longer referenced.
//!
template<class value, class traits=flyweight_traits<value> >
class hashed_factory
{
public:
typedef hashed_factory this_type;
typedef refcounted_value<const value> entry_type;
typedef refcounted_handle<entry_type, this_type> handle_type;
typedef GFLUtils::hash_multimap<std::size_t, entry_type> Map;
typedef typename Map::const_iterator const_iterator;
static handle_type insert(const value& v)
{
std::size_t hashv = traits::hash(v);
return handle_type(insert(v, hashv));
}
static void erase(const handle_type& h)
{
const entry_type& entry = h.get();
get_map().erase(traits::hash(entry.get()));
}
private:
static Map& get_map()
{
static Map theMap;
return theMap;
}
static const entry_type& insert(const value& v, std::size_t hashv)
{
const entry_type* ret = 0;
std:
air<const_iterator, const_iterator> p= get_map().equal_range(hashv);
for( const_iterator it=p.first; !ret && it!=p.second; ++it )
{
const entry_type& found_value = it->second;
if( traits::equal(found_value.get(), v) )
{
ret = &found_value;
}
}
// if we didn't find a previous fly, insert a new
if( !ret )
{
ret = &get_map().insert(std::make_pair(hashv, v))->second;
}
return *ret;
}
};
//!
//! @author Daniel Lidstrom <[email protected]>
//! @date 2007-11-16 11:20
//! @ingroup GFL
//! flyweight design pattern. Allows you to easily create flyweight
//! classes.
//!
template<class fl, class factory=hashed_factory<fl> >
class flyweight
{
public:
typedef fl value_type;
typedef factory factory_type;
typedef typename factory_type::handle_type handle_type;
//!
//! Default constructor.
//!
flyweight()
: value(factory_type::insert(value_type()))
{ }
//!
//! Destructor.
//!
~flyweight()
{}
//!
//! Constructor.
//!
//! @param value_type value_type object (will be copied)
//!
flyweight(const value_type& fly)
: value(factory_type::insert(fly))
{ }
//!
//! Assignment operator.
//!
flyweight& operator=(const value_type& v)
{
return operator=(flyweight(v));
}
//!
//! Swap contents of two flyweights.
//!
void swap(flyweight& right)
{
std::swap(right.value, value);
}
//!
//! Equality comparison. Two flyweights are considered equal
//! if their internal pointers are equal.
//!
friend bool operator==(const flyweight& left, const flyweight& right)
{
return &left.get() == &right.get();
}
friend bool operator!=(const flyweight& left, const flyweight& right)
{
return !(left==right);
}
//!
//! Output stream operator.
//!
template<class Stream>
Stream& StreamOut(Stream& stream) const
{
stream << get();
return stream;
}
//!
//! Input stream operator.
//!
template<class Stream>
Stream& StreamIn(Stream& stream)
{
value_type f;
stream >> f;
operator=(flyweight(f));
return stream;
}
//!
//! Accessor.
//!
//! @return value_type
//!
const value_type& get() const
{
return value.get().get();
}
//!
//! Internal class used to allow changing of
//! a flyweight using the -> operator.
//!
class value_proxy
{
flyweight& mflyweight;
value_type value;
public:
value_proxy(flyweight& f)
: mflyweight(f),
value(f.value.get().get())
{}
// Exceptions are not allowed to propagate from destructors,
// is a requirement for using the standard library containers.
// That is very likely *not* a requirement for value_proxy.
// However, if an exception is thrown during an operation
// of the fly, this destructor must *not* throw. If that
// happens we are throwing during exception handling which
// leads to abort.
~value_proxy()
{
try
{
mflyweight = value;
}
catch(...)
{}
}
value_type* operator->()
{
return &value;
}
};
friend class value_proxy;
//!
//! Provides an easy way to access member functions of the fly.
//!
const value_type* operator->() const
{
return &value.get().get();
}
//!
//! Non-const version.
//!
value_proxy operator->()
{
return value_proxy(*this);
}
//!
//! Automatic conversion.
//!
operator const value_type&() const
{
return get();
}
private:
handle_type value;
};
}
template<class Ostream, class fl, class tr>
Ostream& operator<<(Ostream& os, const GFL::flyweight<fl, tr>& f)
{
return f.StreamOut(os);
}
template<class Istream, class fl, class tr>
Istream& operator>>(Istream& is, GFL::flyweight<fl, tr>& f)
{
return f.StreamIn(is);
}
#endif
I will gratefully accept any comments or (constructive) critizism you might
have. This piece of code owes a lot to Joaquin Lopes Munez (author of the
soon-to-be boost library). Thanks Joaquin!
P.S. Follow-up set to microsoft.public.vc.language because I can only post
through Microsoft's news server.