Subject: Re: [geometry] Are all query iterators const?
From: Adam Wulkiewicz (adam.wulkiewicz_at_[hidden])
Date: 2015-09-02 17:36:39
Hi Hal,
Hal Clark wrote:
> I'm new to Boost.Geometry and have recently discovered the
> rtree::qbegin()/qend() mechanism. It is useful (thanks!) but the
> iterators are all marked const. Is it possible to get non-const
> iterators without mucking about with const_cast? (I see
> rtree::begin()/end() are new between 1.57.0 and 1.58.0 -- hopefully
> non-const qbegin()/qend() follow more easily.)
All rtree iterators are const iterators. The rationale behind it is
similar to the rationale behind the constness of std::multiset
iterators. If it was possible to modify the value it would be very easy
to break the index. In the case of the rtree it's even more
understandable since by definition it's an index, not a container. So
it's a data structure, typically containing only some simple geometrical
representation and an ID, which is kept aside of some container storing
the actual data.
That said, we could of course think about relaxing this requirement. The
rtree taking a ValueType is similar to std::multiset. But in the STL
there is also std::multimap storing std::pair<const Key, T>. If we could
ensure that the geometrical part of the value couldn't be changed by the
user we could implement mutable interators. For instance, mutable
iterators could be enabled only for some specific ValueTypes, e.g.
std::pair<const Box, T>, boost::tuple<const Box, T>, etc. But this could
be not intuitive for the users. An alternative would be to add an rtree
version similar to std::multimap (e.g. rtree_map or soem other name).
Instead of a single ValueType template parameter it could take two:
Indexable and some type T. Then it'd require to insert objects of
ValueType std::pair<const Indexable, T> exactly like the std::multimap.
> ---
>
> My use case is as follows. I'm implementing some point clustering
> algorithms. My point primitive has a 'ClusterID' attribute member, and
> something like a (fat) user-defined boost::any. Because the point is
> not cheap to copy, I'm iterating over nearest neighbours and marking
> the ClusterID in-place using something like this:
>
> //Using Boost version 1.57.0.
> ...
> RTree_t::const_query_iterator it;
> it = rtree.qbegin(boost::geometry::index::satisfies(
> [](const MyPoint &) -> bool { return true; } )
> );
> for( ; it != rtree.qend(); ++it){
> //it->ClusterID = -1; //Compilation error: disregards const.
> const_cast<MyPoint &>(*it).ClusterID = -1;
> }
You should know that the Values can be heavily copied during the
insertion and removal.
Have you considered keeping the points as small as possible and keeping
the rest (boost::any) in some container outside the rtree? In general
using objects containing cold data for indexing is not a good idea
because of increased number of cache misses, so worse performance.
> First: my understanding is that because the spatial coordinates are
> not altered the const_cast is valid. Is this correct?
Yes.
> Second: can something like the back_inserter interface be created that
> won't copy the matching points?
Do you have the query() member function in mind? But instead of copying
the Values into the output iterator (so working like std::copy())
calling some Function for all Values meeting predicates (so working like
std::for_each())?
I wouldn't recommend it but actually you could do it even now by passing
Function/UnaryPredicate into bgi::satisfies() and then into query()
method. This predicate would be called for all Values meeting other
predicates. To prevent copying you could pass some kind of dummy output
iterator (dev_null_iterator). But this code wouldn't be clear. And the
catch is that also in this case the const reference to Value is passed
into the UnaryPredicate taken by the bgi::satisfies(). The reason is the
same, to not allow the user to modify the Indexable part by mistake.
> non-const query_iterators would be
> nice. I don't understand the rationale for, or distinction between,
> query_iterator, spatial_query_iterator, distance_query_iterator, but
> presumably they are all non-const candidates.
The kind of an iterator is not a problem here, all of them could be made
mutable. The problem is, how to design an interface dissallowing the
users to modify an Indexable part of a ValueType object stored in the
rtree index.
But your solution seems to be ok (const_cast). It's the same as if
someone wanted to do a similar thing with std::set. And const_cast is a
nice warning sign.
Regards,
Adam