29 Aug 12:10
lifetime of ranges vs. iterators
From: Arno Schödl <aschoedl <at> think-cell.com>
Subject: lifetime of ranges vs. iterators
Newsgroups: gmane.comp.lib.boost.devel
Date: 2008-08-29 10:12:44 GMT
Subject: lifetime of ranges vs. iterators
Newsgroups: gmane.comp.lib.boost.devel
Date: 2008-08-29 10:12:44 GMT
Hello, some adaptor ranges need certain constant information about their underlying ranges. For example, iterating over a forward "difference_range", the difference between two sorted ranges, requires access to the ends of the underlying ranges. These two additional iterators are constant, they do not change when the difference_iterator is incremented. Now, where should this additional constant information be stored? a) In the difference_range, and each iterator holds a reference to the difference_range? That requires the difference_range to be alive as long as its iterators are alive. This may be difficult to ensure if the difference_range is a temporary. b) In the iterators, so the lifetime of adaptor iterators is independent of the adaptor range. Of course, one can use shared_ptrs and so on, but still the iterators are ultimately responsible to keep that information available. This initially seemed more natural to me, but if implemented naively by storing the additional iterators in the iterator itself, it leads to storage bloat: each difference_iterator needs 4 instead of 2 of its underlying iterators. When stacking difference iterators, the difference in required storage grows exponentially: instead of 2^N, you need 4^N storage... I feel that in order to solidify the range concept, one needs to make a choice whether a) or b) is "standard", because any user of ranges would need to know. Any thoughts on this? Arno -- Dr. Arno Schoedl · aschoedl <at> think-cell.com Technical Director(Continue reading)
when I need a simple for loop (and can't reach for BOOST_FOREACH), the syntax
I sometimes use is:
for(range<container> r (c); r; r = rest(r)) {
....
}
I think there may be some relationship between this and hierarchical
iterator representation, so I'd like to explore it further from that
angle as well.
> [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]
That's why the problem occurred to me looking at difference_iterator.
------
struct both_end {};
template<class Iter, class F>
struct filter_iterator : iterator_facade<blah,blah...> {
filter_iterator(associated_range<Iter>::type const& rng, F f ) :
m_range(rng), m_f(f) {}
filter_iterator(iter e, F f, both_end ) :
m_range(e,e), m_f(f) {} // if m_range takes e by value, e is expanded twice here, but no more, so no problem
private:
void increment() {
while(!m_f(front(m_range))
