On 8/21/2014 3:12 AM, Joaquin M Lopez Munoz wrote:
Eric Niebler
writes: On 08/20/2014 07:40 AM, Beman Dawes wrote:
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