CODEWITHSUNDEEP
c++templatestuplestemplate-meta-programming
spring cc
spring cc

Reputation: 1027

How does this template work to find the index of a tuple?

In my project, there is function defined by template to find the index of an tuple, by I still don't understand how it works: there seems have a recursion but I have no idea about how it terminated at the right index?

// retrieve the index (for std::get) of a tuple by type
//  usage: std::get<Analysis::type_index<0, Type, Types ...>::type::index>(tuple)
//  TODO: should make this tidier to use
template<int Index, class Search, class First, class ... Types>
struct type_index
{
  typedef typename Analysis::type_index<Index + 1, Search, Types ...>::type type;
  static constexpr int index = Index;
};

template<int Index, class Search, class ... Types>
struct type_index<Index, Search, Search, Types ...>
{
  typedef type_index type;
  static constexpr int index = Index;
};

Upvotes: 0

Views: 146

Answers (1)

The Vee
The Vee

Reputation: 11570

The specialization is the termination condition. Note that it requires that First equals Search:

type_index<Index, Search, Search, Types ...>
                  ^^^^^^  ^^^^^^

For example, if you start with

type_index<0, C, A, B, C, D>,

this does not conform to the specialization, so the generic template will be used, redirecting (via its type member) to

type_index<0, C, A, B, C, D>::type = type_index<1, C, B, C, D>::type

but that's not evaluatable either until the chain reaches

type_index<0, C, A, B, C, D>::type = ... = type_index<2, C, C, D>::type

At this point the partial specialization can be used, which says that

type_index<2, C, C, D>::type = type_index<2, C, C, D>
type_index<2, C, C, D>::index = 2

and so

type_index<0, C, A, B, C, D>::type::index = 2
                 ^  ^  ^  ^
                 0  1  2  3

as intended.

Note that you don't need to carry the Index around and can indeed drop the whole ::type thing:

template<typename, typename...>
struct type_index;

template<typename Search, typename Head, typename... Tail>
struct type_index<Search, Head, Tail...> {
  // Search ≠ Head: try with others, adding 1 to the result
  static constexpr size_t index = 1 + type_index<Search, Tail...>::index;
};

template<typename Search, typename... Others>
struct type_index<Search, Search, Others...> {
  // Search = Head: if we're called directly, the index is 0,
  // otherwise the 1 + 1 + ... will do the trick
  static constexpr size_t index = 0;
};

template<typename Search>
struct type_index<Search> {
  // Not found: let the compiler conveniently say "there's no index".
};

This works as:

type_index<C, A, B, C, D>::index
  = 1 + type_index<C, B, C, D>::index
  = 1 + 1 + type_index<C, C, D>::index
  = 1 + 1 + 0
  = 2

and if the type is not among the list, will say something like (GCC 6.2.1):

In instantiation of ‘constexpr const size_t type_index<X, C>::index’:
  recursively required from ‘constexpr const size_t type_index<X, B, C>::index’
  required from ‘constexpr const size_t type_index<X, A, B, C>::index’
  required from [somewhere]
error: ‘index’ is not a member of ‘type_index<X>’

which I find quite self-explanatory.

Upvotes: 3

Related Questions