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.65 (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 accommodate 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::container::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.

Boost.MultiIndex refactored

Boost.MultiIndex was launched as part of Boost 1.32 in November 2004. The library is still actively maintained and in use by some notable projects such as BitcoinCore, CERN ATLAS, ClickHouse, Folly and Redpanda, to name a few.

Back in 2004, variadic templates and typelists were emulated in C++03 with the help of libraries like Boost.Preprocessor and Boost.MPL. These libraries were ground breaking at the time but they have been largely obsoleted by language features available since C++11. Given that Boost.MultiIndex is no longer usable in C++03 (some internal dependencies have moved in the last few years to requiring C++11 as a minimum), it was about time to give the library an upgrade.

Starting in Boost 1.91 (target date April 2026), all the internal machinery of Boost.MultiIndex dependent on Boost.Preprocessor and Boost.MPL is refactored to use C++11 variadic templates and Boost.Mp11:

• All type lists accepted or provided by the library (indexed_by, tag, nested typedefs index_specifier_type_list, index_type_list, iterator_type_list and const_iterator_type_list) are no longer based on Boost.MPL but instead they are now Boost.Mp11 lists.
• composite_key and associated class templates (composite_key_equal_to, composite_key_compare, composite_key_hash) have been made truly variadic (previously the maximum number of template arguments was limited by the macro BOOST_MULTI_INDEX_LIMIT_COMPOSITE_KEY_SIZE). 

The upgrade should be transparent to end users in the overwhelming majority of cases, although we discuss some potential backwards compatibility issues later.

Reduction in lengths of type and symbol names

Consider:

using namespace boost::multi_index;

struct element
{
  int x, y;
};

using container = multi_index_container<
  element,
  indexed_by<
    random_access<tag<struct i0>>,
    ordered_unique<tag<struct i1>, key<&element::x, &element::y>>
  >
>;

container c;
auto&     idx = c.get<0>(); // first index of the container

Prior to Boost 1.91, typeid(c).name() and typeid(idx).name() were the following in Visual Studio (after formatting):

class boost::multi_index::multi_index_container<
  struct element,
  struct boost::multi_index::indexed_by<
    struct boost::multi_index::random_access<
      struct boost::multi_index::tag<
        struct i0,
        struct boost::mpl::na, struct boost::mpl::na, struct boost::mpl::na,
        struct boost::mpl::na, struct boost::mpl::na, struct boost::mpl::na,
        struct boost::mpl::na, struct boost::mpl::na, struct boost::mpl::na,
        struct boost::mpl::na, struct boost::mpl::na, struct boost::mpl::na,
        struct boost::mpl::na, struct boost::mpl::na, struct boost::mpl::na,
        struct boost::mpl::na, struct boost::mpl::na, struct boost::mpl::na,
        struct boost::mpl::na
      >
    >,
    struct boost::multi_index::ordered_unique<
      struct boost::multi_index::tag<
        struct i1,
        struct boost::mpl::na, struct boost::mpl::na, struct boost::mpl::na,
        struct boost::mpl::na, struct boost::mpl::na, struct boost::mpl::na,
        struct boost::mpl::na, struct boost::mpl::na, struct boost::mpl::na,
        struct boost::mpl::na, struct boost::mpl::na, struct boost::mpl::na,
        struct boost::mpl::na, struct boost::mpl::na, struct boost::mpl::na,
        struct boost::mpl::na, struct boost::mpl::na, struct boost::mpl::na,
        struct boost::mpl::na
      >,
      struct boost::multi_index::composite_key<
        struct element,
        struct boost::multi_index::member<struct element, int, 0>,
        struct boost::multi_index::member<struct element, int, 4>,
        struct boost::tuples::null_type, struct boost::tuples::null_type,
        struct boost::tuples::null_type, struct boost::tuples::null_type,
        struct boost::tuples::null_type, struct boost::tuples::null_type,
        struct boost::tuples::null_type, struct boost::tuples::null_type
      >,
      struct boost::mpl::na
    >,
    struct boost::mpl::na, struct boost::mpl::na, struct boost::mpl::na,
    struct boost::mpl::na, struct boost::mpl::na, struct boost::mpl::na,
    struct boost::mpl::na, struct boost::mpl::na, struct boost::mpl::na,
    struct boost::mpl::na, struct boost::mpl::na, struct boost::mpl::na,
    struct boost::mpl::na, struct boost::mpl::na, struct boost::mpl::na,
    struct boost::mpl::na, struct boost::mpl::na, struct boost::mpl::na
  >,
  class std::allocator<struct element>
>

class boost::multi_index::detail::random_access_index<
  struct boost::multi_index::detail::nth_layer<
    1,
    struct element,
    struct boost::multi_index::indexed_by<
      struct boost::multi_index::random_access<
        struct boost::multi_index::tag<
          struct i0,
          struct boost::mpl::na, struct boost::mpl::na, struct boost::mpl::na,
          struct boost::mpl::na, struct boost::mpl::na, struct boost::mpl::na,
          struct boost::mpl::na, struct boost::mpl::na, struct boost::mpl::na,
          struct boost::mpl::na, struct boost::mpl::na, struct boost::mpl::na,
          struct boost::mpl::na, struct boost::mpl::na, struct boost::mpl::na,
          struct boost::mpl::na, struct boost::mpl::na, struct boost::mpl::na,
          struct boost::mpl::na
        >
      >,
      struct boost::multi_index::ordered_unique<
        struct boost::multi_index::tag<
          struct i1,
          struct boost::mpl::na, struct boost::mpl::na, struct boost::mpl::na,
          struct boost::mpl::na, struct boost::mpl::na, struct boost::mpl::na,
          struct boost::mpl::na, struct boost::mpl::na, struct boost::mpl::na,
          struct boost::mpl::na, struct boost::mpl::na, struct boost::mpl::na,
          struct boost::mpl::na, struct boost::mpl::na, struct boost::mpl::na,
          struct boost::mpl::na, struct boost::mpl::na, struct boost::mpl::na,
          struct boost::mpl::na
        >,
        struct boost::multi_index::composite_key<
          struct element,
          struct boost::multi_index::member<struct element, int, 0>,
          struct boost::multi_index::member<struct element, int, 4>,
          struct boost::tuples::null_type, struct boost::tuples::null_type,
          struct boost::tuples::null_type, struct boost::tuples::null_type,
          struct boost::tuples::null_type, struct boost::tuples::null_type,
          struct boost::tuples::null_type, struct boost::tuples::null_type
        >,
        struct boost::mpl::na
      >,
      struct boost::mpl::na, struct boost::mpl::na, struct boost::mpl::na,
      struct boost::mpl::na, struct boost::mpl::na, struct boost::mpl::na,
      struct boost::mpl::na, struct boost::mpl::na, struct boost::mpl::na,
      struct boost::mpl::na, struct boost::mpl::na, struct boost::mpl::na,
      struct boost::mpl::na, struct boost::mpl::na, struct boost::mpl::na,
      struct boost::mpl::na, struct boost::mpl::na, struct boost::mpl::na
    >,
    class std::allocator<struct element>
  >,
  struct boost::mpl::vector1<struct i0>
>

Those many boost::mpl::nas are default template arguments used by Boost.MPL to emulate variadic class templates; similarly, boost::tuples::null_type is the default argument for non-variadic boost::tuple. With the upgrade, the corresponding type names are: 

class boost::multi_index::multi_index_container<
  struct element,
  struct boost::multi_index::indexed_by<
    struct boost::multi_index::random_access<
      struct boost::multi_index::tag<struct i0>
    >,
    struct boost::multi_index::ordered_unique<
      struct boost::multi_index::tag<struct i1>,
      struct boost::multi_index::composite_key<
        struct element,
        struct boost::multi_index::member<struct element, int, 0>,
        struct boost::multi_index::member<struct element, int, 4>
      >,
      void
    >
  >,
  class std::allocator<struct element>
>

class boost::multi_index::detail::random_access_index<
  struct boost::multi_index::detail::nth_layer<
    1,
    struct element,
    struct boost::multi_index::indexed_by<
      struct boost::multi_index::random_access<
        struct boost::multi_index::tag<struct i0>
      >,
      struct boost::multi_index::ordered_unique<
        struct boost::multi_index::tag<struct i1>,
        struct boost::multi_index::composite_key<
          struct element,
          struct boost::multi_index::member<struct element, int, 0>,
          struct boost::multi_index::member<struct element, int, 4>
        >,
        void
      >
    >,
    class std::allocator<struct element>
  >,
  struct boost::multi_index::tag<struct i0>
>

Terser type names are beneficial when inspecting compile error messages related to the use of the library. Internal symbol names are also drastically reduced, which can improve compile and link times.

Faster compilation

We have measured compile times for a synthetic example program using Boost.MultiIndex 1.90 and the upcoming 1.91 version under Clang 20, GCC 15 and Visual Studio 2022 (benchmark setup here). The new version is faster in all three compilers by around 20% (Clang 1.19x, GCC 1.25x, Visual Studio 1.20x). Your mileage of course may vary.

Backwards compatibility

We foresee that most existing users of Boost.MultiIndex won't be affected by the upgrade beyond the collateral benefits described above. Some changes to user code may be needed, though, in rare situations:

• If you were using Boost.MPL to synthezise or analyze the typelists featured in the library, your code will stop working as these are now Boost.Mp11 lists. If you are not in a position to do the necessary changes, the old Boost.MPL-based frontend can be restored by globally defining the macro BOOST_MULTI_INDEX_ENABLE_MPL_SUPPORT.
• composite_key::key_extractors returns a std::tuple instead of a boost::tuple (and similarly for composite_key_equal_to, composite_key_compare and composite_key_hash). This change is needed because boost::tuple has a limit on the number of arguments it accepts, which is no longer the case for composite_key. If you're using key_extractors, chances are you may need to modify your code (for instance, std::tuple does not provide member function extractors of the form t.get<N>()).

Call to action

If you're a Boost.MultiIndex user, please test your project with the new version of the library to ensure there won't be any issues with the upgrade; Boost 1.91 will ship in April 2026, so as of this writing there's still plenty of time to fix any detected problem. The simplest way to do the test is to clone the develop branch of boostorg/multi_index and add its include directory to your include list before the path to your local installation of Boost. Please report your results through the usual channels. Thank you!

 

Comparing the run-time performance of Fil-C and ASAN

After the publication of the experiments with Boost.Unordered on Fil-C, some readers asked for a comparison of run-time performances between Fil-C and Clang's AddressSanitizer (ASAN).

Warning

Please do not construe this article as implying that Fil-C and ASAN are competing technologies within the same application space. Whereas ASAN is designed to detect bugs resulting in memory access violations, Fil-C sports a stricter notion of memory safety including UB situations where a pointer is directed to a valid memory region that is nonetheless out of bounds with respect to the pointer's provenance. That said, there's some overlapping between both tools, so it's only natural to question about their relative impact on execution times.

Results

Our previous benchmarking repo has been updated to include results for plain Clang 18, Clang 18 with ASAN enabled, and Fil-C v0.674, all with release mode settings. The following figures show execution times in ns per element for Clang/ASAN (solid lines) and Fil-C (dashed lines) for three Boost.Unordered containers (boost::unordered_map,  boost::unordered_flat_map and boost::unordered_node_map) and four scenarios.

Running insertion	Running erasure

Successful lookup	Unsuccessful lookup

In summary:

• Insertion:
  Fil-C is between 1.8x slower and 4.1x faster than ASAN (avg. 1.3x faster).
• Erasure:
  Fil-C is between 1.3x slower and 9.2x faster than ASAN (avg. 1.9x faster).
• Successful lookup:
  Fil-C is between 2.5x slower and 1.9x faster than ASAN (avg. 1.6x slower).
• Unsuccessful lookup:
  Fil-C is between 2.6x slower  and 1.4x faster than ASAN (avg. 1.9x slower).

So, results don't allow us to establish a clear-cut "winner". When allocation/deallocation is involved, Fil-C seems to perform better (except for insertion when the memory working set gets past a certain threshold). For lookup, Fil-C is generally worse, and, again, the gap increases as more memory is used. A deeper analysis would require knowledge of the internals of both tools that I, unfortunately, lack.

(Update Nov 16, 2025) Memory usage

By request, we've measured peak memory usage in GB (as reported by time -v) for the three environments and three scenarios (insertion, erasure, combined successful and unsuccessful lookup) involving five different containers from Boost.Unordered and Abseil, each holding 10M elements. The combination of containers doesn't allow us to discern how closed vs. open addressing affect memory usage overheads in ASAN and Fil-C.

ASAN uses between 2.1x and 2.6x more memory than regular Clang, whereas Fil-C ranges between 1.8x and 3.9x. Results are again a mixed bag. Fil-C performs worst for the erasure scenario, perhaps because of delays in memory reclamation by this technology's embedded garbage collector.

Some experiments with Boost.Unordered on Fil-C

Fil-C is a C and C++ compiler built on top of LLVM that adds run-time memory-safety mechanisms preventing out-of-bounds and use-after-free accesses. This naturally comes at a price in execution time, so I was curious about how much of a penalty that is for a performance-oriented, relatively low-level library like Boost.Unordered.

Compiling and testing

From the user's perspective, Fil-C is basically a Clang clone, so it is fairly easy to integrate in previously existing toolchains. This repo shows how to plug Fil-C into Boost.Unordered's CI, which runs on GitHub Actions and is powered by Boost's own B2 build system. The most straightforward way to make B2 use Fil-C is by having a user-config.jam file like this:

using clang : : fil++ ;

which instructs B2 to use the clang toolset with the only change that the compiler name is not the default clang++ but fil++.

We've encountered only minor difficulties during the process:

•  In the enviroment used (Linux x64), B2 automatically includes --target=x86_64-pc-linux as part of the commandline, which confuses the adapted version of libc++ shipping with Fil-C. This option had to be overridden with --target=x86_64-unknown-linux-gnu (which is the default for Clang).
• As of this writing, Fil-C does not accept inline assembly code (asm or __asm__ blocks), which Boost.Unordered uses to provide embedded GDB pretty-printers. The feature was disabled with the macro BOOST_ALL_NO_EMBEDDED_GDB_SCRIPTS. 

Other than this, the extensive Boost.Unordered test suite compiled and ran successfully, except for some tests involving Boost.Interprocess, which uses inline assembly in some places. CI completed in around 2.5x the time it takes with a regular compiler. It is worth noting that Fil-C happily accepted SSE2 SIMD intrinsics crucially used by Boost.Unordered.

Run-time performance

We ran some performance tests compiled with Fil-C v0.674 on a Linux machine, release settings (benchmark code and setup here). The figures show execution times in ns per element for Clang 15 (solid lines) and Fil-C (dashed lines) and three containers: boost::unordered_map (closed-addressing hashmap), and boost::unordered_flat_map and boost::unordered_node_map (open addressing).

Running insertion	Running erasure

Successful lookup	Unsuccessful lookup

Execution with Fil-C is around 2x-4x slower, with wide variations depending on the benchmarked scenario and container of choice. Closed-addressing boost::unordered_map is the container experiencing the largest degradation, presumably because it does the most amount of pointer chasing.

Bulk operations in Boost.Bloom

Starting in Boost 1.90, Boost.Bloom will provide so-called bulk operations, which, in general, can speed up insertion and lookup by a sizable factor. The key idea behind this optimization is to separate in time the calculation of a position in the Bloom filter's array from its actual access. For instance, if this is the the algorithm for regular insertion into a Bloom filter with k = 1 (all the snippets in this article are simplified, illustrative versions of the actual source code):

void insert(const value_type& x)
{
  auto h = hash(x);
  auto p = position(h);
  set(position, 1);
}

then the bulk-mode variant for insertion of a range of values would look like:

void insert(const std::array<value_type, N>& x)
{
  std::size_t positions[N];
  
  // pipeline position calculation and memory access
  
  for(std::size_t i = 0; i < N; ++i) {
    auto h = hash(x[i]);
    positions[i] = position(h);
    prefetch(positions[i]);
  }
  
  for(std::size_t i = 0; i < N; ++i) {
    set(positions[i], 1);
  }
}

By prefetching the address of positions[i] way in advance of its actual usage in set(positions[i], 1), we make sure that the latter is accessing a cached value and avoid (or minimize) the CPU stalling that would result from reaching out to cold memory. We have studied bulk optimization in more detail in the context of boost::concurrent_flat_map. You can see actual measurements of the performance gains achieved in a dedicated repo; as expected, gains are higher for larger bit arrays not fitting in the lower levels of the CPU's cache hierarchy.

From an algorithmic point of view, the most interesting case is that of lookup operations for k > 1, since the baseline non-bulk procedure is not easily amenable to pipelining:

bool may_contain(const value_type& x)
{ 
  auto h = hash(x);
  for(int i = 0; i < k; ++i) {
    auto p = position(h);
    if(check(position) == false) return false;
    if(i < k - 1) h = next_hash(h);
  }
  return true;
}

This algorithm is branchful and can take anywhere from 1 to k iterations, the latter being the case for elements present in the filter and false positives. For instance, this diagram shows the number of steps taken to look up n = 64 elements on a filter with k = 10 and FPR = 1%, where the successful lookup rate (proportion of looked up elements actually in the filter) is p = 0.1:

As it can be seen, for non-successful lookups may_contain typically stops at the first few positions: the average number of positions checked (grayed cells) is  \[n\left(pk +(1-p)\frac{1-p_b^{k}}{1-p_b}\right),\] where \(p_b=\sqrt[k]{\text{FPR}}\) is the probability that an arbitrary bit in the filter's array is set to 1. In the example used, this results in only 34% of the total nk = 640 positions being checked.

Now, a naïve bulk-mode version could look as follows:

template<typename F>
void may_contain(
  const std::array<value_type, N>& x,
  F f) // f is fed lookup results
{ 
  std::uint64_t hashes[N];
  std::size_t   positions[N];
  bool          results[N];
  
  // initial round of hash calculation and prefetching
  
  for(std::size_t i = 0; i < N; ++i) {
    hashes[i] = hash(x[i]);
    positions[i] = position(hashes[i]);
    results[i] = true;
    prefetch(positions[i]);
  }
  
  // main loop
  
  for(int j = 0; j < k; ++i) {
    for(std::size_t i = 0; i < N; ++i) {
      if(results[i]) { // conditional branch X
        results[i] &= check(positions[i]);
        if(results[i] && j < k - 1) {
          hashes[i] = next_hash(hashes[i]);
          positions[i] = position(hashes[i]);
          prefetch(positions[i]);
        }
      }
    }
  }
  
  // feed results
  
  for(int i = 0; i < k; ++i) {
    f(results[i]);
  }
}

This simply stores partial results in an array and iterates row-first instead of column-first:

The problem with this approach is that, even though it calls check exactly the same number of times as the non-bulk algorithm, the conditional branch labeled X is executed \(nk\) times, and this has a huge impact on the CPU's branch predictor. Conditional branches could in principle be eliminated altogether:

for(int j = 0; j < k; ++i) {
  for(std::size_t i = 0; i < N; ++i) {
    results[i] &= check(positions[i]);
    if(j < k - 1) { // this check is optimized away at compile time
      hashes[i] = next_hash(hashes[i]);
      positions[i] = position(hashes[i]);
      prefetch(positions[i]);
    }
  }
}

but this would result in \(nk\) calls to check for ~3 times more computational work than the non-bulk version.

The challenge then is to reduce the number of iterations on each row to only those positions that still need to be evaluated. This is the solution adopted by Boost.Bloom:

template<typename F>
void may_contain(
  const std::array<value_type, N>& x,
  F f) // f is fed lookup results
{ 
  std::uint64_t hashes[N];
  std::size_t   positions[N];
  std::uint64_t results = 0; // mask of N bits
  
  // initial round of hash calculation and prefetching
  
  for(std::size_t i = 0; i < N; ++i) {
    hashes[i] = hash(x[i]);
    positions[i] = position(hashes[i]);
    results |= 1ull << i;
    prefetch(positions[i]);
  }
  
  // main loop
  
  for(int j = 0; j < k; ++i) {
    auto mask = results;
    if(!mask) break;
    do{
      auto i = std::countr_zero(mask);
      auto b = check(positions[i]);
      results &= ~(std::uint64_t(!b) << i);
      if(j < k - 1) { // this check is optimized away at compile time
        hashes[i] = next_hash(hashes[i]);
        positions[i] = position(hashes[i]);
        prefetch(positions[i]);
      }
      mask &= mask - 1; // reset least significant 1
    } while(mask);
  }
  
  // feed results
  
  for(int i = 0; i < k; ++i) {
    f(results & 1);
    results >>= 1;
  }
}

Instead of an array of partial results, we keep these as a bitmask, so that we can skip groups of terminated columns in constant time using std::countr_zero. For instance, in the 7th row the main loop does 11 iterations instead of n = 64.

In summary, the bulk version of may_contain only does n more conditional branches than the non-bulk version, plus \(n(1-p)\) superfluous memory fetches —the latter could be omitted at the expense of \(n(1-p)\) additional conditional branches, but benchmarks showed that the version with extra memory fetches is actually faster. These are measured speedups of bulk vs. non-bulk lookup for a boost::bloom::filter<int, K> containing 10M elements under GCC, 64-bit mode:

array size	K	p = 1	p = 0	p = 0.1
8M	6	0.78	2.11	1.43
12M	9	1.54	2.27	1.38
16M	11	2.08	2.45	1.46
20M	14	2.24	2.57	1.43

(More results here.)

Conclusions

Boost.Bloom will introduce bulk insertion and lookup capabilities in Boost 1.90, resulting in speedups of up to 3x, though results vary greatly depending on the filter configuration and its size, and may even have less performance than the regular case in some situations. We have shown how bulk lookup is implemented for the case k > 1, where the regular, non-bulk version is highly branched and so not readily amenable to pipelining. The key technique, based on iteration reduction with std::countr_zero, can be applied outside the context of Boost.Bloom to implement efficient pipelining of early-exit operations.

Maps on chains

(From a conversation with Vassil Vassilev.) Suppose we want to have a C++ map where the keys are disjoint, integer intervals of the form [a, b]:

struct interval
{
  int min, max;
};

std::map<interval, std::string> m;

m[{0, 9}] = "ABC";
m[{10, 19}] = "DEF";

This looks easy enough, we just have to write the proper comparison operator for intervals, right?

bool operator<(const interval& x, const interval& y)
{
  return x.max < y.min;
}

But what happens if we try to insert an interval which is not disjoint with those already in the map?

m[{5, 14}] = "GHI"; // intersects both {0, 9} and {10, 19}

The short answer is that this is undefined behavior, but let's try to undertand why. C++ associative containers depend on the comparison function (typically, std::less<Key>) inducing a so-called strict weak ordering on elements of Key. In layman terms, a strict weak order < behaves as the "less than" relationship does for numbers, except that there may be incomparable elements x, y such that x ≮ y and y ≮ x; for numbers, this only happens if x = y, but in the case of a general SWO we allow for distinct, incomparable elements as long as they form equivalence classes. A convenient way to rephrase this condition is to require that incomparable elements are totally equivalent in how they compare to the rest of the elements, that is, they're truly indistinguishable from the point of view of the SWO. Getting back to our interval scenario, we have three possible cases when comparing [a, b] and [c, d]:

• If b < c, the intervals don't overlap and [a, b] < [c, d].
• If d < a, the intervals don't overlap and [c, d] < [a, b].
• Otherwise, the intervals are incomparable. This can happen when [a, b] and [c, d] overlap partially or when they are exactly the same interval.

What we have described is a well known relationship called interval order. The problem is that the interval order is not a strict weak order. Let's depict a Hasse diagram for the interval order on integer intervals [a,b] between 0 and 4:

A Hasse diagram works like this: given two elements x and y, x < y iff there is a path going upwards that connects x to y. For instance, the fact that [1, 1] < [3, 4] is confirmed by the path [1, 1] → [2, 2] → [3, 4]. But the diagram also serves to show why this relationship is not a strict weak order: for it to be so, incomparable elements (those not connected) should be indistinguishable in that they are connected upwards and downwards with the same elements, and this is clearly not the case (in fact, it is not the case for any pair of incomparable elements). In mathematical terms, our relationship is of a more general type called a strict partial order.

Going back to C++, associative containers assume that the elements inserted form a linear arrangement with respect to <: when we try to insert a new element y that is incomparable with some previously inserted element x, the properties of strict weak orders allows us to determine that x and y are equivalent, so nothing breaks up (the insertion fails as a duplicate for a std::map, or y is added next to x for a std::multimap).

There's a way to accommodate our interval scenario with std::map, though. As long as the elements we are inserting belong to the same connecting path or chain, std::map can't possibly "know" if our relationship is a strict weak order or not: it certainly looks like one for the limited subset of elements it has seen so far. Implementation-wise, we just have to make sure we're not comparing partially overlapping intervals:

struct interval_overlap: std::runtime_error
{
  interval_overlap(): std::runtime_error("interval overlap"){}
};

bool operator<(const interval& x, const interval& y)
{
  if(x.min == y.min) {
    if(x.max != y.max) throw interval_overlap();
    return false;
  }
  else if(x.min < y.min) {
    if(x.max >= y.min) throw interval_overlap();
    return true;
  }
  else /* x.min > y.min */
  {
    if(x.min <= y.max) throw interval_overlap();
    return false;
  }
}

std::map<interval, std::string> m;

m[{0, 9}] = "ABC";
m[{10, 19}] = "DEF";
m[{5, 14}] = "GHI"; // throws interval_overlap

So, when we try to insert an element that would violate the strict weak ordering constraints (that is, it lies outside the chain connecting the intervals inserted so far), an exception is thrown and no undefined behavior is hit. A strict reading of the standard would not allow this workaround, as it is required that the comparison object for the map induce a strict weak ordering for all possible values of Key, not only those in the container (or that is my interpretation, at least): for all practical purposes, though, this works and will foreseeably continue to work for all future revisions of the standard.

Bonus point. Thanks to heterogeneous lookup, we can extend our use case to support lookup for integers inside the intervals:

struct less_interval
{
  using is_transparent = void;

  bool operator()(const interval& x, const interval& y) const
  {
    // as operator< before
  }

  bool operator()(int x, const interval& y) const
  {
    return x < y.min;
  }
  
  bool operator()(const interval& x, int y) const
  {
    return x.max < y; 
  }    
};

std::map<interval, std::string, less_interval> m;
  
m[{0, 9}] = "ABC";
m[{10, 19}] = "DEF";

std::cout << m.find(5)->second << "\n"; // prints "ABC"

Exercise for the reader: Can you formally prove that this works? (Hint: define a strict weak order on ℕ ∪ I, where ℕ is the set of natural numbers and I is a collection of disjoint integer intervals.)

WG21, Boost, and the ways of standardization

• Goals of standardization
• Standardizing programming languages
• WG21
• Innovation vs. adoption
• Pros and cons of standardization
• An assessment model for library standardization
• Boost, the standard and beyond
• Golden era: 1998-2011
• Middle-age issues: 2012-2020
• Evolution: 2021-2024 and the future
• Conclusions
  

Goals of standardization

Standardization, in a form resembling our contemporary practices, began in the Industrial Revolution as a means to harmonize incipient mass production and their associated supply chains through the concept of interchangeability of parts. Some early technical standards are the Gribeauval system (1765, artillery pieces) and the British Standard Whitworth (1841, screw threads). Taylorism expanded standardization efforts from machinery to assembly processes themselves with the goal of increasing productivity (and, it could be said, achieving interchangeability of workers). Standards for metric systems, such as that of Revolutionary France (1791) were deemed "scientific" (as befitted the enlightenment spirit of the era) in that they were defined by exact, reproducible methods, but their main motivation was to facilitate local and international trade rather than support the advancement of science. We see a common theme here: standardization normalizes or leverages technology to favor industry and trade, that is, technology precedes standards.

This approach is embraced by 20th century standards organizations (DIN 1917, ANSI 1918, ISO 1947) through the advent of electronics, telecommunications and IT, and up to our days. Technological advancement, or, more generally, innovation (a concept coined around 1940 and ubiquitous today) is not seen as the focus of standardization, even though standards can promote innovation by consolidating advancements and best practices upon which further cycles of innovation can be built —and potentially be standardized in their turn. This interplay between standardization and innovation has been discussed extensively within standards organizations and outside. The old term "interchangeability of parts" has been replaced today by the more abstract concepts of compatibility, interoperability and (within the realm of IT) portability.

Standardizing programming languages

Most programming languages are not officially standardized, but some are. As of today, these are the ISO-standardized languages actively maintained by dedicated working groups within the ISO/IEC JTC1/SC22 subcommittee for programming languages:

• COBOL (WG4)
• Fortran (WG5)
• Ada (WG9)
• C (WG14)
• Prolog (WG17)
• C++ (WG21)
  

What's the purpose of standardizing a programming language? JC22 has a sort of foundational paper which centers on the benefits of portability, understood as both portability across systems/environments and portability of people (a rather blunt allusion to old-school Taylorism). The paper does not mention the subject of implementation certification, which can play a significant role for languages such as Ada that are used in heavily regulated sectors. More importantly to our discussion, it does not either mention what position SC22 holds with respect to innovation: regardless, we will see that innovation does indeed happen within SC22 workgroups, in what represents a radical departure from classical standardization practices.

WG21

C++ was mostly a one man's effort since its inception in the early 80s until the publication of The Annotated C++ Reference Manual (ARM, 1990), which served as the basis for the creation of an ANSI/ISO standardization committee that would eventually release its first C++ standard in 1998. Bjarne Stroustrup cited avoidance of compiler vendor lock-in (a variant of portability) as a major reason for having the language standardized —a concern that made much sense in a scene then dominated by company-owned languages such as Java.

Innovation was seen as WG21's business from its very beginning: some features of the core language, such as templates and exceptions, were labeled as experimental in the ARM, and the first version of the standard library, notably including Alexander Stepanov's STL, was introduced by the committee in the 1990-1998 period with little or no field experience. After a minor update to C++98 in 2003, the innovation pace picked up again in subsequent revisions of the standard (2011, 2014, 2017, 2020, 2023), and the current innovation backlog does not seem to falter; if anything, we could say that the main blocker for innovation within the standard is lack of human resources in WG21 rather than lack of proposals.

Innovation vs. adoption

Not all new features in the C++ standard have originated within WG21. We must distinguish here between the core language and the standard library:

• External innovation in the core language is generally hard as it requires writing or modifying a C++ compiler, a task outside the capabilities of many even though this has been made much more accessible with the emergence of open-source, extensible compiler frameworks such as LLVM. As a result, most innovation activity here happens within WG21, with some notable exceptions like Circle and Cpp2. Others have chosen to depart from the C++ language completely (Carbon, Hylo), so their potential impact on C++ standardization is remote at best.
• As for the standard library, the situation is more varied. These are some examples:
  
• Straight into the standard: <locale>.
  
• Straight into the standard, some prior art: IOStreams, STL, unordered associative containers.
  
• Straight into the standard, extensive prior art: std::string_view.
  
• Explicitly written for standardization, one reference implementation: mdspan.
• Explicitly written for standardization, various reference implementations: ranges, std::expected.
  
• Moderate to high level of prior field experience: Boost.Filesystem, Boost.Regex, Boost.SmartPtr, Boost.Thread, Boost.Tuple.
• Not initially intended for standardization, high level of prior field experience: {fmt}.

In general, the trend for the evolution of the standard library seems to be towards proposing new components straight into the standard with very little field experience.

Pros and cons of standardization

The history of C++ standardization has met with some resounding successes (STL, templates, concurrency, most vocabulary types) as well as failures (exported templates, GC support, exception specifications, std::auto_ptr)  and in-between scenarios (std::regex,  ranges).

Focusing on the standard library, we can identify benefits of standardization vs. having a separate, non-standard component:

• The level of exposure to C++ users increases dramatically. Some companies have bans on the usage of external libraries, and even if no bans are in place, consuming the standard library is much more convenient than having to manage external dependencies —though this is changing.
  
• Standardization ensures a high level of (system) portability, potentially beyond the reach of external library authors without access to exotic environments.
• For components with high interoperability potential (think vocabulary types), having them in the standard library guarantees that they become the tool of choice for API-level module integration.

But there are drawbacks as well that must be taken into consideration:

• The evolution of a library halts or reduces significantly once it is standardized. One major factor for this is WG21's self-imposed restriction to preserve backwards compatibility, and in particular ABI compatibility. For example:
  
• Defects on the API of std::function had to be fixed by adding a new std::copyable_function component.
• Unordered associative containers were specified with the explicit assumption that they should be based on a technique known as separate chaining/closed addressing. The state of the art in this area has evolved spectacularly since 2003, and modern hash table implementations mostly use open addressing, which is de facto forbidden by the standard API, and outperform std::unordered_(map|set) by a large factor.
  

Another factor contributing to library freeze may be the lack of motivation from the authors once they succeed in getting their proposals accepted, as the process involved is very demanding and can last for years.

• Some libraries cover specialized domains that standard library implementors cannot be expected to master. Some cases in point:
• Current implementations of std::regex are notoriously slower than Boost.Regex, a situation aggravated by the need to keep ABI compatibility.
• Correct and efficient implementations of mathematical special functions require ample expertise in the area of numerical computation. As a result, Microsoft standard library implements these as mere wrappers over Boost.Math, and libc++ seems to be following suit. This is technically valid, but begs the question of what the standardization of these functions was useful for to begin with.
• Additions to the upcoming standard (as of this writing, C++26) don't benefit users immediately because the community typically lags behind by two or three revisions of the language.
  

So, standardizing a library component is not always the best course of action for the benefit of current and future users of that component. Back in 2001, Stroustrup remarked that "[p]eople sometime forget that a library doesn't have to be part of the standard to be useful", but, to this day, WG21 does not seem to have formal guidelines as to what constitutes a worthy addition to the standard, or how to engage with the community in a world of ever-expanding and more accessible external libraries. We would like to contribute some modest ideas in that direction.

An assessment model for library standardization

Going back to the basic principles of standards, the main benefits to be derived from standardizing a technology (in our case, a C++ library) are connected to higher compatibility and interoperability as a means to increase overall productivity (assumedly correlated to the level of usage of the library within the community). Leaving aside for the moment the size of the potential target audience, we identify two characteristics of a given library that make it suitable for standardization:

• Its portability requirements, defined as the level of coupling that an optimal implementation has with the underlying OS, CPU architecture, etc. The higher these requirements the more sense it makes to include the library as a mandatory part of the standard.
• Its interoperability potential, that is, how much the library is expected to be used as part of public APIs interconnecting different program modules vs. as a private implementation detail. A library with high interoperability potential is maximally useful when included in the common software "stack" shared by the community.

So, the baseline standardization value of a library, denoted V₀, can be modeled as:

V₀ = aP + bI,

where P denotes the library's portability requirements and I its interoperability potential. The figure shows the baseline standardization value of some library domains within the P-I plane. The color red indicates that this value is low, green that it is high.

A low baseline standardization value for a library does not mean that the library is not useful, but rather that there is little gain to be obtained from standardizing it as opposed to making it available externally. The locations of the exemplified domains in the P-I plane reflect the author's estimation and may differ from that of the reader.

Now, we have seen that the adoption of a library requires some prior field experience, defined as

E = T·U,

where T is the age of the library and U is average number of users.

• When E is very low, the library is not mature enough and standardizing it can result in a defective design that will be much harder to fix within the standard going forward; this effectively decreases the net value of standardization.
  
• On the contrary, if E is very high, which is correlated to the library having already reached its maximum target audience, the benefits of standardization are vanishingly small: most people are already using the library and including it into the official standard has little value added —the library has become a de facto standard.
  

So, we may expect to attain an optimum standardization opportunity S between the extremes E = 0 and E_max.

Finally, the net standardization value of a library is defined as

V = V₀·S·U_max,

where U_max is the library's maximum target audience. Being a conceptual model, the purpose of this framework is not so much to establish a precise evaluation formula as to help stakeholders raise the right questions when considering a library for standardization:

• How high are the library's portability requirements?
• How high its interoperability potential?
• Is it too immature yet? Does it have actual field experience?
  
• Or, on the contrary, has it already reached its maximum target audience?
• How big is this audience?
  

Boost, the standard and beyond

Boost was launched in 1998 upon the idea that "[a] world-wide web site containing a repository of free C++ class libraries would be of great benefit to the C++ community". Serving as a venue for future standardization was mentioned only as a secondary goal, yet very soon many saw the project as a launching pad towards the standard library, a perception that has changed since. We analyze the different stages of this 25+-year-old project in connection with its contributions to the standard and to the community.

Golden era: 1998-2011

In its first 14 years of existence, the project grew from 0 to 113 libraries, for a total uncompressed size of 324 MB. Out of these 113 libraries, 12 would later be included in C++11, typically with modifications (Array, Bind, Chrono, EnableIf, Function, Random, Ref, Regex, SmartPtr, Thread, Tuple, TypeTraits); it may be noted that, even at this initial stage, most Boost libraries were not standardized or meant for standardization. From the point of view of the C++ standard library, however, Boost was the first contributor by far. We may venture some reasons for this success:

• There was much low-hanging fruit in the form of small vocabulary types and obvious utilities.
  
• Maybe due to a combination of scarce competition and sheer luck, Boost positioned itself very quickly as the go-to place for contributing and consuming high-quality C++ libraries. This ensured a great deal of field experience with the project.
  
• Many of the authors of the most relevant libraries were also prominent figures within the C++ community and WG21.
  

Middle-age issues: 2012-2020

By 2020, Boost had reached 164 libraries totaling 717 MB in uncompressed size (so, the size of the average library, including source, tests and documentation, grew by 1.5 with respect to 2011). Five Boost libraries were standardized between C++14 and C++20 (Any, Filesystem, Math/Special Functions, Optional, Variant): all of these, however, were already in existence before 2012, so the rate of successful new contributions from Boost to the standard decreased effectively to zero in this period. There were some additional unsuccessful proposals (Mp11).

The transition of Boost from the initial ramp-up to a more mature stage met with several scale problems that impacted negatively the public perception of the project (and, to some extent that we haven't able to determine, its level of usage). Of particular interest is a public discussion that took place in 2022 on Reddit and touched on several issues more or less recognized within the community of Boost authors:

• The default/advertised way to consume Boost as a monolithic download introduces a bulky, hard to manage dependency on projects.
• B2, Boost's native build technology, is unfamiliar to users more accustomed to widespread tools such as CMake.
• Individual Boost libraries are perceived as bloated in terms of size, internal dependences and compile times. Alternative competing libraries are self-contained, easier to install and smaller as they rely on newer versions of the C++ standard.
• Many useful components are already provided by the standard library.
• There are great differences between libraries in terms of their quality; some libraries are all but abandoned.
• Documentation is not good enough, in particular if compared to cppreference.com, which is regarded as the golden standard in this area.
  

A deeper analysis reveals some root causes for this state of affairs:

• Overall, the Boost project is very conservative and strives not to break users' code on each version upgrade (even though, unlike the standard, backwards API/ABI compatibility is not guaranteed). In particular, many Boost authors are reluctant to increase the minimum C++ standard version required for their libraries. Also, there is no mechanism in place to retire libraries from the project.
• Supporting older versions of the C++ standard locks in some libraries with suboptimal internal dependencies, the most infamous being Boost.MPL, which many identify (with or without reason) as responsible for long compile times and cryptic error messages.
• Boost's distribution and build mechanisms were invented in an era where package managers and build systems were not prevalent. This works well for smaller footprints but presents scaling problems that were not foreseen at the beginning of the project.
• Ultimately, Boost is a federation of libraries with different authors and sensibilities. This fact accounts for the various levels of documentation quality, user support, maintenance, etc.
  

Some of these characteristics are not negative per se, and have in fact resulted in an extremely durable and available service to the C++ community that some may mistakenly take for granted. Supporting "legacy C++" users is, by definition, neglected by WG21, and maintaining libraries that were already standardized is of great value to those who don't live on the edge (and, in the case of the std::regex fiasco, those who do). Confronted with the choice of serving the community today vs. tomorrow (via standardization proposals), the Boost project took, perhaps unplannedly, the first option. This is not to say that all is good with the Boost project, as many of the problems found in 2012-2020 are strictly operational.

Evolution: 2021-2024 and the future

Boost 1.85 (April 2024) contains 176 libraries (7% increase with respect to 2020) and has a size of 731 MB (2% increase). Only one Boost component has partially contributed to the C++23 standard library (boost::container::flat_map), though there has been some unsuccessful proposals (the most notable being Boost.Asio).

In response to the operational problems we have described before, some authors have embarked on a number of improvement and modernization tasks:

• Beginning in Boost 1.82 (Apr 2023), some core libraries announced the upcoming abandonment of C++03 support as part of a plan to reduce code base sizes, maintenance costs, and internal dependencies on "polyfill" components. This initiative has a cascading effect on dependent libraries that is still ongoing.
  
• Alongside C++03 support drop, many libraries have been updated to reduce the number of internal dependencies (that even were, in some cases, cyclic). The figure shows the cumulative histograms of the number of dependencies for Boost libraries in versions 1.66 (2017), 1.75 (2020) and 1.85 (2024):
  

• Official CMake support for the entire Boost project was announced in Oct 2023. This support also allows for downloading and building of individual libraries (and their dependencies).
  
• On the same front of modular consumption, there is work in progress to modularize B2-based library builds, which will enable package managers such as Conan to offer Boost libraries individually. vcpkg already offers this option.
• Starting in July 2023, boost.org includes a search widget indexing the documentation of all libraries. The ongoing MrDocs project seeks to provide a Doxygen-like tool for automatic C++ documentation generation that could eventually support Boost authors  —library docs are currently written more or less manually in a plethora of languages such as raw HTML, Quickbook, Asciidoc, etc. There is a new Boost website in the works scheduled for launch during mid-2024.
  

Where is Boost headed? It must be stressed again that the project is a federation of authors without a central governing authority in strategic matters, so the following should be taken as an interpretation of detected current trends:

• Most of the recently added libraries cover relatively specific application-level domains (networking/database protocols, parsing) or else provide utilities likely to be superseded by future C++ standards, as is the case with reflection (Describe, PFR). One library is a direct backport of a C++17 standard library component (Charconv). Boost.JSON provides yet another solution in an area already rich with alternatives external to the standard library. Boost.LEAF proposes an approach to error handling radically different to that of the latest standard (std::expected). Boost.Scope implements and augment a WG21 proposal currently on hold (<experimental/scope>).
  
• In some cases, standard compatibility has been abandoned to provide faster performance or richer functionality (Container, Unordered, Variant2).
  
• No new library supports C++03, which reduces drastically their number of internal dependencies (except in the case of networking libraries depending on Boost.Asio).
• On the other hand, most new libraries are still conservative in that they only require C++11/14, with some exceptions (Parser and Redis require C++17, Cobalt requires C++20).
• There are some experimental initiatives like the proposal to serve Boost libraries as C++ modules, which has been met with much interest and support from the Visual Studio team. An important appeal of this idea is that it will allow compiler vendors and the committee to obtain field experience from a large, non-trivial codebase.
  

The current focus of Boost seems then to have shifted from standards-bound innovation to higher-level and domain-specific libraries directly available to users of C++11/14 and later. More stress is increasingly being put on maintenance, reduced internal dependencies and modular availability, which further cements the thesis that Boost authors are more concerned about serving the C++ community from Boost itself than eventually migrating to the standard. There is still a flow of ideas from Boost to WG21, but they do not represent the bulk of the project activity.

Conclusions

Traditionally, the role of standardization has been to consolidate previous innovations that have reached maturity so as to maximize their potential for industry vendors and users. In the very specific case of programming languages, and WG21/LEWG in particular, the standards committee has taken on the role of innovator and is pushing the industry rather than adopting external advancements or coexisting with them. This presents some problems related to lack of field experience, limitations to internal evolution imposed by backwards compatibility and an associated workload that may exceed the capacity of the committee. Thanks to open developer platforms (GitHub, GitLab), widespread build systems (CMake) and package managers (Conan, vcpkg), the world of C++ libraries is richer and more available than ever. WG21 could reconsider its role as part of an ecosystem that thrives outside and alongside its own activity. We have proposed a conceptual evaluation model for standardization of C++ libraries that may help in the conversations around these issues. Boost has shifted its focus from being a primary venue for standardization to serving the C++ community (including users of previous versions of the language) through increasingly modular, high level and domain-specific libraries. Hopefully, the availability and reach of the Boost project will help gain much needed field experience that could eventually lead to further collaborations with and contributions to WG21 in a non-preordained way.