Re: [boost] sentinels vs iterators

Subject: Re: [boost] sentinels vs iterators
From: Adam Wulkiewicz (adam.wulkiewicz_at_[hidden])
Date: 2014-09-08 10:50:59

Hi,

2014-08-22 5:34 GMT+08:00 pfultz2 <pfultz2_at_[hidden]>:

> > 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.
>
> There is no need to use type-erased iterators here.

They're required to provide STL-like interface:

rtree_t::const_query_iterator it = rtree.begin(/*some query*/);

> Instead it should return
> a
> range:
>
>     rtree.qrange(bgi::intersects(box1) && !bgi::within(box2));
>
> Then the range that is returned will know the query type that is needed for
> the `.begin()` and `.end()` member functions. Plus, returning a range is
> helpful if the user wants to use it in a range-for loop or with
> Boost.Range.
>
>
Yes, and in this case various queries would produce various types of
Ranges. So the user would be forced to use BOOST_TYPEOF(), C++11 auto
keyword or one of the Boost.Range algorithms or adaptors.

> Also, I'm not sure using different iterators types in this case has a boost
> in
> performance, since the end iterator is pointing to a 'valid' place in the
> sequence, unlike an end iterator for a null-terminated string which is just
> a
> placeholder for the end.
>

The query iterator must store query predicates. If the end iterator has the
same type as e.g. the begin iterator it must store it as well, and those
are fat iterators. So there is a tiny performance penalty related to the
initialization and copying of unneeded data into the end iterator. And the
rtree query end iterator is really a sentinel because the iterator returned
by begin() knows exactly when the iteration should be stopped, e.g. when it
already iterated over k-nearest objects or there is no other bounding box
intersecting some passed region, etc.

Well, the Range could store the required data and the iterators returned by
the Range could only store references/pointers to this Range. So if it was
guaranteed that the Range returning some Iterators would be forced to exist
as long as those Iterators exist, this approach should work. But I'm not
sure if there is such requirement.

Regards,
Adam