Re: [boost] sentinels vs iterators (was: NTCTS Iterator)

Subject: Re: [boost] sentinels vs iterators (was: NTCTS Iterator)
From: Joaquin M Lopez Munoz (joaquin_at_[hidden])
Date: 2014-08-21 06:12:49

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?

Joaquín M López Muñoz
Telefónica