Implementing a Boost range adaptor reversed_if

Question

I regularly encounter situations in my code in which I would like to iterate over a range in direct or in reverse order depending on a runtime condition. This typically results in code like the following

if (reverse) {
    using boost::adaptors::reversed;
    for (auto const & x : range | reversed) do_stuff(x);
} else {
    for (auto const & x : range) do_stuff(x);
}

or

std::vector<Foo> v(range.begin(), range.end());
if (reverse) boost::range::reverse(v);
for (auto const & x : v) do_stuff(x);

which contains code duplication (first one) or is inefficient (second one).

I've been thinking many times about an hypothetical Boost range adaptor that would conditionally reverse a range, so that I could write

using boost::adaptors::reversed_if;
for (auto const & x : range | reversed_if(reverse)) do_stuff(x);

I can implement it myself (starting from here) but I am not sure about how to proceed. In order to support runtime conditions, I'm afraid I'll have to check a boolean at each iteration to determine the iteration direction or use virtuality to dispatch to iteration code. Is this the reason why this is not provided in Boost range adaptors?

Any alternative solution?

Answer 1

If you want to avoid runtime checking at each increment which way to go, you have to convert the runtime value into a compile time value outside the structure of the loop.

In this case, we want the range we are looping over to vary, while the body does not.

The easy way to do this is to write a lambda for the body, then have a switch to pick which loop to choose.

auto do_stuff = [&](auto&& elem){ /* code */ };
if (reverse) {
  using boost::adaptors::reversed;
  for (auto const & x : range | reversed) do_stuff(x);
} else {
  for (auto const & x : range) do_stuff(x);
}

we have done the runtime dispatch outside of the loop, creating two different loops with static type information about how they loop.

We can make an adapter like this:

magic_switch
  ( reverse )
  ( range, range|reversed )
  (
    [&](auto&& range){
      for (auto const& x : decltype(range)(range)) {
        do_stuff(x);
      }
    }
  );

where magic_switch takes an index (std::size_t) as its first argument. It returns a lambda, which takes a list of arguments. It returns a lambda, which takes a lambda and passes to it the argument from the 2nd list as determined by the first argument's index into that list.

inline auto magic_switch( std::size_t I ) {
  return [I](auto&&...options) {
    return [I, &](auto&& f)->decltype(auto) {
      using fptr = void(*)(void const volatile* op, decltype(f));
      static const fptr table[] = {
        +[](void const volatile* op_in, decltype(f) f) {
          auto* option = static_cast<std::decay_t<decltype(options)>*>(op_in);
          decltype(f)(f)( decltype(options)(*option) );
        }...
      };
      const volatile void* ptrs[] = {std::addressof(options)...};
      if (I >= sizeof...(options)) I = sizeof...(options)-1;
      if (I == -1) return;
      table[I]( ptrs[I], decltype(f)(f) );
    };
  };
}

is a sketch at an implementation (it almost certainly contains build errors).

The hard part is that "type flow" (to coin a term) doesn't go the way you usually want it to. So I'm forced to use continuation-passing-style basically.

Note that many compilers are unhappy with a pack expansion containing an entire lambda. A helper function that returns the function pointer can be written:

template<class F>
using f_ptr = void(*)(const volatile void*, F&&);

template<class Option, class F>
f_ptr<F> get_f_ptr() {
  return +[](void const volatile* op_in, F&& f) {
    auto* option = static_cast<std::decay_t<Option>*>(op_in);
    std::forward<F>(f)( std::forward<Option>(*option) );
  };
}

then replace the table with:

      static const fptr table[] = {
        get_fptr<decltype(options), decltype(f)>()...
      };

on those compilers.