On Mon, Sep 1, 2008 at 8:55 PM, Arno Schödl <aschoedl@think-cell.com> wrote:
If I understand Giovanni's implementation correctly, it only needs to expand one layer at a time.
Let's expand it:
iterator begin() const{ return iterator(begin(m_range), end(m_range), m_f); }
-->
return iterator( iterator( begin(subrange), end(subrange), m_f ), iterator( end(subrange), end(subrange), m_f ), m_f);
-->
...
The expansion will terminate when begin/end(sub...subrange) is the base iterator. Then the call is made to the filter_iterator ctor, which calls the associated_range<filter_iterator> ctor, which condenses everything back down.
I see the problem. I think that for non complex iterators, the optimizer can still manage to fix the problem. For more complex iterators (think of an any_iterator, whose constructor and copy operator happen to be fairly expensive), things get bad. A general fix is having the constructor of the filter iterator take a range parameter instead of two iterators, and use that range to directly initialize its containing range (note that the two ranges do not need to be of the same type). That should take care of the doubly recursive call in begin. It doesn't fix end though, and we cannot pass a range because we obviously do not have one. We need another constructor that only takes a single iterator and initializes both ends of the subrange with that iterator. You would still have a (tail and static) recursive call to end(), but it would be O(N), which shouldn't be a problem. NRVO should take care of eliminating excessive copying. Arno, can you see other exponential expansions? [btw, for long chains of filter and map iterators it is not really a problem because you can always transform them exactly to one each of map and filter iterator] -- gpd