Standard-layout tuple implementation

Question

I have written a simple (read: incomplete) tuple implementation that, AFAICT, does not violate the standard layout requirements. It's largely based on Nish's implementation, but I use a recursive hierarchy of nested members, rather than recursive inheritance. Unfortunately this approach necessitates recursion for element access. But for my purposes I am willing to sacrifice compilation time for a predictable memory layout... my tuple stores elements in the "correct" order.

Aside from lengthy compilation times, are there any obvious flaws to this approach?

#include <cstddef>
#include <type_traits>
template <class... Ts>
struct tuple;
template <class T, class... Ts>
struct tuple<T, Ts...>
{
 T first;
 tuple<Ts...> rest; 
};
template <class T>
struct tuple<T>
{
 T first;
};
namespace detail {
 template < ::std::size_t i, class T>
 struct tuple_element;
 template < ::std::size_t i, class T, class... Ts>
 struct tuple_element<i, tuple<T, Ts...> >
 : tuple_element<i - 1, tuple<Ts...> >
 {};
 template <class T, class... Ts>
 struct tuple_element<0, tuple<T, Ts...> >
 {
 using type = T;
 };
 template < ::std::size_t i>
 struct tuple_accessor
 {
 template <class... Ts>
 static inline typename tuple_element<i, tuple<Ts...> >::type & get (tuple<Ts...> & t)
 {
 return tuple_accessor<i - 1>::get(t.rest);
 }
 template <class... Ts>
 static inline const typename tuple_element<i, tuple<Ts...> >::type & get (const tuple<Ts...> & t)
 {
 return tuple_accessor<i - 1>::get(t.rest);
 }
 };
 template <>
 struct tuple_accessor<0>
 {
 template <class... Ts>
 static inline typename tuple_element<0, tuple<Ts...> >::type & get (tuple<Ts...> & t)
 {
 return t.first;
 }
 template <class... Ts>
 static inline const typename tuple_element<0, tuple<Ts...> >::type & get (const tuple<Ts...> & t)
 {
 return t.first;
 }
 };
 template <class T, class... Ts>
 struct tuple_builder
 {
 static inline void make (tuple<typename ::std::decay<T>::type, typename ::std::decay<Ts>::type...> & t, T && x, Ts &&... xs)
 {
 t.first = x;
 tuple_builder<Ts...>::make(t.rest, ::std::forward<Ts>(xs)...);
 }
 };
 template <class T>
 struct tuple_builder<T>
 {
 static inline void make (tuple<typename ::std::decay<T>::type> & t, T && x)
 {
 t.first = x;
 }
 };
} // namespace detail
template <class... Ts>
inline tuple<typename ::std::decay<Ts>::type...> make_tuple (Ts &&... x)
{
 tuple<typename ::std::decay<Ts>::type...> t;
 detail::tuple_builder<Ts...>::make(t, ::std::forward<Ts>(x)...);
 return t;
}
template < ::std::size_t i, class... Ts>
inline typename detail::tuple_element<i, tuple<Ts...> >::type & get (tuple<Ts...> & t)
{
 return detail::tuple_accessor<i>::get(t);
}
template < ::std::size_t i, class... Ts>
inline const typename detail::tuple_element<i, tuple<Ts...> >::type & get (const tuple<Ts...> & t)
{
 return detail::tuple_accessor<i>::get(t);
}
static_assert(::std::is_standard_layout<tuple<bool, int, float, char, double, tuple<int, char> > >(), "Compiler is stupid");

For more context, see this

Answer 1

Minor issues:

• You need to include <utility> for std::forward.

• You don't support empty tuples. It's obviously not a huge problem, but adding one line

  template <> struct tuple<> {};
  

  is no great burden either.

• You should be using std::forward for the assignments in the make functions:

  t.first = std::forward<T>(x);
  

  so move assignment is used when x is an rvalue reference.

Slightly bigger issue:

• Having no constructors in tuple means that your tuple can never contain a type that is not default constructible. "Default construction followed by assignment" is inherently less efficient than value construction. I would write perfect forwarding constructors for the tuple specializations, something like:

  template <class T, class... Ts>
  struct tuple<T, Ts...>
  {
   T first;
   tuple<Ts...> rest;
   tuple() = default;
   template <class U, class...Us, class=
   typename ::std::enable_if<
   !::std::is_base_of<
   tuple,
   typename ::std::decay<U>::type
   >::value
   >::type
   >
   tuple(U&& u, Us&&...tail) :
   first(::std::forward<U>(u)),
   rest(::std::forward<Us>(tail)...) {}
  };
  template <class T>
  struct tuple<T>
  {
   T first;
   tuple() = default;
   template <class U, class=
   typename ::std::enable_if<
   !::std::is_base_of<
   tuple,
   typename ::std::decay<U>::type
   >::value
   >::type
   >
   tuple(U&& u) :
   first(::std::forward<U>(u)) {}
  };
  

  (All that enable_if junk is to keep the perfect forwarding constructors from being used for copy/move construction from another tuple.) This allows make_tuple to become a one-liner:

  return tuple<typename ::std::decay<Ts>::type...>(::std::forward<Ts>(x)...);
  

(Code demo with suggested changes and the now-unnecessary builder templates removed)

• linguamachina: Awesome reply. Thanks Casey. Yes, constructors are the obvious omission (it took me quite a while to get make_tuple working - the reason I asked for review was to double-check I wasn't doing something completely stupid before moving on to tackle constructors)! Good catches on utility and forward. Not sure about empty tuples - why are they considered necessary? Obviously they can exist conceptually, but not in memory. By leaving out the empty class definition I get a nice compiler error if I try to instantiate an empty tuple. That seems like the most desired behaviour, no?
• Casey: @Chris My reasoning was purely for compatibility with std::tuple. I think empty tuples happen occasionally in esoteric metaprogramming scenarios, but it's obviously something very simple to add in later if you end up needing it.
• linguamachina: Thanks Casey. Your example has been a tour de force for me; perfect-forwarding constructors make a lot more sense after seeing this.

Answer 2

One issue I see with it is that rest is not guaranteed to be placed immidiately after first. Structure alignment is not specified (to the best of my knowledge) and is often the alignment of its biggest field. So this implementation is only "locally" standard layout, allowing to reliably calculate the offsets of its members (which std::tuple doesn't, whatever you can read on the web), but its gloabal layout is still undefined.

• bremen_matt: I didn't catch your point. Could you elaborate more on what you mean by Global vs local memory layout?