Inside Boost.PolyCollection

• Introduction
• What’s a polymorphic collection
• Abstracting dynamic polymorphism
• Deeper into poly_collection<Model>
• Segment backend implementations
  • Why split_segment
  • Why not split_hub_segment
• value_type implementations
  • boost::function_[unordered_]collection<Signature>
  • boost::variant_[unordered_]collection_of<Ts...>
• value_holder
• Type-erased segment iteration
• Conclusions

Introduction

Boost.PolyCollection was released in Boost 1.64 (2017). Starting in Boost 1.93 (scheduled for Dec 2026), the library introduces unordered polymorphic collections, which provide iterator/reference stability at the cost of some loss in performance with respect to the existing ordered collections.

Boost.PolyCollection’s internal design has proven robust over the years as new collections were added. We will describe this design in some detail, both as a maintenance aid and for those readers curious about the concepts and techniques involved in writing a library that connects static and dynamic polymorphism in mildly interesting ways.

The article assumes that the reader has some user-level familiarity with Boost.PolyCollection.

What’s a polymorphic collection

STL and STL-like containers, implemented as class templates parameterized over their element type, are not directly suitable for polymorphic values (like objects in a virtual class hierarchy with top class Base): the most obvious reason for this is that such containers assume that value_type objects have value semantics, which implies, among other things, that all permissible values have the same size (namely sizeof(value_type)). This mismatch is typically resolved by resorting to containers of pointers (e.g. std::vector<std::unique_ptr<Base>>) or using wrappers that emulate value semantics on top of the polymorphic entities (like C++26 std::polymorphic). Neither solution is completely transparent in terms of the resulting user interface, and both result in notoriously bad performance since each element is allocated individually.

The key insight behind Boost.PolyCollection is that many times the exact type of an element is known at compile time at or around the point of insertion:

std::vector<std::unique_ptr<Base>> c;
c.push_back(std::make_unique<Derived>(...));

In the example, c receives a pointer to Base, but the user explicitly created a Derived object, which gets immediately type-erased to accomodate the container’s interface. Consider now:

boost::base_collection<Base> c;
c.insert(Derived{...});

Here, c is passed a Derived object directly, which can then be type-erased internally and handled as before. But, crucially, this interface allows for boost::base_collection to capture the type Derived at compile time and use that information to implement a more efficient data structure than a plain vector of pointers.

boost::base_collection accepts elements by reference (not by type-erased pointer) and stores them by value in segments dedicated to each concrete derived type. The resulting data structure is much more efficient than a vector of pointers because 1) it avoids per-element allocation and 2) element grouping by type increases cache locality dramatically and helps branch prediction through virtual calls when doing whole-container iteration and processing. We have analyzed the performance gains in a previous article.

So, the defining aspect of polymorphic collections is that they present a value-oriented interface and do the required type erasure internally. One downside is that they can’t always accept a type-erased object:

boost::base_collection<Base> c;
const Base& x = Derived{};
c.insert(x); // throws boost::poly_collection::unregistered_type

Since c does not know about Derived (technically, no member function template dependent on Derived has been instantiated and invoked before the point of insertion), there is no way it can create the dedicated segment. In these cases, explicit type registration is required:

boost::base_collection<Base> c;
c.register_types<Derived>(); // creates dedicated (empty) segment
const Base& x = Derived{};   
c.insert(x);                 // works OK

Abstracting dynamic polymorphism

Classical OOP is the most obvious runtime polymorphism model, but by no means the only one. For instance:

• std::function<Signature>, a type-erasing wrapper over callable objects, allows for different Signature-compatible entities to be treated in an unified way.
• Libraries like Boost.TypeErasure, Dyno, AnyAny or Typeclasses all provide OOP-like capabilities without requiring interface-compatible entities to derive from a common abstract base class.
• std::variant and similar utilities can be thought of as implementing a kind of runtime polymorphism where the allowable concrete types form a closed set specified at compile time: a std::variant<T...> object type-erases the contained value and provides a run-time dispatching procedure to handle it (visitation).

The common themes here are type erasure and run-time dispatch to the concrete implementation type. Boost.PolyCollection relies on a generic, metalinguistic definition of a (runtime) polymorphism model. A polymorphism model is:

• A family Interface of permissible interface types and, for each I ∈ Interface, the family Implementation(I) of types satisfying I.
• For a given interface type I, an operation subobject(x) that maps each value of an implementation type to its internally used value y of a possibly different implementation type.

An implementation type is said to be concrete if it is the type of some subobject. The polymorphism model is open if it has an unbounded number of potential concrete types, or closed if the set of concrete types is finite (like with std::variant<Ts...>, where the concrete types are exactly those in Ts...)

The mathematical jargon can look a bit opaque: it may help to see how OOP polymorphism is described within this framework:

• Interface = { Base : std::is_polymorphic_v<Base> }.
• Implementation(Base) = { Derived : std::is_base_of_v<Base,Derived> }.
• subobject(x) = static_cast<Derived&>(x) with typeid(x) == typeid(Derived).

The polymorphism models associated with std::function, Boost.TypeErasure and std::variant can also be formalized analogously. This abstraction allows us to implement all the containers in Boost.PolyCollection with one internal class template poly_collection<Model> just by suitably providing the corresponding polymorphism model codified in C++:

Polymorphism model	Open/ closed	C++ implementation	Polymorphic collections
OOP	open	base_polymorphism	base_collection base_unordered_collection
std::function	open	function_polymorphism	function_collection function_unordered_collection
Boost.TypeErasure	open	any_polymorphism	any_collection any_unordered_collection
std::variant	closed	variant_polymorphism	variant_collection variant_unordered_collection

poly_collection<Model> gives closed models special treatment by registering all implementation types at construction time, thus rendering register_types unneeded.

NB: The type Model in poly_collection<Model> not only contains information about the polymorphism model, but also specifies other aspects related to how elements are to be stored —we call this part the storage model. For instance, base_model (used for boost::base_collection) and base_unordered_model (boost::base_unordered_collection) are different, but they both derive from base_polymorphism.

Deeper into poly_collection<Model>

The core of poly_collection<Model> is a segment map from type descriptors to segment_types, where segment_type is the class in charge of the segment for a particular concrete type. For open collections, concrete types are described by their typeid, and the segment map is roughly an std::unordered_map<std::type_index, segment_type>. For closed collections, the type descriptor is a simple integer, and the associated segment map is based on std::vector<segment_type>.

There are two possible implementations of segment_type: segment<Model> for ordered collections and unordered_segment<Model> for unordered ones. These two classes are not related by inheritance and their interfaces are different; poly_collection<Model> interoperates with them generically by appropriately SFINAEing on the ordered/unordered attribute of the model. Their shape and behavior, however, are similar, so we will describe segment<Model> only.

template<typename Model>
class segment
{
public:
  using value_type = typename Model::value_type;
  using allocator_type = typename Model::segment_allocator_type;
  // other types coming from Model

  // construction
  template<typename Concrete>
  static segment make(const allocator_type& al);

  // value semantics: copy ctor, assignment, etc.
  ...

  // container-like interface
  ...
  template<typename T>
  base_iterator push_back(T&& x);

  template<typename Concrete, typename... Args>
  base_iterator emplace_back(Args&&... args)
  ...

private:
  using segment_backend = typename Model::segment_backend;
  template<typename Concrete>
  using segment_backend_implementation=typename Model::
    template segment_backend_implementation<Concrete>;
  ...
  std::unique_ptr<segment_backend> pimpl;
};

Note that a segment in charge of some Concrete type (created with segment<Model>::make<Concrete>(al)) does not contain Concrete as part of its type, so this information has to be type-erased somehow. We use a technique popularized by Sean Parent (see slides 157-205 of his 2013 “C++ Seasoning” presentation) which lies at the core of many C++ type erasure libraries (and which, to the best of our knowledge, unfortunately lacks a standard name):

• The core functionality of the segment is defined by a virtual interface (class segment_backend<StorageModel>).
• For any Concrete type, segment_backend_implementation<Concrete> provides an implementation of segment_backend (i.e., derives from segment_backend) specialized to handle a segment of Concrete values.
• make<Concrete>(al) dynamically allocates and constructs a segment_backend_implementation<Concrete> and type-erases it into a pimpl member of type std::unique_ptr<segment_backend>.
• Public member functions are not virtual, but they typically delegate to an internal virtual call over pimpl (for instance, segment::push_back(x) resolves to pimpl->push_back(p), where p is the type-erased address of x’s subobject).

In some cases poly_collection<Model> knows statically the exact Concrete type of the target segment. For instance, the operation poly_collection::emplace<Derived>(args...) finds the segment s in charge of Derived and executes s.emplace_back<Derived>(std::forward<Args>(args)...). s, which has type-erased Derived, is passed this same type back as part of the call, so, instead of relying on the virtual segment_backend interface offered by pimpl, it does (roughly) the following:

template<typename Concrete, typename... Args>
base_iterator emplace_back(Args&&... args)
{
  auto& restored = 
    static_cast<segment_backend_implementation<Concrete>&>(*pimpl);
  return restored.nv_emplace_back(std::forward<Args>(args)...));
}

where nv_emplace_back is a non-virtual member function of segment_backend_implementation (that is, not part of the virtual interface of its base class segment_backend). This idiom can be regarded as a performance optimization, and in fact it is used as such in many cases throughout the implementation of poly_collection<Model>, but in the particular case of emplace it is essential: emplacing from a variadic pack of arguments can’t be served by segment_backend’s virtual interface (in short, there are no virtual member function templates in C++).

Segment backend implementations

Three different implementations are used:

• packed_segment<StorageModel, Concrete> (derived from segment_backend<StorageModel>): Used for boost::base_collection and boost::variant_collection, where a value_type object and its Concrete subobject are stored in the same memory region: this is obvious in the case of boost::base_collection; for boost::variant_collection, see the dedicated section. packed_segment stores its same-sized Concrete-containing objects contiguously in a std::vector.

• split_segment<StorageModel, Concrete> (derived from segment_backend<StorageModel>): Used for boost::function_collection and boost::any_collection, where value_type is a wrapper pointing to an external Concrete value. split_segment maintains two std::vectors, one (the index) with the value_type objects and the other (the store) with their Concrete pointees, and keeps both in sync.

   

• packed_hub_segment<StorageModel, Concrete> (derived from unordered_segment_backend<StorageModel>): Used for all unordered collections. Analogous to packed_segment, except that a boost::container::hub is used to store the elements instead of a std::vector. The use of packed_hub_segment is exactly what allows unordered polymorphic collections to provide iterator/reference stability (at the expense of losing the ability to control intrasegment insertion positioning).

Why split_segment

There’s no technical reason why boost::function_collection and boost::any_collection couldn’t have used packed_segment as their segment backend implementation: it would only require that the value_type wrappers and their Concrete pointees be stored adjacently (as boost::function_unordered_collection and boost::any_unordered_collection do to use packed_hub_segment). Benchmarks during the development phase showed, however, that split_segment was generally faster, most likely due to better cache locality.

Why not split_hub_segment

Polymorphic collections provide two types of local iterators to a given segment: local_iterator<Concrete> refers to the concrete type, and local_base_iterator is a type-erased version of the former (that is, it refers to the collection’s value_type). These two types of iterators are specified to be interconvertible. In the case of split_segment, local_iterators point to the store vector and local_base_iterators to the index vector. local_base_iterator → local_iterator<Concrete> is trivial, since value_type is a wrapper class pointing to the Concrete value, whereas local_iterator<Concrete> → local_base_iterator is implemented in constant time as:

lbit = index.begin() + (lit - store.begin());

The difficulty with a hypothetical split_hub_segment lies in the fact that this convertibility technique would not be constant time because boost::container::hub iterators are not random access.

value_type implementations

Obviously, boost::base_[unordered_]collection<Base>::value_type is Base. What about the other polymorphic collections? boost::any_[unordered_]collection<Concept>, which rely on Boost.TypeErasure, define their value_type as boost::type_erasure::any<Concept2, boost::type_erasure::_self&>, where the unspecified Concept2 subsumes Concept and the & in boost::type_erasure::_self& indicates that the wrapped entity is external. The case for the remaining polymorphic collections is more interesting.

boost::function_[unordered_]collection<Signature>

These collections couldn’t have used std::function<Signature> because std::function allocates dynamic memory for its owned wrapped entity, thus defeating Boost.PolyCollection’s primary goal of storing concrete values together. Passing SBO-compatible std::reference_wrappers to std::function or using C++26 std::function_ref would be tantalizingly close to working, but there is a fundamental blocker: Boost.PolyCollection internally requires that a type-erased void* to the concrete value can be obtained from its associated value_type without knowing the concrete type, and there is no way to do that with any of the callable wrappers in the C++ standard library. Ultimately, Boost.PolyCollection uses its own callable_wrapper with a suitable data() accessor.

On a note unrelated to Boost.PolyCollection, it is surprising that std::function and its variations don’t provide a void* data() member function or similar functionality. std::function::target requires that the target type be passed, whereas std::move_only_function, std::copyable_function and std::function_ref don’t even provide target (seemingly to remove internal dependencies on RTTI support). In our opinion, such capability becomes essential or extremely useful in advanced scenarios involving multilayered designs, serialization, etc. For what it’s worth, C++ virtual classes provide this functionality (dynamic_cast<void*>).

boost::variant_[unordered_]collection_of<Ts...>

Barring some minor difficulties, std::variant<Ts...> (or boost::variant2::variant<Ts...>) could have served as the value_type for these collections, but this would have resulted in annoying inefficiencies: as sizeof(std::variant<Ts...>) is fixed and greater than max{sizeof(Ts)...}, the segment for, say, char in a boost::variant_collection_of<char, double> would take as much memory as the segment for double (for the same number of elements), when we obviously can do better.

fixed_variant<Ts...> is mostly a reimplementation of std::variant (taking inspiration and extra functionality from boost::variant2::variant) with the following differences:

• A fixed_variant<Ts...> can’t be assigned a different alternative type (standard parlance for “any of Ts...”), or in fact any value of any alternative type, after construction (hence the fixed_ prefix). This behavior is exactly what Boost.PolyCollection needs: variants with the same alternative type go to the same segment, so the user shouldn’t be able to break this invariant.
• A fixed_variant object v assumes that its contained value (of the appropriate alternative type) is stored adjacently to and before v. In this sense, fixed_variant is an “abstract” type that can only be meaningfully constructed as part of a “derived” class including the required alternative value. This is implemented internally with a fixed_variant_closure<T, fixed_variant<Ts...>> (T ∈ Ts...). So, the segment for Ti is a packed_segment/packed_hub_segment over a std::vector/boost::container::hub of fixed_variant_closure<Ti, fixed_variant<Ts...>>s.

value_holder

In our simplified explanation of segment backend implementations, it was implied that Concrete values are inserted directly in the corresponding data structure. Actually, the values stored are of type value_holder<Concrete>. value_holder serves several purposes, but the most interesting one is that it turns compile-time constraints into run-time exceptions. For instance, value_holder<Concrete> is always copy constructible even if Concrete is not: when that is the case and copy construction is invoked, value_holder throws boost::poly_collection::not_copy_constructible. The reason we do this is that we don’t want to block a non-copy-constructible Concrete at compile time because most of the collection’s interface does not actually require copy constructibility. This is not an issue with static STL containers, where an operation imposing such a requirement is instantiated and checked only when used. In our case, however, type erasure is involved and the segment backend must expose the operation regardless of the concrete type stored behind it, so an unsupported operation can only be diagnosed at run time.

Type-erased segment iteration

Iteration with global iterators or local_base_iterators involves traversing segments whose concrete type is not known at compile time. This is simple to do when segments are implemented with packed_segment, which works over a plain std::vector: stride_iterator takes a type-erased pointer and a stride value (how many bytes there are between the address of a concrete value and the next), and iteration (random access, actually) is trivially implemented from there. Type-erased iteration with split_segment is also trivial (proxy_iterator is a simple value_type* wrapper ranging over the segment’s index vector).

The challenge comes with boost::unordered::hub, used by packed_hub_segment. This container’s data structure is officially unspecified and technically inaccessible (we don’t have a data member function like with std::vector). There are two possible ways to implement type-erased iteration in this scenario:

1. Define a virtual interface for iteration and implement it via internal delegation to a boost::container::hub::iterator.
2. Break boost::container::hubs encapsulation and handle its internal data structure directly.

The first alternative is of course unacceptably costly: each operation on the type-erased iterator would incur a virtual call. So, we can only resort to the second option: stride_hub_iterator knows how to access boost::container::hub::iterator’s internal members and uses those to navigate the container’s data structure in a manner functionally equivalent to that of stride_iterator. This, unfortunately, creates a private implementation-level coupling between Boost.PolyCollection and Boost.Container.

With the notable exception of containers exposing contiguous storage (std::vector, std::array, etc.), STL’s design, based around strongly-typed components, does not lend itself to type-erased iteration/access in general. Curiously enough, C libraries such as GLib typically provide type-erased data structures, and it is the user who has to restore the types at information access time.

Conclusions

Runtime polymorphism is an umbrella term for a number of conceptually related paradigms. A common formalization of these paradigms allows Boost.PolyCollection to support different kinds of collections by instantiating the same core implementation with different polymorphism model specifications; extending this parametrization to the underlying storage allows the same machinery to support both ordered and unordered variants.

The library also shows how the static framework provided by the STL can be extended to a hybrid static/dynamic setting that performs run-time dispatch while retaining as much static efficiency as possible.

We have explored a number of techniques that may be of interest beyond the scope of Boost.PolyCollection: hidden type erasure through encapsulated virtual interfaces, restitution of type-erased information for efficiency or to support unvirtualizable interfaces, turning compile-time constraints into run-time exceptions, and efficient type-erased access to data structures.

There’s one area of Boost.PolyCollection we haven’t covered: specialized versions of standard algorithms for polymorphic collections. This could be the subject of a future article.