spring cc - 3 months ago 26

C++ Question

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;

};

Answer

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.