Abstract:

This article by Peter Dimov presents a modern approach to C++ template metaprogramming, demonstrating how C++11 features like variadic templates, parameter packs, and template aliases enable the creation of a simple, powerful, and highly efficient library. The first part establishes a design philosophy centered on generic primitives that operate on any variadic class template (e.g., std::tuple), not just a custom type list. It introduces foundational algorithms like mp_rename and mp_transform and showcases their utility by solving the complex tuple_cat challenge. The author also argues that direct composition of template aliases in C++11 often obviates the need for complex higher-order metaprogramming libraries.

The second part of the article focuses on compile-time performance, systematically replacing slow, recursive algorithms with highly optimized, non-recursive techniques. It introduces several advanced implementation tricks that leverage specific C++ language features for significant performance gains. These include an inheritance-based method using std::is_base_of for near-constant-time set membership testing (mp_contains), a function overload resolution technique for efficient key-value lookups in maps (mp_map_find), and a function-call-based approach for random access in vectors (mp_at).

A Guide to Simple and Performant C++11 Metaprogramming

• C++11 as a Game Changer: The article argues that C++11 features, particularly variadic templates and template aliases (using), fundamentally simplify template metaprogramming. They allow for much cleaner and more direct syntax compared to the boilerplate-heavy typename ... ::type style common in C++03 and libraries like Boost.MPL.
• Generic Primitives: A core design principle is that metaprogramming functions should operate on any variadic template L<T...>, not a specific mp_list type. This allows the library to work directly on standard types like std::tuple and std::pair without requiring costly conversions.
• Fundamental Algorithms: The library is built on simple but powerful primitives.
  • mp_rename: Changes one variadic template type to another (e.g., std::tuple<A, B> to mp_list<A, B>). It is also cleverly used to apply a metafunction to the contents of a list.
  • mp_transform: Applies a given metafunction to the elements of one or more lists. The C++11 implementation is extremely concise due to parameter pack expansion (L<F<T>...>).
• The tuple_cat Challenge: The author demonstrates the library's power by implementing std::tuple_cat. The solution elegantly computes and concatenates inner and outer index lists to construct the final result, showcasing the library's practical utility.
• Avoiding Higher-Order Complexity: The article posits that complex higher-order metaprogramming constructs (like bind or compose libraries) are often unnecessary in C++11. New metafunctions can be easily created by simply defining a new template alias that composes existing ones, e.g., template<class T> using Fgh = F<G<H<T>>>;.
• The Problem of Performance: The second part of the article highlights that naive, recursive implementations of metaprogramming algorithms lead to extremely poor compile times and can easily crash compilers when used with large type lists.
• Efficient Set Operations (mp_contains): To achieve fast membership testing, the article introduces an "inheritance trick." A temporary struct is defined to inherit from a wrapper around each type in the list (struct U: mp_identity<T>... {}). This allows std::is_base_of to perform a near-constant-time check, which is orders of magnitude faster than recursion.
• Efficient Map Operations (mp_map_find): For fast key-value lookups in a map (represented as a list of lists), a "deduction trick" is used. By creating a struct that inherits from all map entries and using an overloaded function, template argument deduction can efficiently find the entry for a given key and return its corresponding value type.
• Efficient Vector Operations (mp_at): To access a type by its index, the most performant solution is to first transform the list into a map of indices to types (e.g., [[0, T0], [1, T1], ...]) and then use the highly efficient mp_map_find algorithm for the lookup.