Anthony Williams from Just Software Solutions Blog
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 n
th 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 n
th 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 n
th 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:
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:
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 n
th element
of a tuple where all the elements have the same type.
Final code
Here 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);
}
Posted by Anthony Williams
[/ cplusplus /] permanent link
Tags: cplusplus, tuples
| Stumble It! | Submit to Reddit | Submit to DZone
Follow me on Twitter