Boost C++ Libraries

...one of the most highly regarded and expertly designed C++ library projects in the world. — Herb Sutter and Andrei Alexandrescu, C++ Coding Standards

Boost.Flyweight Tutorial: Key-value flyweights

Basics

Boost.Flyweight tutorial

Configuring Boost.Flyweight

Key-value flyweights
- Key extractors
- Type requirements

Key-value flyweights

Continuing with our online game example, suppose we have a huge class for handling rendering textures:

class texture
{
public:
  texture(const std::string& filename){/* loads texture file */}

  const std::string& get_filename()const;

  // rest of the interface
};

and we decide to use flyweight<texture> to ease the manipulation of these objects. Now consider this seemingly innocent expression:

flyweight<texture> fw("grass.texture");

Note that in order to construct fw we are implicitly constructing a full grass texture object. The expression is mostly equivalent to

flyweight<texture> fw(texture("grass.texture"));

This is unnaceptably costly: we are constructing a massive temporary object just to throw it away in most cases, since Boost.Flyweight most likely already has an internal equivalent object to which fw will be bound --value sharing is the key feature behind the flyweight pattern after all. In this particular example, texture filenames act as a key to the actual texture objects: two texture objects constructed from the same filename are equivalent. So, we would like for filenames to be used for texture lookup and somehow be sure that the costly texture construction is only performed when no equivalent value has been found.

flyweight<T> makes this distinction between key and value blurry because it uses T both as the key type and its associated value type. When this is inefficient, as in our texture example, we can explicity specify both types using the key_value construct:

#include <boost/flyweight.hpp>
#include <boost/flyweight/key_value.hpp>
...
flyweight<key_value<std::string,texture> > fw("grass.texture");

So called key-value flyweights have then the form flyweight<key_value<K,T> >: the key type K is used to do the internal lookup for the associated values of type T. Key-value flyweights guarantee that T values are not constructed except when no other equivalent value exists; such construction is done from the associated K value.

Key extractors

Besides the key-based semantics on construction time, key-value flyweights behave much the same as regular flyweights, although some differences persist. Consider the following code, which poses no problems with regular flyweights:

const texture& get_texture(const object&);
...
flyweight<key_value<std::string,texture> > fw;
...
fw=get_texture(obj);

The assignment cannot possibly work, because a key of type std::string is needed to do the internal lookup whereas we are passing a full texture object. Indeed, the code produces a compilation error similar to this:

error: 'boost::mpl::assertion_failed' : cannot convert parameter 1 from
'boost::mpl::failed ************(__thiscall boost::flyweights::detail::
regular_key_value<Key,Value>::rep_type::no_key_from_value_failure::
NO_KEY_FROM_VALUE_CONVERSION_PROVIDED::* ***********)(std::string,texture)'
to 'boost::mpl::assert<false>::type'...

It turns out that we can make the assignment work if only we provide a means to retrieve the key from the value. This is not always possible, but in our particular example the texture class does store the filename used for construction, as indicated by the texture::get_filename member function. We take advantage of this by specifying a suitable key extractor as part of the flyweight type definition:

struct texture_filename_extractor
{
  const std::string& operator()(const texture& x)const
  {
    return x.get_filename();
  }
};

flyweight<key_value<std::string,texture,texture_filename_extractor> > fw;
...
fw=get_texture(obj); // OK now

The specification of a key extractor in the definition of a key-value flyweight results in internal space optimizations, as the keys need not be stored along the values but are retrieved from them instead. So, it is always a good idea to provide a key extractor when possible even if your program does not contain assignment statements like the one above.

Examples 2 and 5 of the examples section make use of key-value flyweights.

Type requirements

Many of the requirements imposed on T for regular flyweights move to the key type in the case of a key-value flyweight<key_value<K,T> >. Now it is K that must be Assignable, Equality Comparable and interoperate with Boost.Hash, where equality and hash compatibility are requirements imposed by the default internal factory of Boost.Flyweight and can change if this factory is further configured or replaced by the user. The only requisite retained on T is that it must be constructible from K; only in the case that a flyweight is directly assigned a T object is also T required to be Assignable. To serialize objects of type flyweight<key_value<K,T> > only K needs to be serializable.