Eric Niebler <eniebler <at> boost.org> 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? Joaquín M López Muñoz Telefónica