Re: [boost] sentinels vs iterators

Subject: Re: [boost] sentinels vs iterators
From: Eric Niebler (eniebler_at_[hidden])
Date: 2014-08-21 12:23:54

On 8/21/2014 3:12 AM, Joaquin M Lopez Munoz wrote:
> Eric Niebler <eniebler <at> boost.org> writes:
>> On 08/20/2014 07:40 AM, Beman Dawes wrote:
>>>
>>> See http://beman.github.io/ntcts_iterator/
>>>
>>> or https://github.com/Beman/ntcts_iterator
>>
>> The need for such a thing is an unfortunate side-effect of the fact that
>> a range's begin and end iterators must have the same type. I'm building
>> a range library that loosens that restriction and writing a proposal to
>> get it into the standard.
> 
> Hi Eric,
> 
> This might be connected in a way with your sentinel idea. Some
> months ago I explored a container-like construct for polymorphic
> objects that group elements by run-time type so as to greatly
> speed up for_each processing:
> 
> http://bannalia.blogspot.com.es/2014/05/fast-polymorphic-collections.html
> 
> This poly_collection class (currently just a sketch to show the
> underlying ideas) has a for_each member function
> 
>   template<typename F> F for_each(F f);
> 
> that internally dispatches to the different same-type chunks
> the collection is comprised of:
> 
>   template<typename F>
>   F for_each(F f)
>   {
>     for(const auto& p:chunks)p.second->for_each(f);
>     return std::move(f);
>   }
> 
> The performance gains are massive, as shown in the article. Now, if
> we wished to use the standard for_each algorithm rather than
> the provided member function:
> 
>   poly_collection<base> c;
>   ...
>   std::foreach(c.begin(),c.end(),f);
> 
> then poly_collection would have to implement an iterator type
> that sequentally traverses all the chunks, which implies a fairly
> expensive increment operation (in pseudocode):
> 
>   iterator& operator++()
>   {
>     node+=chunk_element_size;
>     if(node==chunk_end()){
>       node=next_chunk_begin(node);
>     }
>     return *this;
>   }
> 
> That is, incrementing involves checking against chunk end, which,
> combined with the begin!=end check of std::for_each, implies two
> checks per step. This is slower than poly_collection::for_each,
> which can get by with just one check per step.
> 
> I wonder: maybe a sentinel-based range can be used so that
> std::for_each(c,f) is as efficient as c.for_each(f) for a
> poly_collection c?

You're looking for segmented iterators and hierarchical algorithms. Matt
Austern wrote a paper about it:

http://lafstern.org/matt/segmented.pdf

Segmented iterators force you to rewrite all the algorithms. They are a
different beast than iterators with sentinels, which are not nearly so
invasive. I'm not proposing segmented iterators.

Eric