Compile-time Data Structures in C++17: Part 2, Map of Types

In part one of the series, we were introduced to a ‘set of types’ – a compile-time data structure where both insertions and lookups are performed during the compilation, rather than in runtime, which gave them ‘O(0)’ complexity. The useful functionality this enabled was a test meta-function (technically, a template variable), returning true during the compilation time if a given tag type was present in the set (and false otherwise). The use case for such a data structure was perhaps not the most convincing if constexpr or a parameter to std::enable_if and std::conditional.

This part of the series starts with a more sophisticated scenario shown in Listing 1.

struct IFuzzer {
  virtual ~IFuzzer() = default;
  virtual std::string fuzz(std::string) const = 0;
};

struct Fuz {};

struct Foo {
  template <typename Map> Foo(Map) {
    if constexpr ((bool)Map::template test<Fuz>)
      fuzz = std::make_unique
             <typename Map::template type<Fuz>>();
  }
  std::unique_ptr<IFuzzer> fuzz;
};

struct Fuzzer : IFuzzer {
  std::string fuzz(std::string n) const override {
    return n + "-fuzz!"; }
};

int main() {
  constexpr static auto m1 = map<>{}
    .insert&lt;Fuz, Fuzzer>();

  const Foo foo {m1};
  std::cout << foo.fuzz->fuzz("Hello")
            << std::endl;
}
            

As we can see, the class Foo is decoupled from any implementation of IFuzzer, and yet it can instantiate it with the help of Map, which performs the necessary mapping with the selector type Fuz, to find the implementation type Fuzzer. The mapping of Fuz to Fuzzer is defined in one place only, inside int main(), which means that we have achieved ‘parametrisation from the above’ with static polymorphism.

The implementation of such a ‘map of types’ is the subject of this article.

What is a ‘selector type’? In a C++ standard library, a selector in std::map<int, std::string> is some value of type int used to select value in a map. In our case, a selector type is just a tag type but used to select something (usually other than itself). Any type can be employed as a selector with the help of overloading, but there are few points to note:

• The result of such performed selection will be the return type of the selected overload. Keyword decltype can be used to deduce this type.
• If we want to do something useful when a match is not found (rather than fail the compilation), a template parameter can be used.
• The functions in the overload set do not need to be defined, as we only care about the return type of the function found by overloading (the actual function never gets called).
• The overload selection should be strengthened against accidental overloading matches, e.g. by implicit type conversion.
• We should avoid instantiating objects of arbitrary types for overloading parameters or return value.

The two last points may seem to contradict the use of overloading until we realise that any type can be made a parameter of a simple ‘wrapper’ template type, and such a template can then be used instead, both for function parameters and their result. An example of such a selection based on type is presented below, in Listing 2.

#include <type_traits>

template <typename T> struct wrap {
  constexpr explicit wrap() = default;
  using type = T;
};

struct Fuz {};
struct Baz {};
struct Bar {};

wrap<double> pair(wrap<Fuz>);
wrap<bool> pair(wrap<Baz>);
template<typename T> wrap<void> pair(wrap<T>);

template <typename T>
using type = typename decltype(pair(wrap<T>{}))::type;

int main() {
  static_assert(std::is_same_v<type<Fuz>,
    double>);
  static_assert(std::is_same_v<type<Baz>, bool>);
  static_assert(std::is_void_v<type<Bar>>);
}
            

The example in Listing 2 has an obvious limitation – selector and return types are both tightly coupled, inside the declarations of overload set pair functions. It does, however, demonstrate the principles. The type template alias instantiates a wrapper class appropriate for the selector type (for example, wrap<Fuz>) and then passes it to the overload set of pair functions. The result of overloading is deduced by the decltype keyword. Since that return type is also a wrapper template, we refer to its type nested alias to unwrap the result type. In this example, we do not do much with the selected type, using the compile-time static_assert only to verify that it is, indeed, the type expected.

The limitation mentioned above can be overcome using the same means as demonstrated in the previous article in the series – building the type of the collection with an insert function, which will create a new type containing both the newly inserted types, and (by means of inheritance) the types of the original collection. The using keyword is used to inject the pair and test overloads of the base types into the scope of the newly created type. See Listing 3.

namespace map_impl {
  template<typename T> struct wrap {
    constexpr explicit wrap() = default;
    using type = T;
  };
  template<typename ...L> struct impl;
  template<> struct impl<> {
    constexpr explicit impl() = default;
    template &lt;typename U&gt;
    constexpr static void pair(wrap&lt;U>) noexcept
    {}

    template &lt;typename U&gt;
  constexpr static bool test(wrap&lt;U>) noexcept {
    return false; }
  };
  template&lt;typename T, typename V, typename ...L&gt;
      struct impl&lt;T, V, L...> : impl&lt;L...> {
    constexpr explicit impl() = default;

    using impl&lt;L...>::pair;
    constexpr static auto pair(wrap&lt;T>) noexcept {
      return wrap&lt;V>(); }

    using impl&lt;L...>::test;
    constexpr static bool test(wrap&lt;T>) noexcept {
      return true; }
  };
}
template &lt;typename ...L&gt; class map {
  using impl = map_impl::impl&lt;L...>;

public:
  constexpr map() = default;

  template &lt;typename T, typename V&gt; constexpr
      auto insert() const noexcept {
    using result = map&lt;std::decay_t&lt;T>,
        std::decay_t&lt;V>, L...>;
      return result();
  }

  template &lt;typename U&gt;
  constexpr static bool test =
    impl::test(map_impl::wrap&lt;U>());

  template &lt;typename U&gt;
  using type = typename
    decltype(impl::pair(map_impl::wrap&lt;U>()))
    ::type;
};
            

While the map of types presented here will suffice for the simple use case presented at the start, it does not fulfil some implied requirements. These are:

• Uniqueness of the selector elements
• Prohibit void as selector type
• Constraints on the type of selector or mapped types.

The first requirement sets the behaviour of our map when a duplicate selector is being used to insert a new element. As opposed to a set of types, we are not going to ignore duplicate elements quietly, but will fail the compilation instead – this is to protect against accidentally hiding existing elements in a map. Reusing a set of types discussed in the first part of the series will help with this requirement, as we can static_assert that the newly inserted selector type is not already present in the set of selectors.

The second requirement needs a short explanation. In the previous part, we defined void as a placeholder for an element when no element is available (an empty set, in other words). However, what should we do with an element which is not there, but something is mapped to it? That makes no sense, hence prohibition. Interestingly, if we employ test from the set of types to enforce the first constraint, it will automatically apply this one as well, because void is considered to be an element of every set (including an empty one). Do we also want to prohibit a void mapped element? Surprisingly, we do not have to – the map of types is perfectly capable of returning a mapped void type, although specific user semantics of a map instance might prohibit it.

This is where the last requirement comes in – it provides us with the semantics of ‘a map of something mapped to something else’ (as opposed to a ‘map of anything’). We are also going to extend the meaning of the constraint to optionally perform transformation of types – this enables the use case where, rather than prohibit e.g. reference types as selectors, the user would rather apply std::decay_t on them. In the previous part, we have already defined a similar constraint for a set of types. We could reuse such a check for a map of types, but we need two (for the selector type T and for the mapped type V). For example, see Listing 4.

template <typename T> struct PlainTypes {
  static_assert(std::is_same_v<T, std::decay_t<T>>);
  static_assert(not std::is_pointer_v<T>);
  using type = T;
};

template <typename T> struct PlainNotVoid {
  static_assert(std::is_same_v<T,
    std::decay_t<T>>);
  static_assert(not std::is_void_v<T>);
  using type = T;
};

int main() {
  constexpr static auto m1 = map<PlainTypes,
     PlainNotVoid> {}
  .insert<Fuz, Fuzzer>();
            

Note, the PlainTypes constraint does not enforce a non-void selector type – as explained above, the test to prohibit duplicate selector types inside the implementation of the map will perform this role. On the other hand, the check for non-void mapped type is implemented in the PlainNotVoid constraint. This is because (as discussed above) this constraint belongs to the domain where the map is used, rather than its inherent limitation. We are passing two parameters to our map, just like std::map requires two parameters. However, in our case the constraints are not independent types – they have no other purpose than to allow the customisation of the semantics of our data structure. This could be a good reason to consider passing a set of both constraints as a single parameter, but we are not going to pursue this path.

Since we are going to reuse ‘a set of types’, we might as well expose it in place of the test meta-function. This avoids the duplication of the functionality of both data structures. Note that because of the dependency on set, Listing 5 requires the reader to copy a large part of Listing 6 from the Part 1 [Kozicki18].

// copy the definition of set in Listing 6 from
// https://accu.org/index.php/journals/2531
// to here
namespace map_impl {
  template<typename T> struct wrap {
    constexpr explicit wrap() = default;
    using type = T;
  };

  template<template <typename> typename CheckT,
    template <typename> typename CheckV,
    typename ...L> struct impl;
  template<template <typename> typename CheckT,
      template <typename> typename CheckV> struct
      impl<CheckT, CheckV> {
    using selectors = set<CheckT>;
    constexpr explicit impl() = default;

    constexpr static void pair() noexcept;
  };

  template<template <typename> typename CheckT,
    template <typename> typename CheckV,
    typename T, typename V, typename ...L>
  struct impl<CheckT, CheckV, T, V, L...>
  : impl<CheckT, CheckV, L...> {
    using check = typename CheckV<V>::type;
    using base = impl<CheckT, CheckV, L...>;
    using selectors =
      typename base::selectors::template insert<T>;
    static_assert(not base::selectors
      ::template test<T>);
    constexpr explicit impl() = default;

    using base::pair;
    constexpr static auto pair(wrap<T>) noexcept {
       return wrap<check>(); }
  };
}

template <template <typename> typename CheckT,
    template <typename> typename CheckV,
    typename ...L> class map {
  using impl = map_impl::impl<CheckT, CheckV,
    L...>;

public:
  constexpr map() = default;

  template <typename T, typename V> constexpr auto
      insert() const noexcept {
    using result = map<CheckT, CheckV, T, V,
      L...>;
    return result();
  }
  using set = typename impl::selectors;
  template <typename U>
  using type = typename
     decltype(impl::pair(map_impl::wrap<U>()))
     ::type;
};

struct IFuzzer {
  virtual ~IFuzzer() = default;
  virtual std::string fuzz(std::string) const = 0;
};

struct Fuz {};

struct Foo {
  template <typename Map> Foo(Map) {
    if constexpr ((bool)Map::set::template
        test<Fuz>) {
      fuzz = std::make_unique<typename
        Map::template type<Fuz>>();
    }
  }

  std::unique_ptr<IFuzzer> fuzz;
};

struct Fuzzer : IFuzzer {
  std::string fuzz(std::string n) const override {
    return n + "-fuzz!"; }
};

template <typename T> struct PlainTypes {
  static_assert(std::is_same_v<T,
    std::decay_t<T>>);
  static_assert(not std::is_pointer_v<T>);
  using type = T;
};

template <typename T> struct PlainNotVoid {
  static_assert(std::is_same_v<T,
    std::decay_t<T>>);
  static_assert(not std::is_void_v<T>);
  using type = T;
};

int main() {
  constexpr static auto m1 = map<PlainTypes,
    PlainNotVoid> {}
  .insert<Fuz, Fuzzer>();

  const Foo foo {m1};
  if (foo.fuzz)
    std::cout << foo.fuzz->fuzz("Hello")
       << std::endl;
  else
    std::cout << "Sad Panda" << std::endl;
}
            

The techniques presented here can be also applied to create a heterogeneous collection of values (as opposed to types), with compile time insertion and extraction of data, for elements supporting such operations (and runtime otherwise). Such collections will be the subject of the next article in the series.

Reference

[Kozicki18] See Listing 6 from https://accu.org/index.php/journals/2531, from the top until the declaration of ‘struct Baz’.

Bronek Kozicki Bronek Kozicki developed his lifelong programming habit at the age of 13, teaching himself Z80 assembler to create special effects on his dad’s ZX Spectrum. BASIC, Pascal, Lisp and a few other languages followed, before he settled on C++ as his career choice. In 2005, he moved from Poland to London, and promptly joined the BSI C++ panel with a secret agenda: to make C++ more like Lisp, but with more angle brackets.