How would you implement a lazy "range factory" for C++20 ranges that just calls a generator function?

user_1413244 0
Viewed 464

I like the idea of the lazy ranges you can make with std::views::iota but was surprised to see that iota is currently the only thing like it in the standard; it is the only "range factory" besides views::single and views::empty. There is not currently, for example, the equivalent of std::generate as a range factory.

I note however it is trivial to implement the semantics of generate by using a transform view on iota and just ignoring the value iota passes to transform i.e.

#include <iostream>
#include <ranges>
#include <random>

template<typename F>
auto generate1(const F& func) {
    return std::views::iota(0) | std::views::transform([&func](int) {return func(); });
}

std::random_device dev;
std::mt19937 rng(dev());

int main() {

    auto d6 = []() {
        static std::uniform_int_distribution<> dist(1, 6);
        return dist(rng);
    };

    for (int v : generate1(d6) | std::views::take(10)) {
        std::cout << v << ' ';
    }
    std::cout << '\n';
}

My questions is what would be "the real way" to implement something like this? To make a range view object that is pipeable that does not just use iota.

I tried inheriting from ranges::view_interface -- no idea if this is the correct approach -- and just having it return a dummy iterator that calls a generator function but my code doesn't work because of the part where it needs to pipe the range view to std::views::take in order to not cause an infinite loop. The object I define here does not end up being pipeable.

#include <iostream>
#include <ranges>
#include <random>

template<typename F>
class generate2 : public std::ranges::view_interface<generate2<F>>
{
    using value_type = decltype(std::declval<F>()());

    class iterator {
        const F* gen_func_;
    public:
        iterator(const F* f) : gen_func_(f)
        {}

        value_type operator*() const {
            return (*gen_func_)();
        }

        bool operator!=(const iterator&) {
            return true;
        }

        iterator& operator++() {
            return *this;
        }
    };

    F generator_func_;

public:

    generate2(const F& f) : generator_func_(f) {
    }

    iterator begin()  {
        return iterator(&generator_func_);
    }

    iterator end()  {
        return iterator(nullptr);
    }
};

std::random_device dev;
std::mt19937 rng(dev());

int main() {

    auto d6 = []() {
        static std::uniform_int_distribution<> dist(1, 6);
        return dist(rng);
    };

    // the following doesnt compile because of the pipe...
    for (int v : generate2(d6) | std::views::take(10)) { 
        std::cout << v << ' ';
    }
    std::cout << '\n';
}
std-ranges c++20 c++
1 Answers

The reason why generate2 cannot work is that it does not model the range concept, that is, the type returned by its begin() does not model input_iterator, because input_iterator requires difference_type and value_type to exist and i++ is a valid expression.

In addition, your iterator does not satisfy sentinel_for<iterator>, which means that it cannot serve as its own sentinel, because sentinel_for requires semiregular which requires default_initializable, so you also need to add default constructors for it.

You also need to rewrite bool operator!=(...) to bool operator==(...) const since operator!= does not reverse synthesize operator==. But it's easier to just use default_sentinel_t as sentinel in your case.

if you add them to iterator you will find the code will be well-formed:

class iterator {
 public:
  using value_type = decltype(std::declval<F>()());
  using difference_type = std::ptrdiff_t;
  iterator() = default;
  void operator++(int);
  bool operator==(const iterator&) const {
    return false;
  }
  // ...
};

However, the operator*() of iterator does not meet the requirements of equality-preserving, that is to say, the results obtained by the two calls before and after are not equal, which means that this will be undefined behavior.

You can refer to the implementation of ranges::istream_view to use a member variable to cache each generated result, then you only need to return the cached value each time iterator::operator*() is called.

template<typename F>
class generate2 : public std::ranges::view_interface<generate2<F>> {
 public:
  auto begin() {
    value_ = generator_func_();
    return iterator{*this};
  }

  std::default_sentinel_t end() const noexcept { return std::default_sentinel; }

  class iterator {
   public:
   //...
    value_type operator*() const {
      return parent_->value_;
    }
   private:
    generate2* parent_;
  };

 private:
   F generator_func_;
   std::remove_cvref_t<std::invoke_result_t<F&>> value_; 
};
user_116387180
Related