Boost C++ Libraries

(Code samples from basic_base.cpp.)

Imagine we are developing a role playing game in C++ where sprites are rendered on screen; for the purposes of illustration we can model rendering simply as outputting some information to a std::ostream:

struct sprite
{
  sprite(int id):id{id}{}
  virtual ~sprite()=default;
  virtual void render(std::ostream& os)const=0;

  int id;
};

The game features warriors, juggernauts (a special type of warrior) and goblins, each represented by its own class derived (directly or indirectly) from sprite:

struct warrior:sprite
{
  using sprite::sprite;
  warrior(std::string rank,int id):sprite{id},rank{std::move(rank)}{}

  void render(std::ostream& os)const override{os<<rank<<" "<<id;}

  std::string rank="warrior";
};

struct juggernaut:warrior
{
  juggernaut(int id):warrior{"juggernaut",id}{}
};

struct goblin:sprite
{
  using sprite::sprite;
  void render(std::ostream& os)const override{os<<"goblin "<<id;}
};

Let us populate a polymorphic collection with an assortment of sprites:

#include <boost/poly_collection/base_collection.hpp>
...

boost::base_collection<sprite> c;

std::mt19937                 gen{92748}; // some arbitrary random seed
std::discrete_distribution<> rnd{{1,1,1}};
for(int i=0;i<8;++i){        // assign each type with 1/3 probability
  switch(rnd(gen)){
    case 0: c.insert(warrior{i});break;
    case 1: c.insert(juggernaut{i});break;
    case 2: c.insert(goblin{i});break;
  }
}

There are two aspects to notice here:

Important

Elements inserted into a boost::base_collection (or the other containers of Boost.PolyCollection) must be copyable and assignable; strictly speaking, they must at least model MoveConstructible and either be MoveAssignable or not throw on move construction. This might force you to revisit your code as it is customary to explicitly forbid copying at the base level of a virtual hierarchy to avoid slicing.

Rendering can now be implemented with a simple for loop over c:

const char* comma="";
for(const sprite& s:c){
  std::cout<<comma;
  s.render(std::cout);
  comma=",";
}
std::cout<<"\n";

The output being:

juggernaut 0,juggernaut 4,juggernaut 7,goblin 1,goblin 3,goblin 5,warrior 2,warrior 6

As we have forewarned, the traversal order does not correspond to that of insertion. Instead, the elements are grouped in segments according to their concrete type. Here we see that juggernauts come first, followed by goblins and warriors. In general, no assumptions should be made about segment ordering, which may be different for this very example in your environment. On the other hand, elements inserted into an already existing segment always come at the end (except if a hint is provided). For instance, after inserting a latecomer goblin with id==8:

c.insert(goblin{8});

the rendering loop outputs (new element in red):

juggernaut 0,juggernaut 4,juggernaut 7,goblin 1,goblin 3,goblin 5,goblin 8,warrior 2,warrior 6

Deletion can be done in the usual way:

// find element with id==7 and remove it
auto it=std::find_if(c.begin(),c.end(),[](const sprite& s){return s.id==7;});
c.erase(it);

Now rendering emits:

juggernaut 0,juggernaut 4,goblin 1,goblin 3,goblin 5,goblin 8,warrior 2,warrior 6

(Code samples from basic_function.cpp. C++14 std::make_unique is used.)

Well into the development of the game, the product manager requests that two new types of entities be added to the rendering loop:

struct window
{
  window(std::string caption):caption{std::move(caption)}{}

  void display(std::ostream& os)const{os<<"["<<caption<<"]";}

  std::string caption;
};

We then decide to refactor the code so that sprites, messsages and windows are stored in dedicated containers:

std::vector<std::unique_ptr<sprite>> sprs;
std::vector<std::string>             msgs;
std::vector<window>                  wnds;

and define our rendering container as a boost::function_collection of callable entities —function pointers or objects with a function call operator()— accepting a std::ostream& as a parameter

#include <boost/poly_collection/function_collection.hpp>
...

// function signature accepting std::ostream& and returning nothing
using render_callback=void(std::ostream&);

boost::function_collection<render_callback> c;

which we fill with suitable adaptors for sprites, std::strings and windows, respectively. Lambda functions allow for a particularly terse code.

auto render_sprite(const sprite& s){
  return [&](std::ostream& os){s.render(os);};
}

auto render_message(const std::string& m){
  return [&](std::ostream& os){os<<m;};
}

auto render_window(const window& w){
  return [&](std::ostream& os){w.display(os);};
}
...

for(const auto& ps:sprs)c.insert(render_sprite(*ps));
for(const auto& m:msgs)c.insert(render_message(m));
for(const auto& w:wnds)c.insert(render_window(w));

The rendering loop now looks like this:

const char* comma="";
for(const auto& cbk:c){
  std::cout<<comma;
  cbk(std::cout);
  comma=",";
}
std::cout<<"\n";

and produces the following for a particular scenario of sprites, messages and windows:

juggernaut 0,goblin 1,warrior 2,goblin 3,"stamina: 10,000","game over",[pop-up 1],[pop-up 2]

The container we have just created works in many respects like a std::vector<std::function<render_callback>>, the main difference being that with boost::function_collection callable entities of the same type are packed together in memory ^[10], thus increasing performance (which is the whole point of using Boost.PolyCollection), while a vector of std::functions results in an individual allocation for each entity stored ^[11]. In fact, the value_type elements held by a boost::function_collection are actually not std::functions, although they behave analogously and can be converted to std::function if needed:

auto cbk=*c.begin();
cbk(std::cout); // renders first element to std::cout
std::function<render_callback> f=cbk;
f(std::cout);   // exactly the same

There is a reason for this: elements of a polymorphic collection cannot be freely assigned to by the user as this could end up trying to insert an object into a segment of a different type. So, unlike with std::function, this will not work:

*c.begin()=render_message("last minute message"); // compile-time error

(Code samples from basic_any.cpp.)

	Note
	Here we just touch on the bare essentials of Boost.TypeErasure needed to present boost::any_collection. The reader is advised to read Boost.TypeErasure documentation for further information.

After measuring the performance of the latest changes, we find that rendering is too slow and decide to refactor once again: if we could store all the entities --sprites, messages and windows-- into one single container, that would eliminate a level of indirection. The problem is that these types are totally unrelated to each other.

Boost.TypeErasure provides a class template boost::type_erasure::any<Concept> able to hold an object of whatever type as long as it conforms to the interface specified by Concept. In our case, we find it particularly easy to implement a common interface for rendering by providing overloads of operator<<

std::ostream& operator<<(std::ostream& os,const sprite& s)
{
  s.render(os);
  return os;
}

// std::string already has a suitable operator<<

std::ostream& operator<<(std::ostream& os,const window& w)
{
  w.display(os);
  return os;
}

so that we can use it to specify the interface all entities have to adhere to:

#include <boost/poly_collection/any_collection.hpp>
#include <boost/type_erasure/operators.hpp>
...

using renderable=boost::type_erasure::ostreamable<>;
boost::any_collection<renderable> c;

The collection just created happily accepts insertion of heterogeneous entities (since interface conformity is silently checked at compile time)

// populate with sprites
std::mt19937                 gen{92748}; // some arbitrary random seed
std::discrete_distribution<> rnd{{1,1,1}};
for(int i=0;i<4;++i){        // assign each type with 1/3 probability
  switch(rnd(gen)){
    case 0: c.insert(warrior{i});break;
    case 1: c.insert(juggernaut{i});break;
    case 2: c.insert(goblin{i});break;
  }
}

// populate with messages
c.insert(std::string{"\"stamina: 10,000\""});
c.insert(std::string{"\"game over\""});

// populate with windows
c.insert(window{"pop-up 1"});
c.insert(window{"pop-up 2"});

and rendering becomes

const char* comma="";
for(const auto& r:c){
  std::cout<<comma<<r;
  comma=",";
}
std::cout<<"\n";

with output

[pop-up 1],[pop-up 2],juggernaut 0,goblin 1,goblin 3,warrior 2,"stamina: 10,000","game over"

As was the case with boost::function_collection, this container is similar to a std::vector<boost::type_erasure::any<Concept>> but has better performance due to packing of same-type elements. Also, the value_type of a boost::any_collection<Concept> is not boost::type_erasure::any<Concept>, but a similarly behaving entity ^[12]. In any case, we are not accessing sprites through an abstract sprite& anymore, so we could as well dismantle the virtual hierarchy and implement each type autonomously: this is left as an exercise to the reader.

Getting back to our boost::base_collection example, suppose we want to refactor the populating code as follows:

std::unique_ptr<sprite> make_sprite()
{
  static std::mt19937                 gen{92748};
  static std::discrete_distribution<> rnd{{1,1,1}};
  static int                          id=0;

  switch(rnd(gen)){
    case 0: return std::make_unique<warrior>(id++);break;
    case 1: return std::make_unique<juggernaut>(id++);break;
    case 2: return std::make_unique<goblin>(id++);break;
  }
}
...

for(int i=0;i<8;++i)c.insert(*make_sprite());
// throws boost::poly_collection::unregistered_type

Unexpectedly, this piece of code throws an exception of type boost::poly_collection::unregistered_type. What has changed from our original code?

Suppose a warrior has been created by make_sprite. The statement c.insert(*make_sprite()) is passing the object as a sprite&: even though boost::base_collection is smart enough to know that the object is actually derived from sprite (by using typeid()) and slicing is to be avoided, there is no way that a segment for it can be created without accessing the type warrior at compile time for the proper internal class templates to be instantiated ^[13]. This did not happen in the pre-refactoring code because objects were passed as references to their true types.

A type is said to be registered into a polymorphic collection if there is a (potentially empty) segment created for it. This can be checked with:

std::cout<<c.is_registered<warrior>()<<"\n";       // prints 0
std::cout<<c.is_registered(typeid(warrior))<<"\n"; // alternate syntax

Registration happens automatically when the object is passed as a reference to its true type or emplace'd, and explicitly with register_types:

c.register_types<warrior,juggernaut,goblin>();
// everything works fine now
for(int i=0;i<8;++i)c.insert(*make_sprite());

Once T has been registered into a polymorphic collection, it remains so regardless of whether objects of type T are stored or not, except if the collection is moved from, assigned to, or swapped.

As slicing is mainly an issue with OOP, unregistered_type exceptions are expected to be much less frequent with boost::function_collection and boost::any_collection. Contrived examples can be found, though:

boost::any_collection<renderable> c1,c2;
... // populate c2

c1.insert(*c2.begin()); // throws: actual type of *c2.begin() not known by c1

For most of the interface of a polymorphic collection, it is possible to only refer to the elements of a given segment by providing either their type or typeid(). For instance:

... // populate c with 8 assorted entities

std::cout<<c.size()<<"\n";                    // 8 sprites
std::cout<<c.size<juggernaut>()<<"\n";        // 2 juggernauts
std::cout<<c.size(typeid(juggernaut))<<"\n";  // alternate syntax
c.clear<juggernaut>();                        // remove juggenauts only
std::cout<<c.empty<juggernaut>()<<"\n";       // 1 (no juggernauts left)
std::cout<<c.size()<<"\n";                    // 6 sprites remaining

Note that any of these (except reserve) will throw boost::poly_collection::unregistered_type if the type is not registered. Segment-specific addressability also includes traversal:

The following runs only over the warriors of the collection:

const char* comma="";
for(auto first=c.begin(typeid(warrior)),last=c.end(typeid(warrior));
    first!=last;++first){
  std::cout<<comma;
  first->render(std::cout);
  comma=",";
}
std::cout<<"\n";

Output:

warrior 2,warrior 6

begin|end(typeid(T)) return objects of type local_base_iterator associated to the segment for T. These iterators dereference to the same value as regular iterators (in the case of boost::base_collection<base>, base&) but can only be used to traverse a given segment (for instance, local_base_iterator's from different segments cannot be compared between them). In exchange, local_base_iterator is a RandomAccessIterator, whereas whole-collection iterators only model ForwardIterator.

A terser range-based for loop can be used with the convenience segment member function:

const char* comma="";
for(const auto& x:c.segment(typeid(warrior))){
  std::cout<<comma;
  x.render(std::cout);
  comma=",";
}
std::cout<<"\n";

Even more powerful than local_base_iterator is local_iterator<T>:

const char* comma="";
for(auto first=c.begin<warrior>(),last=c.end<warrior>();
    first!=last;++first){
  first->rank.insert(0,"super");
  std::cout<<comma;
  first->render(std::cout);
  comma=",";
}
std::cout<<"\n";

// range-based for loop alternative

const char* comma="";
for(auto& x:c.segment<warrior>()){
  x.rank.insert(0,"super");
  std::cout<<comma;
  x.render(std::cout);
  comma=",";
}
std::cout<<"\n";

This appends a "super" prefix to the rank data member of existing warriors:

superwarrior 2,superwarrior 6

The observant reader will have noticed that in order to access rank, which is a member of warrior rather than its base class sprite, first (or x in the range for loop version) has to refer to a warrior&, and this is precisely the difference between local_iterator<warrior> (the type returned by begin<warrior>()) and local_base_iterator. local_iterator<warrior> is also a RandomAccessIterator: for most respects, [begin<T>(), end<T>()) can be regarded as a range over an array of T objects. local_iterator<T>s can be explicitly converted to local_base_iterators. Conversely, if a local_base_iterator is associated to a segment for T, it can then be explictly converted to a local_iterator<T> (otherwise the conversion is undefined behavior).

The figure shows the action scopes of all the iterators associated to a polymorphic collection (const_ versions not included):

We have yet to describe the bottom part of the diagram. Whereas segment(typeid(T)) is used to range over the elements of a particular segment, segment_traversal() returns an object for ranging over segments, so that the whole collection can be processed with a nested segment-element for loop like the following:

const char* comma="";
for(auto seg:c.segment_traversal()){
  for(sprite& s:seg){
    std::cout<<comma;
    s.render(std::cout);
    comma=",";
  }
}
std::cout<<"\n";

Segment decomposition of traversal loops forms the basis of improved-performance algorithms.

Much like std::vector, segments can be made to reserve memory in advance to minimize reallocations:

c.reserve<goblin>(100); // no reallocation till we exceed 100 goblins
std::cout<<c.capacity<goblin>()<<"\n"; // prints 100

If there is no segment for the indicated type (here, goblin), one is automatically created. This is in contrast with the rest of segment-specific member functions, which throw boost::poly_collection::unregistered_type.

reserve can deal with all segments at once. The following

c.reserve(1000); // reserve(1000) for each segment
std::cout<<c.capacity<warrior>()<<", "
         <<c.capacity<juggernaut>()<<", "
         <<c.capacity<goblin>()<<"\n"; // prints 1000, 1000, 1000

instructs every existing segment to reserve 1,000 elements. If a segment is created later (through element insertion or with type registration), its capacity will be different.

	Note
	Unlike standard containers, collection-level capacity() and max_size() are not provided because their usual semantics cannot be applied to Boost.PolyCollection: for instance, capacity() is typically used to check how many elements can be inserted without reallocation, but in a segmented structure that depends on the exact types of the elements and whether they are registered or not.

By type restitution we mean the generic process of getting a concrete entity from an abstract one by providing missing type information:

sprite*  ps=new warrior{5};
// sprite -> warrior
warrior* pw=static_cast<warrior*>(ps);

boost::type_erasure::any<renderable> r=std::string{"hello"};
// renderable -> std::string
std::string& str=boost::type_erasure::any_cast<std::string&>(r);

Type restitution has the potential to increase performance. Consider for instance the following:

// render r with std::string restitution
if(boost::type_erasure::typeid_of(r)==typeid(std::string)){
  std::string& str=boost::type_erasure::any_cast<std::string&>(r);
  std::cout<<str<<"\n";
}
else{
  std::cout<<r<<"\n";
}

Behaviorwise this code is equivalent to simply executing std::cout<<r<<"\n", but when type restitution succeeds the statement std::cout<<str<<"\n" is skipping a virtual-like call that would have happened if r were used instead. From a general point of view, supplying the compiler with extra type information allows it to perform more optimizations than in the abstract case, inlining being the prime example.

All Boost.PolyCollection algorithms accept an optional list of types for restitution. Let us use the boost::any_collection scenario to illustrate this point:

const char* comma="";
boost::poly_collection::for_each
  <warrior,juggernaut,goblin>( // restituted types
  c.begin(),c.end(),[&](const auto& x){ // loop traverses *all* elements
    std::cout<<comma<<x;
    comma=",";
  });
std::cout<<"\n";

Output:

warrior 2,warrior 6,[pop-up 1],[pop-up 2],juggernaut 0,juggernaut 4,
juggernaut 7,goblin 1,goblin 3,goblin 5,"stamina: 10,000","game over"

This rendering loop differs from the non-restituting one in two aspects:

Internally, boost::poly_collection::for_each checks for each segment if its type, say T, belongs in the type restitution list: if this is the case, the lambda function is passed a const T& rather than the generic const boost::any_collection::value_type&. For each restituted type we are saving indirection calls and possibly getting inlining optimizations, etc. As we see in the performance section, the speedup can be very significant.

Type restitution works equally for the rest of collections of Boost.PolyCollection. When using boost::base_collection, though, the case of improved performance is more tricky:

const char* comma="";
boost::poly_collection::for_each<warrior,juggernaut,goblin>(
  c.begin(),c.end(),[&](const auto& s){
    std::cout<<comma;
    s.render(std::cout);
    comma=",";
  });
std::cout<<"\n";

The problem here is that, even though the argument to the lambda function will be restituted (when appropriate) to warrior&, juggernaut& or goblin&, using it still involves doing a virtual function call in s.render(std::cout). Whether this call is resolved to a non-virtual one depends on the quality of implementation of the compiler: