Hi,

Bruno Lalande wrote:

Hi Adam,

There is also a no-parameter qend() which return a special end_query_iterator which may be compared with arbitrary iterator returned by qbegin() to check if the query has ended. But since it has different type it can't be used in STL algorithms like std::copy().

This sounds a bit unusual. What I've seen done so far is that the same iterator type is used and it simply as a no parameter constructor, and flags itself as end-iterator/default-constructed if constructed this way. Was it really an issue to do like that?

Otherwise, sounds like a useful addition, thanks for that.

The problem is that the Predicates are stored inside the iterator which means that they're a part of the iterator type. To construct the end iterator of the same type the Predicates must also be known. Additionally, the type of this raw iterator can't be defined in the container because it depends on the Predicates expression. And yes a default-constructed iterator is an end iterator. These iterators can be obtained by:

tree.qbegin(/*predicates*/) and tree.qend(/*predicates*/)

For convinience I've added tree.qend() but it returns an iterator of different type.
To allow less experienced users to use those iterators e.g. in a for loop I've defined a type-erased const_iterator_type.

I also think that this is quite complicated and if we found a better solution I'd gladly change the existing one.

For example qbegin() and qend() could return type-erased iterators, then the interface would become like in the STL containers but since memory allocation and virtual methods are involved in the process those iterators are slower.
E.g. on VS2010 those are the times of some queries:

// 1M boxes stored, linear<16>, times of 100k queries
0.920406 seconds - tree.query(B)
0.936006 seconds - std::copy(tree | queried(B))
1.20121 seconds - std::copy(tree.qbegin(B), tree.qend(B))
1.15441 seconds - my_copy(tree.qbegin(B), tree.qend())
1.23241 seconds - boost::copy(std::make_pair(tree.qbegin(B), tree.qend(B)))
1.27921 seconds - type-erased std::copy(tree.qbegin(B), tree.qend(B))
1.21681 seconds - type-erased std::copy(tree.qbegin(B) tree.qend())
1.34161 seconds - type-erased boost::copy(std::make_pair(tree.qbegin(B) tree.qend(B)))
1.23241 seconds - type-erased boost::copy(std::make_pair(tree.qbegin(B) tree.qend()))

// 1M boxes stored, linear<16>, times of 20k queries
0.795605 seconds - tree.query(N)
0.858006 seconds - std::copy(tree.qbegin(N) tree.qend(N))
0.842405 seconds - my_copy(tree.qbegin(N) tree.qend())
0.951606 seconds - type-erased std::copy(tree.qbegin(N)) tree.qend(N))
0.967206 seconds - type-erased std::copy(tree.qbegin(N) tree.qend())

The above code is pseudocode:
- B means intersects(box)
- N means nearest(point, 10)
- to erase a type of an iterator one must convert it to Rtree::const_query_iterator first.
- all calls lack the last output iterator parameter

One possible solution would be the implementation of qbegin() and qend() returning type-erased iterators and e.g. some other methods like qbegin_xxx() and qend_xxx() returning raw Predicates-dependent iterators.

Or maybe do you have some other ideas?

One thing you should probably know is that those raw Predicates-dependent iterators are fat iterators, tree traversing stack is stored inside so they're quite big.

Regards,
Adam