Variadic CRTP template class with a field using constexpr basing on the parameter classes list

Question

I've written (in c++11) a variadic template constexpr function which calculates max sizeof of the parameter types, e.g.:

maxSizeof<int, char, MyType>()

That works correctly. Then I would like to have a variadic template class with a field which is an array of size equal to the maxSizeof(). That should also work correctly:

template <typename... TypesT>
    class Myclass {
        uint8_t field[maxSizeOf<TypesT...>()]
    }

But I also need Myclass to declare methods for each of the parameter types. I've used CRTP for that in following way:

template <typename... TypesT>
class Myclass;

template <>
class Myclass {
    uint8_t field[maxSizeOf<TypesT...>()] // (1) Couldn't do it here as there are no `TypesT`
}

template <typename FirstT, typename... OtherT>
class Myclass<FirstT, OtherT...> : public Myclass<OtherT...> {
    public:
        virtual void doSomething(FirstT object) = 0;
    private:
        uint8_t field[maxSizeOf<FirstT, OtherT...>()] // (2) Shouldn't do it here as it will create field for all of the "middle" classes
}

The question is how implement the declarations of the methods and in the same time have the array field with proper size. (1) and (2) doesn't work for the reasons stated in comments.

Angew is no longer proud of SO · Answer 1 · 2018-09-10T13:51:19.517

6

Like most SW engineering problems, this can be solved by adding more layers of indirection^[1]:

template <typename... TypesT>
class MyclassFunctions;

template <>
class MyclassFunctions
{};

template <typename FirstT, typename... OtherT>
class MyclassFunctions<FirstT, OtherT> : public MyClassFunctions<OtherT...>
{
public:
  virtual void doSomething(FirstT object) = 0;
};

template <typename... TypesT>
class Myclass : public MyclassFunctions<TypesT...>
{
  uint8_t field[maxSizeOf<TypesT...>()]
};

edited Sep 10 '18 at 13:51

answered Sep 10 '18 at 12:20

Angew is no longer proud of SO

167,307
17
350
455

6

"Any problem in computer science can be solved with another level of indirection." https://en.wikipedia.org/wiki/Fundamental_theorem_of_software_engineering – Andriy Tylychko Sep 10 '18 at 12:28
@AndriyTylychko Yes, that's exactly what I was trying to reference; thanks for the link. – Angew is no longer proud of SO Sep 10 '18 at 13:51

Yakk - Adam Nevraumont · Answer 2 · 2018-09-10T14:10:39.227

There are two problems here. The first is getting it to compile. The second is to be able to call doSomething.

The easy solution to the first problem is:

template <class T>
class MyClassFunction {
public:
  virtual void doSomething(T object) = 0;
};


template <typename... TypesT>
class MyClass : public MyClassFunction<TypesT>...
{
  uint8_t field[maxSizeOf<TypesT...>()];
};

this has the disadvantage that calls to doSomething can be hard to do:

prog.cpp:33:59: error: request for member ‘doSomething’ is ambiguous
    using foo = decltype( ((MyClass<int, char>*)nullptr)->doSomething(7) );
                                                          ^~~~~~~~~~~

we need some usings to fix this. In c++17 we could just do:

template <typename... TypesT>
class MyClass : public MyClassFunction<TypesT>...
{
  uint8_t field[maxSizeOf<TypesT...>()];
public:
  using MyClassFunction<TypesT>::doSomething...;
};

but that isn't available in c++11.

To fix this we have to do a tree-based inheritance. The easiest tree-based is linear:

template<class...Ts>
struct MyClassFunctions {};

template<class T0, class T1, class...Ts>
struct MyClassFunctions<T0, T1, Ts...>:
  MyClassFunction<T0>, MyClassFunctions<T1, Ts...>
{
  using MyClassFunction<T0>::doSomething;
  using MyClassFunctions<T1, Ts...>::doSomething;
};
template<class T0>
struct MyClassFunctions:MyClassFunction<T0> {};

template <typename... TypesT>
class MyClass : public MyClassFunctions<TypesT...>
{
  uint8_t field[maxSizeOf<TypesT...>()];
};

Live example.

This has the disadvantage of creating O(n^2) total type name length, which can cause problems for long lists of types. At medium length you get memory bloat and compile time slowdown, at long length you get compilers crashing.

To get around that you can build a binary tree of inheritance. The trick is to be able to split a ... pack in half using log-depth template recursion. Once you have that, the code becomes:

template<class T0, class T1, class...Ts>
struct MyClassFunctions<T0, T1, Ts...>:
  left_half< MyClassFunctions, T0, T1, Ts... >,
  right_half< MyClassFunctions, T0, T1, Ts... >
{
  using left_half< MyClassFunctions, T0, T1, Ts... >::doSomething;
  using right_half< MyClassFunctions, T0, T1, Ts... >::doSomething;
};

however this effort is only worthwhile if you have more than a few dozen types being passed in.

left/right half look like this:

template<template<class...>class Z, class...Ts>
using left_half = /* todo */;
template<template<class...>class Z, class...Ts>
using right_half = /* todo */;

with some crazy metaprogramming in todo.

You can use the indexes trick and the machinery of std::tuple to split those lists (in c++11 log-depth index generation takes a bit of effort). Or you can do an exponential split on the type list.

Write

template<class...Ts>
struct pack {};
template<std::size_t N, class Pack>
struct split/* {
  using lhs = // part before N
  using rhs = // part after N
};

that splits a type list with the first N being on the left. It can be written recursively:

template<std::size_t N, class...Ts>
struct split<N, pack<Ts...>> {
private:
  using half_split = split<N/2, pack<Ts...>>;
  using second_half_split = split<N-N/2, typename half_split::rhs>;
public:
  using lhs = concat< typename half_split::lhs, typename second_half_split::lhs >;
  using rhs = typename second_half_split::rhs;
};
template<class...Ts>
struct split<0, pack<Ts...>> {
  using lhs=pack<>;
  using rhs=pack<Ts...>;
};
template<class T0, class...Ts>
struct split<1, pack<T0, Ts...>> {
  using lhs=pack<T0>;
  using rhs=pack<Ts...>;
};

this requires concat<pack, pack> to do the obvious thing.

Now you need apply<template, pack> and then write left_half and right_half.

score 0 · Answer 3 · answered Sep 10 '18 at 14:55

To sum up Angew answer, and the accessiblity problem pointed out by Yakk, you can reapply the Angew's engineering principle:

template <typename... TypesT>
class MyclassFunctions;

template <>
class MyclassFunctions<>
{};

template <typename FirstT>
class MyclassFunctions<FirstT>
{
public:
  virtual void doSomething(FirstT object){};
};

template <typename FirstT, typename... OtherT>
class MyclassFunctions<FirstT, OtherT...> : public MyclassFunctions<OtherT...>
{
public:
  using MyclassFunctions<OtherT...>::doSomething;
  virtual void doSomething(FirstT object){};
};

template <typename... TypesT>
class Myclass : public MyclassFunctions<TypesT...>
{
  int field[sizeof...(TypesT)];
};

score 0 · Answer 4 · answered Sep 10 '18 at 17:30

One way to do it is to exploit an old trick well known to users of functional programming languages: Recursing on a partial result, e.g. the accumulated maximum as first template parameter. To maintain the Myclass<Ts...> signature, however, we then need to add a level of indirection, as Angew suggested:

template<std::size_t curMax, typename... Ts>
struct MyclassImpl
{
    std::uint8_t field[curMax];
};

template<std::size_t curMax, typename T1, typename... Ts  >
struct MyclassImpl<curMax, T1, Ts...> : MyclassImpl<(curMax > sizeof(T1) ? curMax : sizeof(T1)), Ts...>
{
    virtual void doSomething(T1) = 0;
};

template<typename... Ts>
using Myclass = MyclassImpl<0u, Ts...>;

Let's add a primitive test case (you can also make use of maxSizeof here):

struct TestStruct{ char c[100]; };
using TestMC = Myclass<int, double, TestStruct, short>;
static_assert( sizeof(TestMC::field) == sizeof(TestStruct), "Field size incorrect" );

While this is not better than Angew's version (other than not requiring maxSizeof), it's still a good opportunity to point out this useful recursion pattern. Mostly but not only in pure functional programming languages like Haskell, it is very useful for enabling tail-call optimization, e.g.:

-- slowMax "tail call unfriendly"
-- (optional) signature
slowMax :: Ord a => [a] -> a
slowMax [x] = x
slowMax (x:xs) = let m = slowMax xs in if x > m then x else m

-- fastMax "tail call friendly"
fastMax :: Ord a => [a] -> a
fastMax (x:xs) = fastMaxImpl x xs where
   fastMaxImpl m [] = m
   fastMaxImpl m (x:xs) = fastMaxImpl (if x > m then x else m) xs

(In a simple test I made with -O2, fastMax was 3.5x faster.)

Variadic CRTP template class with a field using constexpr basing on the parameter classes list

4 Answers4