Generator list with c++ standard library?

Question

Does the C++ standard library include any mechanism to produce a list-like iterable range that uses an injected generator function to return the value at each position? i.e. something that could give behavior analogous to C#'s yield return or F#'s yield list comprehensions? The ideal would be:

hypothetical_generator_list<size_t> l([](size_t index) { return index * 2; });
assert(l[4] == 8);
assert(*(l.begin() + 1000000000) == 2000000000);

Motivation: I would like to do a binary search over a space of hundreds of billions of (monotonically increasing) values. But std::lower_bound wants iterators, and it would be completely impossible to put all the values into anything like a vector. However, I could easily write a function that, given an index, does a few calculations and returns the value at that index.

hypothetical_generator_list<size_t> c([](size_t index) { return index * 2; });
auto itFound = std::lower_bound(l.begin(), l.begin() + 100000000000, 6000);
assert(itFound - l.begin() == 3000);

I could write my own custom iterator, but that seems like a lot of work compared to just passing a simple lambda to a constructor. And of course I could just write the binary search myself (but what fun would that be?). Are those the only choices?

For posterity, here are a couple links I found on the subject:

Equivalent C++ to Python generator pattern

http://www.sirver.net/blog/2011/08/19/generators-in-c++/

But it seems the answer is that there is no way to do this that is simpler than just writing a binary search.

Answer 1

Algorithms won't give you the index while scanning over the range. You can use boost.Iterator (or Boost.range) to help you to write your iterator (either [boost::iterator_facade][1] or [boost::function_input_iterator][2]for instance)

Answer 2

It may work

template<int X >       
class ListGenerator
{
  public:
    int operator[](int Y){ return X*Y;}
};

int main()
{
    ListGenerator<5> lg;
    cout<<lg[5]<<endl;
    return 0;
 }

you can modify template parameter list to add as many as you need.

Answer 3

Something like this?

std::size_t index = 0;
std::generate_n(std::back_inserter(list), count, [&index]
{
    return index++ * 2;
});

Here we're populating list with count elements from our generator function (the lambda).