Boost logo

Boost :

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>> writes:

> On 08/20/2014 07:40 AM, Beman Dawes wrote:
> >
> > See
> >
> > or
> 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:

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;

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++()
    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

Boost list run by bdawes at, gregod at, cpdaniel at, john at