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. 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 he 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!