Implementing a tuple_iterator

01 Mar 2017 by Jonathan

This post is part of a collaboration with Arne Mertz. Arne is a software Engineer at Zühlke and a clean code enthusiast with a focus on modern C++. You can find him online at Twitter and at his “Simplify C++!” blog. We’ve both written something about accessing std::tuple, but swapped our blogs - my post is over at his blog and his one follows here now:

Did you ever wonder how we could iterate over the contents of a std::tuple at runtime, similar to an array or std::vector? You may or may not see the need for such a functionality - this walkthrough shows a proof of concept and how you tackle problems like this in C++17.

The mission

When I say “iterate over the contents of a tuple”, I think of range-based for loops. Tuples have neither begin() and end() methods, nor are we allowed to overload free versions of those functions in namespace std. That means, range-based for directly over a tuple is not possible, so we’ll have to provide a wrapper for the functionality around std::tuple.

Another problem is the content we iterate over: This should work for any instantiation of std::tuple, i.e. with arbitrary contents. The elements we iterate over will have to be some kind of sum type. The type for that in the STL is std::variant, and with std::visit we can access whatever is in it.

An example of the code we would like to get working is this:

int main() {
  std::tuple<int, std::string, double> tup{42, "foo", 3.14};
  for (auto const& elem : to_range(tup)) { 
    std::visit(
      overload(
        [](int i) { std::cout << "int: " << i << '\n'; },
        [](std::string const& s) { std::cout << "string: " << s << '\n'; },
        [](double d) { std::cout << "double: " << d << '\n'; }
      ),
      elem
    );
  }
}

Here, overload is just a functionality that draws all the arguments together into one single function object.

Taking it apart

Compile time access at runtime?

Iterating over a tuple at compile time is easy. With std::get<N> we can access any member. The N, however, needs to be known at compile time. If iterators in a range-based for loop were allowed to change their type in every step, we could just write a tuple_iterator<N> template and call it a day.

But it’s not that easy. Iteration happens at runtime, and we have no arbitrary runtime access for tuples. That means, we somehow have to map runtime information (i.e. which element should the iterator point to) to the access functions that need compile time information.

The only way to achieve this is to put all of the compile-time information in a list we can iterate over at runtime. In other words, we need a lookup table.

template< /* ??? */ >
struct tuple_runtime_access_table {
  using tuple_type = /* ??? */;
  using return_type = /* ??? */;
  using converter_fun = /* ??? */;

  template <std::size_t N>
  static return_type access_tuple(tuple_type& t, converter_fun& f) {
    return f(std::get<N>(t));
  }

  using accessor_fun_ptr = return_type(*)(tuple_type&, converter_fun&);
  const static auto table_size = std::tuple_size_v<tuple_type>;

  const static std::array<accessor_fun_ptr, table_size> lookup_table = {
    {&access_tuple<0>, &access_tuple<1>, /* ... and so on ... */ , &access_tuple<table_size - 1> }
  };
};

Let’s go over this step by step: Since std::get<N> returns different types, we can not simply take the addresses of std::get<0>, std::get<1> etc. for a given tuple. We need to convert the result into a result_type common to all those functions, e.g. the std::variant I mentioned earlier.

To get that, we need a converter_fun function or function object that, applied to any element of our tuple, results in the result_type. The static function template access_tuple<N> does exactly this. Last but not least we have to stuff pointers to all those functions into our lookup table.

Filling out the blanks

We don’t want to put too much logic into this one template, so we can just use template parameters for tuple_type, return_type and converter_fun. In addition, to generate the contents of our table, we’ll need to generate indices from 0 through table_size -1 as shown here. This is a typical use case for variadic non-type templates.

template <typename Tup, typename R, typename F, std::size_t... Idxs>
struct tuple_runtime_access_table {
  using tuple_type = Tup;
  using return_type = R;
  using converter_fun = F;

  template <std::size_t N>
  static return_type access_tuple(tuple_type& t, converter_fun& f) {
    return f(std::get<N>(t));
  }

  using accessor_fun_ptr = return_type(*)(tuple_type&, converter_fun&);
  const static auto table_size = sizeof...(Idxs);

  constexpr static std::array<accessor_fun_ptr, table_size> lookup_table = {
    {&access_tuple<Idxs>...}
  };
};

Leverage type deduction

We’d like to have most of the template parameters deduced, especially since the converter function will probably be a lambda. The index parameter pack will be provided via a std::index_sequence. So let’s write a small utility function to do the type deduction for us:

template <typename R, typename Tup, typename F, std::size_t... Idxs>
auto call_access_function(Tup& t, std::size_t i, F f, std::index_sequence<Idxs...>) {
  auto& table = tuple_runtime_access_table<Tup, R, F, Idxs...>::lookup_table;
  auto* access_function = table[i];
  return access_function(t, f);
}

Now, the only thing that has to be provided explicitly is the return type. Note that neither R nor F, nor Idxs... are specified at this point. That means, we could use this to execute any given F on our tuple, as long as it can be applied to all elements in that index list and the return types are convertible to R.

The return type

It’s time to get more concrete on that return type. I wrote it should be a std::variant. To be able to have write access to the tuple, and to not have to make potentially costly copies of the tuple elements, the variant should contain references. Sadly, std::variant may not contain references, so we’ll have to use std::reference_wrapper.

template <typename Tup> struct common_tuple_access;

template <typename... Ts>
struct common_tuple_access<std::tuple<Ts...>> {
  using type = std::variant<std::reference_wrapper<Ts>...>;
};

The standard library makes an effort to provide most of the functionalities that are available for std::tuple also for std::pair and std::array. Therefore, we should specialize this metafunction for those two as well. Note that for std::array this is quite useless in most cases, since it already has begin() and end() member functions.

template <typename T1, typename T2>
struct common_tuple_access<std::pair<T1, T2>> {
  using type = std::variant<std::reference_wrapper<T1>, std::reference_wrapper<T2>>;
};

template <typename T, auto N>
struct common_tuple_access<std::array<T, N>> {
  using type = std::variant<std::reference_wrapper<T>>;
};

And then finally make it easily accessible.

template <typename Tup>
using common_tuple_access_t = typename common_tuple_access<Tup>::type;

The runtime access function

With the lookup table and the utility function, we should be able to write a function that simply takes the Nth entry of it and invokes it on a tuple to get the std::variant containing the corresponding element. All that is missing is to write the function object that does the wrapping into the std::reference_wrapper for us, and create the right std::index_sequence:

template <typename Tup>
auto runtime_get(Tup& t, std::size_t i) {
  return call_access_function<common_tuple_access_t<Tup>>(
    t, i, 
    [](auto & element){ return std::ref(element); },
    std::make_index_sequence<std::tuple_size_v<Tup>>{}
  );
}

The rest is easy…

Having tackled the runtime access to the ith element of any tuple, the rest of the way to our range based for loop is relatively straight forward.

tuple_iterator

The absolute minimum for the range-based for loop is that the iterator type returned from begin() have the pre-increment and dereferencing operators defined, and that operator!= is defined for the two types returned by begin() and end(). Note that from C++17 the two types need not necessarily be the same.

For our purposes it will be sufficient if we use the same type of iterator for begin() and end(). Personally, I think operator!= should always be implemented in terms of operator==, if possible, so I’ll provide that one as well.

template <typename Tup> class tuple_iterator {
  Tup& t;
  size_t i;
public:
  tuple_iterator(Tup& tup, size_t idx)
    : t{tup}, i{idx} 
  {}
  
  tuple_iterator& operator++() { 
    ++i; return *this; 
  }
  bool operator==(tuple_iterator const& other) const {
    return std::addressof(other.t) == std::addressof(t)
      && other.i == i;
  }
  
  bool operator!=(tuple_iterator const& other) const {
    return !(*this == other);
  }

  auto operator*() const{ 
    return runtime_get(t, i); 
  }
};

There’s much more to implement to make this a proper iterator, e.g. range checks and many other operators, but I’ll leave that as an exercise to the reader.

to_range

The last piece of the puzzle is a very simple range wrapper:

template <typename Tup>
class to_range {
  Tup& t;
public:    
  to_range(Tup& tup) : t{tup}{}

  auto begin() {
    return tuple_iterator{t, 0};
  }
  auto end() {
    return tuple_iterator{t, std::tuple_size_v<Tup>};
  }
      
  auto operator[](std::size_t i){
    return runtime_get(t, i);
  }
};

Again, I provide only the necessary operations, plus an overload of operator[] to make the access of single elements easy.

overload

Using template deduction for classes, overload can be implemented relatively simply and naively in C++17:

template <class ... Fs>
struct overload : Fs... {
  overload(Fs&&... fs) : Fs{fs}... {}
  using Fs::operator()...;
};

There is also a proposal to add something more sophisticated to a later standard, but for this use case it will suffice.

Putting it all together

Let’s revisit again the original goal:

int main() {
  std::tuple<int, std::string, double> tup{42, "foo", 3.14};
  for (auto const& elem : to_range(tup)) { 
    std::visit(
      overload(
        [](int i) { std::cout << "int: " << i << '\n'; },
        [](std::string const& s) { std::cout << "string: " << s << '\n'; },
        [](double d) { std::cout << "double: " << d << '\n'; }
      ),
      elem
    );
  }
}

This code will now compile as it is and delivers the expected results. It will also “just work” for std::pair, because we took care of common_tuple_access for pairs.

Dealing with reference_wrapper

Since we had to make the tradeoff of using std::reference_wrapper inside the variant, we have to be aware of that fact. For example, if we have a generic lambda in our visitor, it will always be called with the reference_wrappers instead of the functions we intended to do the job.

In addition, if the reference wrapper contains a template like std::string, then printing it via operator<< will fail, because it will not consider the implicit conversion from std::reference_wrapper<std::string>> to std::string. Therefore, the following code will result in a template error novel:

…
std::visit(
  overload(
    [](int i) { std::cout << "int: " << i << '\n'; },
    [](double d) { std::cout << "double: " << d << '\n'; },
    [](auto const& s) { std::cout << "???: " << s << '\n'; }
  ),
  elem
);
…

This can be fixed with a helper that derives from overload and applies the unwrapping for us:

template <class ... Fs>
struct overload_unref : overload<Fs...> {
  overload_unref(Fs&&... fs) 
    : overload<Fs...>{std::forward<Fs>(fs)...}      
  {}

  using overload<Fs...>::operator();

  template <class T>
  auto operator()(std::reference_wrapper<T> rw){
    return (*this)(rw.get());
  }
};

Using this, the code will work again:

int main() {
  std::tuple<int, std::string, double> tup{42, "foo", 3.14};
  for (auto const& elem : to_range(tup)) { 
    std::visit(
      overload_unref(
        [](int i) { std::cout << "int: " << i << '\n'; },
        [](double d) { std::cout << "double: " << d << '\n'; },
        [](auto const& s) { std::cout << "???: " << s << '\n'; }
      ),
      elem
    );
  }
}

You can find the full code on here on GitHub.

Conclusion

We can get runtime access to tuples, although there is some overhead involved. The redirection via the function pointer table can not be optimized away, and neither can the resolution of the variant’s content in std::visit. We trade some performance for flexibility, because we do not need to know which element we are accessing at compile time.

Would you like to see a way to implement an operator[] that can make the clumsy std::get<N> calls on tuples much nicer without any run time overhead? Head over to my blog for Jonathan’s solution!

This blog post was written for my old blog design and ported over. If there are any issues, please let me know.