Boost C++ Libraries Home Libraries People FAQ More

PrevUpHomeNext

An efficient polymorphic data structure

Suppose we have a base abstract class with implementations derived1, derived2 and derived3. The memory layout of a std::vector<base*> (or similar constructs such as std::vector<std::unique_ptr<base>> or boost::ptr_vector<base>) looks like the following:

Elements that are adjacent in the vector are not necessarily allocated contiguously, much less so if the vector has undergone mid insertions and deletions. A typical processing operation

std::vector<base*> v;
...
for(base* b: v){
  ... // access base's virtual interface
}

is impacted negatively by two factors:

These limitations are imposed by the very nature of dynamic polymorphism: as the exact types of the elements accessed through base's interface are not known, an indirection through base* (a particular form of type erasure) is required. There is however a critical observation: even though derived types are not known when traversing a std::vector<base*>, the information is typically available at compile time at the point of insertion in the vector:

std::vector<base*> v;
...
v.insert(new derived2{...}); // the type derived2 is "forgotten" by v

A suitably designed container can take advantage of this information to arrange elements contiguously according to their exact type, which results in an internal data structure (a map of pointers to std::type_info objects, actually) pointing to as many vectors or segments as there are derived classes:

Traversing such a structure reduces to looping over all the segments one after another: this is extremely efficient both in terms of caching and branch prediction. In the process we have however lost the free-order capability of a std::vector<base*> (free order can only be retained at the segment level), but if this is not relevant to the user application the potential performance gains of switching to this structure are large.

The discussion has focused on base/derived programming, also known as OOP, but it also applies to other forms of dynamic polymorphism:

Boost.PolyCollection provides three different container class templates dealing with OOP, std::function-like polymorphism and duck typing as implemented by Boost.TypeErasure:

The interfaces of these containers are mostly the same and follow the usual conventions of standard library containers.


PrevUpHomeNext