How to implement std::tuple efficiently such that a tuple of empty types is itself an empty type?

Question

I am implementing std::tuple and I want it to be as efficient in both object size and compile time as possible. I am following the suggestions given here and here.

To improve compile-time performance, the implementation does not use recursive inheritance and instead uses multiple inheritance with the tuple_leaf trick. Additionally it uses the empty base class optimization when possible to reduce the size of the type.

To ensure that the empty base class optimization is always applied, my implementation of tuple itself derives from a base class instead of storing the implementation inside a member variable. However, this causes problems with nested tuples because the tuple_leaf technique works through conversion to a base class. Nested tuples cause ambiguity because the same type of tuple_leaf may occur more than once in the derivation chain.

A program illustrating a simplification of the problem is posted below. Is there a simple way to disambiguate the conversion and allow the program to compile and execute without throwing the assert? I have considered detecting the nested tuple case and encoding the multidimensional position of each tuple_leaf within its type somehow, but that seems complex and would probably degrade compile-time performance.

#include <type_traits>
#include <cassert>

template<int i, class T, bool = std::is_empty<T>::value>
struct tuple_leaf
{
  tuple_leaf(T x) : val(x) {}

  T& get() { return val; }

  T val;
};


template<int i, class T>
struct tuple_leaf<i,T,true> : private T
{
  tuple_leaf(T x) : T(x) {}

  T& get() { return *this; }
};


template<int i, class T1, class T2>
struct type_at
{
  using type = T1;
};


template<class T1, class T2>
struct type_at<1,T1,T2>
{
  using type = T2;
};


template<class T1, class T2>
struct tuple_base : tuple_leaf<0,T1>, tuple_leaf<1,T2>
{
  tuple_base(T1 a, T2 b) : tuple_leaf<0,T1>(a), tuple_leaf<1,T2>(b) {}

  template<int i>
  tuple_leaf<i,typename type_at<i,T1,T2>::type> get_leaf()
  {
    // XXX how to disambiguate this conversion?
    return *this;
  }
};


// XXX deriving from tuple_base rather than
//     making tuple_base a member is the root of the issue
template<class T1, class T2>
struct my_tuple : tuple_base<T1,T2>
{
  my_tuple(T1 a, T2 b) : tuple_base<T1,T2>(a, b) {}
};

template<int i, class T1, class T2>
typename type_at<i,T1,T2>::type& get(my_tuple<T1,T2>& t)
{
  return (t.template get_leaf<i>()).get();
}

template<class T1,class T2>
my_tuple<T1,T2> make_tuple(T1 a, T2 b)
{
  return my_tuple<T1,T2>(a,b);
}

struct empty {};

int main()
{
  auto tuple = make_tuple(empty(), make_tuple(empty(),empty()));

  assert((std::is_empty<decltype(tuple)>::value));
  assert(sizeof(tuple) == sizeof(empty));

  get<0>(tuple);

  return 0;
}

The compiler output:

$ clang-3.5 -std=c++11 repro.cpp 
repro.cpp:47:12: error: ambiguous conversion from derived class 'tuple_base<empty, my_tuple<empty, empty> >' to base class 'tuple_leaf<0, empty, true>':
    struct tuple_base<struct empty, struct my_tuple<struct empty, struct empty> > -> tuple_leaf<0, struct empty>
    struct tuple_base<struct empty, struct my_tuple<struct empty, struct empty> > -> tuple_leaf<1, struct my_tuple<struct empty, struct empty> > -> struct my_tuple<struct empty, struct empty> -> tuple_base<struct empty, struct empty> -> tuple_leaf<0, struct empty>
    return *this;
           ^~~~~
repro.cpp:63:22: note: in instantiation of function template specialization 'tuple_base<empty, my_tuple<empty, empty> >::get_leaf<0>' requested here

  return (t.template get_leaf<i>()).get();
                     ^
repro.cpp:80:3: note: in instantiation of function template specialization 'get<0, empty, my_tuple<empty, empty> >' requested here
  get<0>(tuple);
  ^
1 error generated.

Well, when I run into a "how can I solve this problem with templates", everything looks like a nail: use CRTP? Include the type of `tuple_base` in at least the type you are casting to in `get_leaf`. Barring a recusive template definition (!), the leaves of the child type cannot match the leaves of the parent. — Yakk - Adam Nevraumont, Feb 28 '15 at 02:21
when I tried to do it, I'm getting non-empty tuples with your sample code. — Yakk - Adam Nevraumont, Feb 28 '15 at 02:29
g++ 4.8 & clang 3.5 seem to pass the program at http://gist.github.com/jaredhoberock/f42026101412578172cc — Jared Hoberock, Feb 28 '15 at 02:34

score 3 · Accepted Answer · answered Feb 28 '15 at 02:32

When all you have is a hammer, everything looks like "why not try CRTP". Because CRTP solves all problems with templates.

Extend tuple_leaf with a class D derived, and pass the type of tuple_base in. (Alternatively, write a template<class...>struct types{}; and pass that in -- all you need is an type that uniquely distinguishes two different tuples).

Modify the get_leaf to get the appropriate class, and now there is no ambiguity.

Problems:

First, without ICF, this makes a bunch of methods that would be identical now distinct.

Second, if you implement recursive tuples, this breaks horribly. The above relies on the fact that a tuple containing a subtuple X has a different set of types in it than the subtuple.

Third, when I tried it myself with the above code, I get empty structures with non-1 size. Strange. And if I bypass the static asserts and the like, get<0> segfaults. This could be an artifact of your simplified problem, I am uncertain.

Those tuples contains multiple instances of the same empty class. The tuples can't be empty, since those instances must have different addresses. — Casey, Feb 28 '15 at 08:38
@casey amusingly they are `is_empty` but also have non-1 size. — Yakk - Adam Nevraumont, Feb 28 '15 at 11:42
The segfault is because `get_leaf` returns by value, causing `get` to return a reference to a temporary. [The program works correctly once that's fixed.](http://coliru.stacked-crooked.com/a/4635479ca1e3073c) — Casey, Feb 28 '15 at 17:32

How to implement std::tuple efficiently such that a tuple of empty types is itself an empty type?

1 Answers1