Boost 1.65 adds type-segmented polymorphic containers

A vector of pointers keeps the pointers together, but the objects they point to can be scattered throughout memory. For a program that repeatedly traverses polymorphic objects, this distinction affects the cost of every pass. The new Boost.PolyCollection library in Boost 1.65.0, released on August 21, changes how those objects are stored. It groups objects of each concrete type into a contiguous segment and traverses the segments in turn.

Joaquín M López Muñoz's library uses information that a conventional container of base pointers discards at insertion. The concrete type is often known when an object enters the container, even though subsequent code accesses it through an abstract interface. Preserving that information lets the container choose storage appropriate to the actual object. The resulting layout requires the application to accept an iteration order determined by type grouping.

I find this a useful addition to C++ because the performance argument is specific enough to inspect. The library introduction identifies memory contiguity and branch prediction as its targets. Both depend on the collection's organisation, so changing the container can address costs that remain even when the individual classes are carefully implemented.

Keeping concrete types at insertion

The library's data structure explanation starts with the familiar arrangement of a vector containing base pointers. Adjacent entries need not point to adjacent objects. A loop that calls a virtual function on each object also encounters a sequence of call targets determined by the mixture of derived types.

PolyCollection maintains a map keyed by pointers to type information, with a separate vector-like segment for each concrete type. Objects of the same type therefore occupy contiguous storage. Traversal visits a run of objects with the same concrete type before moving to another segment. The documentation explains why this arrangement can improve cache behaviour and make the sequence of virtual call targets more predictable.

The base-class version is boost::base_collection<Base>. Objects enter by value through insert, or through emplacement with an explicit concrete type. The versioned tutorial demonstrates it with a hierarchy of game sprites. The essential insertion pattern is small. Given its sprite, warrior and goblin definitions, a collection can be populated and traversed as follows.

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

boost::base_collection<sprite> sprites;
sprites.insert(warrior{0});
sprites.insert(goblin{1});
sprites.insert(warrior{2});

for (const sprite& s : sprites) {
    s.render(std::cout);
}

The container stores the concrete objects, while the loop sees the base interface. The two warriors belong to the same segment despite the intervening goblin insertion. Code must not assume whether that segment appears before or after the goblin segment. The tutorial explicitly warns that segment ordering can differ between environments.

This is why the container has no push_back. Without a position hint, insertion appends within the appropriate type's segment. An application whose processing depends on the global insertion sequence cannot substitute this container without changing that behaviour. For independent operations on a collection of objects, the absence of an ordering requirement makes the layout available as an optimisation.

The factory boundary matters

The connection between insertion and static type information becomes visible when objects arrive through a factory. Inserting a warrior expression gives the container enough information to instantiate storage for warriors. Inserting through a sprite& supplies a different amount of information, even when the referenced object is still a warrior.

Runtime type identification can discover which concrete type the reference denotes. It cannot, by itself, instantiate the templates needed to create a segment for an otherwise unknown class. The tutorial shows a factory returning std::unique_ptr<sprite> and an insertion through the dereferenced result. An initially empty collection throws boost::poly_collection::unregistered_type in that example.

Explicit registration resolves this boundary when the possible concrete types are available to the calling code. The collection's register_types<warrior, juggernaut, goblin>() member establishes the segments before insertion through the base interface. Direct insertion through a reference to the true concrete type registers that type automatically. Registration can persist even after its segment becomes empty.

I am wary of C++ interfaces whose requirements only become apparent after a refactor. This requirement is at least tied to a concrete mechanism. A factory returning the base interface removes static information that the container previously used to build its storage. Registration makes the missing relationship explicit at the point where the application knows its implementations.

Algorithms can use the segments too

Storage layout is only part of the implementation. A whole-collection iterator must detect segment boundaries as it advances. The tutorial explains that a nested traversal over segments and their elements moves the segment-management work outside the inner loop. This reduces the checks repeated for each element.

The library supplies algorithms, including boost::poly_collection::for_each, that use this structure. They accept the collection's ordinary iterators, so callers need not write the nested traversal themselves. This matters most when the operation performed on each object is small enough that iterator overhead accounts for a meaningful portion of the loop.

An optional template argument list enables what the library calls type restitution. For a listed concrete type, an algorithm can pass a reference of that type to a generic callable. Unlisted types still receive processing through the abstract interface. The list supplies optimisation information without restricting the collection to those types.

For base-class polymorphism, a concrete reference does not guarantee that the compiler removes a virtual call. The tutorial distinguishes type restitution from successful devirtualisation and discusses the additional information provided by a final class. The optimisation therefore has several parts whose effects should be understood separately. Contiguous storage does not itself establish that every operation becomes a direct call.

Runtime flexibility affects container operations

The release also provides function_collection for callable objects sharing a signature and any_collection for interfaces expressed through Boost.TypeErasure. These apply the same segmentation approach to forms of polymorphism that do not require a common base class. The library is header-only and requires C++11, according to its release documentation.

Dynamic membership also changes how some invalid operations are reported. A collection can hold a movable, non-copyable object, but copying a collection containing that object throws boost::poly_collection::not_copy_constructible. The compiler cannot reject every such copy in advance because the concrete contents are determined at runtime. Equality comparison can similarly throw not_equality_comparable when it needs an element comparison that the type does not support.

I value the ability to see these costs and restrictions in the container contract. PolyCollection offers a specific option for applications that repeatedly process heterogeneous objects without requiring a chosen global order. Its segment-specific operations also let code reserve capacity or traverse only one concrete type. Reserving capacity applies to individual segments, and a collection-wide reserve request affects the segments that already exist. A type registered later needs its own capacity decision.