Re: [boost] lifetime of ranges vs. iterators

From: David Abrahams (dave_at_[hidden])
Date: 2008-08-31 00:15:31

on Sat Aug 30 2008, Steven Watanabe <watanabesj-AT-gmail.com> wrote:

> AMDG
>
> David Abrahams wrote:
>>>    friend Iterator get_end(const filter_iterator& self) {
>>>        return
>>>            filter_iterator(
>>>                get_end(self.iter), get_end(self.iter), self.f);
>>>    }
>>>        friend Iterator set_end(
>>>        const filter_iterator& self, const filter_iterator& other);
>>>     
>>
>> Hi Steven,
>>
>> Say for example Iterator is strided_iterator<int>.  Then the return type
>> of set_end above is strided_iterator<int>, right?  So how will its body
>> typecheck?  Seems like this needs a little more thought.
>>   
>
> Oops.  I intended the return type to be filter_iterator.

Okay then, I take it you meant something like:

    template<IteratorWithEnd Iterator, class F>
    class filter_iterator<Iterator, F>
    {
    public:
       //...
       filter_iterator(Iterator begin, Iterator end, F f)
         : iter(set_end(begin,end)), f(f)
       {}
        
       filter_iterator& operator++() {
           ++iter;
           while(iter != get_end(iter) && !f(*iter)) ++iter;
           return *this;
       }
        
       friend filter_iterator get_end(const filter_iterator& self) {
           return
               filter_iterator(
                   get_end(self.iter), get_end(self.iter), self.f);
       }
        
       friend filter_iterator set_end(
           const filter_iterator& self, const filter_iterator& other)
       {
           return filter_iterator(self.iter, get_end(other.iter), f);
       }
    
    private:
       Iterator iter;
       F f;
    };

??

I'm still not seeing it.  In set_end you have:

     return filter_iterator(self.iter, get_end(other.iter), f);

Isn't the result of get_end going to be a filter_iterator?
The 2nd argument to filter_iterator's ctor is Iterator, though.

Maybe if you wrote out what you were trying to say in english it would
be easier for me to understand your goal here.

One thing that seems missing from your design in general is some way of
getting a type that represents the common information that must be
carried by any two iterators over the same range.  If you don't provide
a way to factor that information out, I don't see a way to avoid
redundant storage.

I was thinking of something more like this:

  // Gimme a better name, please!  The abstraction is a thing that
  // is always used in pairs, where each instance contains some 
  // redundant information in common.
  auto concept Factorable<typename T>
  {
       typename common_data = void;
       typename unique_data = T;

       common_data common(T) {}
       unique_data unique(T x) { return x; }
       T reconstruct(common_data, unique_data x) { return x; }
  };

  template <class I, class F>
  concept_map Factorable<filter_iterator<I,F> >
  {
       typedef compressed_pair<I,F> common_data
       typedef I unique_data;

       common_data common(filter_iterator<I,F> p)
       {
           return common_data(p.end(), p.func());
       }

       unique_data common(filter_iterator<I,F> p)
       {
           return p.base();
       }

       filter_iterator<I,F> reconstruct(common_data c, unique_data u)
       {
           return filter_iterator<I,F>( c.first(), c.second(), u);
       }
  };

-- 
Dave Abrahams
BoostPro Computing
http://www.boostpro.com