Re: [boost] sentinels vs iterators

Subject: Re: [boost] sentinels vs iterators
From: Adam Wulkiewicz (adam.wulkiewicz_at_[hidden])
Date: 2014-08-21 16:07:56

Eric Niebler wrote:
> 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.
>

This reminds me about the Boost.Geometry rtree query iterators.

The most basic way of querying the rtree is to call a query() member 
function and pass a set of predicates into it, like this:

rtree.query(bgi::intersects(box1) && !bgi::within(box2), 
std::back_inserter(result));

There is also possible to perform iterative queries implemented as 
iterators. To get the iterator one calls a member function the same way 
as the one above:

rtree.qbegin(bgi::intersects(box1) && !bgi::within(box2));

this means that the type of an iterator depends on the type of the 
query. But the container in general should also define the type of an 
iterator. To keep the story short, I was forced to implement type-erased 
iterators. This also allowed me to internally use different iterators 
for begin and end. Otherwise it would be required to pass pass the query 
also to qend() method, since its type would also depend on the query's 
type. So the user may just write:

rtree.qend();

to get the end iterator. Technically the end iterator of course could 
have the same type and also store the query however then iterative 
queries are slower because the iterator is bigger. And as you can 
imagine type-erased iterators are also slower than "regular" ones.

The straightforward solution would be to allow different types of begin 
and end iterators but they'd require C++11/auto or Boost.Typeof and 
would be basically unusable since STL algorithms and Boost.Range 
requires the same types.
Have you thought about relaxing this requirement for the whole STL 
(algorithms, containers ctors, etc.)?

Your proposal could solve the problem described above, as long as it 
wouldn't be a good habit (wasn't done in one of the STL containers) to 
define some subrange types in the containers, since again - the type of 
a query range would depend on the type of a query. So something like 
this could work:

auto rng = rtree.qrange(bgi::intersects(box1) && !bgi::within(box2));

or if they were also supported by a range-based for loop:

for (auto g : rtree.qrange(bgi::intersects(box1) && !bgi::within(box2)))
     // something

Regards,
Adam