Title: Getting Tuple Elements with a Runtime Index

Author: Martin Moene

Date: 02 June 2017 13:32:06 +01:00 or Fri, 02 June 2017 13:32:06 +01:00

Summary: Accessing a tuple with a runtime index is a challenge. Anthony Williams shows us his approach.

Body: 

std::tuple is great. It provides a nice, generic way of holding a fixed-size set of data items of whatever types you need. However, sometimes it has limitations that mean it doesn’t quite work as you’d like. One of these is accessing an item based on a runtime index.

std::get needs a compile-time index

The way to get the nth item in a tuple is to use std::get: std::get<n>(my_tuple). This works nicely, as long as n is a compile-time constant. If you’ve got a value that is calculated at runtime, this doesn’t work: you can’t use a value that isn't known until runtime as a template parameter.

  std::tuple<int,int,int> my_tuple=...;
  size_t index;
  std::cin>>index;
  int val=std::get<index>(my_tuple); //won't compile

So, what can we do? We need a new function, which I’ll call runtime_get, to retrieve the nth value, where n is a runtime value.

  template<typename Tuple>
  ... runtime_get(Tuple&& t,size_t index){
    ...
  }

The question is: how do we implement it?

Fixed return type

The return type is easy: our function must have a single return type for any given Tuple. That means that all the elements in the tuple must have the same type, so we can just use the type of the first element. std::tuple_element will tell us this, though we must first adjust our template parameter so it’s not a reference.

  template<typename Tuple>
  typename std::tuple_element<
   0, typename std::remove_reference<Tuple>
   ::type>::type&
  runtime_get(Tuple&& t,size_t index){
    ...
  }

Note: C++17 includes std::variant, so you might think we could use that to hold the return type, but that wouldn’t actually help us: to get the value from a variant, you need to call std::get<n>(v), which requires n to be a constant (again)!

OK, so the return type is just a reference to the type of the first element. How do we get the element?

Retrieving the nth element

We can’t do a straightforward switch, because that requires knowing all the cases in advance, and we want this to work for any size of tuple.

One way would be to have a recursive function that checked the runtime index against a compile-time index, and then called the function with the next compile-time index if they were different, but that would mean that the access time would depend on the index, and potentially end up with a deeply nested function call if we wanted the last element in a large tuple.

One thing we can do is use the index value as an array index. If we have an array of functions, each of which returns the corresponding element from the tuple, then we can call the appropriate function to return the relevant index.

The function we need is of course std::get; it’s just a matter of getting the function signature right. Our overload of std::get has the following signature for const and non-const tuples:

  template <size_t I, class... Types>
  constexpr tuple_element_t<I, tuple<Types...>>&
  get(tuple<Types...>&) noexcept;
  template <size_t I, class... Types>
  constexpr const tuple_element_t<I,
    tuple<Types...>>&
  get(const tuple<Types...>&) noexcept;

so, we can capture the relevant instantiation of std::get for a given tuple type Tuple in a function pointer declared as:

  using return_type=typename
    std::tuple_element<0,Tuple>::type&;
  using get_func_ptr=return_type(*)(Tuple&)
    noexcept;

The signature is the same, regardless of the index, because we made the decision that we’re only going to support tuples where all the elements are the same.

This makes it easy to build a function table: use a variadic pack expansion to supply a different index for each array element, and fill in std::get<N> for each entry (see Listing 1).

template<
    typename Tuple,
    typename Indices=std::make_index_sequence<std::tuple_size<Tuple>::value>>
struct runtime_get_func_table;

template<typename Tuple,size_t ... Indices>
    struct runtime_get_func_table<Tuple,std::index_sequence<Indices...>>{
    using return_type=typename std::tuple_element<0,Tuple>::type&;
    using get_func_ptr=return_type (*)(Tuple&) noexcept;
    static constexpr get_func_ptr table[std::tuple_size<Tuple>::value]={
        &std::get<Indices>...
    };
};

template<typename Tuple,size_t ... Indices>
constexpr typename
runtime_get_func_table<Tuple,std::index_sequence<Indices...>>::get_func_ptr
runtime_get_func_table<Tuple,std::index_sequence<Indices...>>::table[
    std::tuple_size<Tuple>::value];			

We need the separate redeclaration of the table to satisfy a pre-C++17 compiler; with C++17 inline variables it is no longer needed.

Our final function is then just a simple wrapper around a table lookup (see Lising 2).

template<typename Tuple>
constexpr
typename std::tuple_element<0,typename std::remove_reference<Tuple>::type>::type&
runtime_get(Tuple&& t,size_t index){
    using tuple_type=typename std::remove_reference<Tuple>::type;
    if(index>=std::tuple_size<tuple_type>::value)
        throw std::runtime_error("Out of range");
    return runtime_get_func_table<tuple_type>::table[index](t);
}			

It’s constexpr safe, though in a constexpr context you could probably just use std::get directly anyway.

So, there you have it: a constant-time function for retrieving the nth element of a tuple where all the elements have the same type.

Final code

Listing 3 is the final code for a constant-time function to retrieve an item from a tuple based on a runtime index.

#include <tuple>
#include <utility>
#include <type_traits>
#include <stdexcept>

template<
    typename Tuple,
    typename Indices=std::make_index_sequence<std::tuple_size<Tuple>::value>>
struct runtime_get_func_table;

template<typename Tuple,size_t ... Indices>
struct runtime_get_func_table<Tuple,std::index_sequence<Indices...>>{
    using return_type=typename std::tuple_element<0,Tuple>::type&;
    using get_func_ptr=return_type (*)(Tuple&) noexcept;
    static constexpr get_func_ptr table[std::tuple_size<Tuple>::value]={
        &std::get<Indices>...
    };
};

template<typename Tuple,size_t ... Indices>
constexpr typename
runtime_get_func_table<Tuple,std::index_sequence<Indices...>>::get_func_ptr
runtime_get_func_table<Tuple,std::index_sequence<Indices...>>::table[std::tuple_size<Tuple>::value];

template<typename Tuple>
constexpr
typename std::tuple_element<0,typename std::remove_reference<Tuple>::type>::type&
runtime_get(Tuple&& t,size_t index){
    using tuple_type=typename std::remove_reference<Tuple>::type;
    if(index>=std::tuple_size<tuple_type>::value)
        throw std::runtime_error("Out of range");
    return runtime_get_func_table<tuple_type>::table[index](t);
}			

Notes: 

More fields may be available via dynamicdata ..