0

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.

Community
  • 1
  • 1
dlf
  • 9,045
  • 4
  • 32
  • 58
  • 1
    This does not strike me as something that a *container* should be used for at all. Seems like a mathematical or logical process, rather. – John Dibling May 06 '14 at 13:52
  • @John You are correct. I am attempting to get iterators over the output space of a function so I can leverage the standard library algorithms to search it. I will edit the word "container" out of the question. – dlf May 06 '14 at 13:57
  • this seems similar to what you are asking: http://stackoverflow.com/questions/12511711/initializing-stdvector-with-iterative-function-calls also you might want to check: http://en.cppreference.com/w/cpp/algorithm/generate_n – Pedrom May 06 '14 at 14:05

3 Answers3

3

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)

Qassim
  • 96
  • 3
  • 1
    +1, [Boost.Iterator](http://www.boost.org/doc/libs/1_55_0/libs/iterator/doc/index.html) makes this task easy. – JBentley May 06 '14 at 15:14
  • @JBentley It *looks* like I could get what I want by combining `counting_iterator` (which is lazy) with `transform_iterator`. And though a strict logician would disagree, based on the fact that boost added these, I'll conclude there is no simple way to get this behavior using the standard library alone. – dlf May 06 '14 at 15:45
0

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.

Rakib
  • 7,435
  • 7
  • 29
  • 45
  • Something like that would give me `[]` semantics, but not the iterators I'd need to use the standard library algorithms. – dlf May 06 '14 at 13:59
0

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).

oz10
  • 153,307
  • 27
  • 93
  • 128