Implementation of state machines (ala generators) using iterators

Question

Recently, I need to implement small classes that generate a bunch of numbers. It would be very convenient if C ++ had generators like python, but unfortunately this is not the case.

So, I was thinking about how to best implement these types of objects, for easy iteration and composition. When we think of iterators over containers, they essentially only contain the index for the element, and most of the information is in the container itself. This allows multiple iterators to reference different elements in the collection at the same time.

When it comes to machine states, it becomes obvious that the iterator will have to hold the whole state, since several iterators must be independent. In this sense, the state class of a machine is rather the “builder” of these iterators, which are actual state machines.

As an example of toys, I implemented a range generator (ala xrange in python) that can be used in loops:

 // using range-for from c++11 for (auto i : range<int>(1, 30)) { cout << i << endl; } 

The code can be found on my bitbucket .

However, it is inconvenient to store an integer state in an iterator, since the end() iterator is only created to compare the final state that allocates space if the state is a large collection of members.

Was something done using simple machines with a linear state and looping over them using iterators?

Answer 1

If you only support forward iteration, you can get away with using a different type for end () and then for begin (). Here is the main idea

 class iterator; class iterator_end { typedef ... value_type; ... iterator& operator++ () { throw ... } value_type operator* () { throw ... } bool operator== (const iterator& e) const { return e == *this; } } class iterator { typedef ... value_type; .. iterator& operator++ () { ... } value_type operator* () { ... } bool operator== (const iterator_end& e) const { return are_we_done_yet } } class statemachine { iterator begin() const { ... } iterator_end end() const { ... } } 

I have never tried to do this, so I cannot guarantee that this will work. In your state machines, iterator and const_iterator typedefs specify a different type than end() returns, which may or may not cause problems.

Another possibility is to switch from the variation to pimpl, which uses boost::optional . Put the iterator state in a separate class and save it inside boost::optional inside the iterator. Leave the status undone for the iterator returned by end() . You will not save any memory, but avoid heap allocation (boost :: optional does not, uses a new location!) And initialization overhead.