output iterator in find_within_range

[Paul Harris]

2008/7/29 Michael Zillich <zillich at acin.tuwien.ac.at>

> Hello,
>
> It seems to me that one could change in the function _M_find_within_range
>  *__out++ = _S_value(__N);
> to
>  __out = _S_value(__N);
>
> as operator++() has not effect on a back_insert_iterator and operator*()
> simply returns *this.
> At least this is the case for the STL back_insert_iterator.
> Don't know if that would result in any speedup though. Just thought it
> "looks"
> faster :)
>

it must always work with something like a plain array... eg, in fudged
code...


Node nodes[1000];

Node* last_found = find_within_range( blah blah,  &nodes[0] );

this approach would be desirable for cases where the tree has (in this case)
1000 leaves (or at least, couldn't possibly find more than 1000 nodes within
the range - so no danger of overflow but that is up to the programmer to
decide), and would be faster than pushing the nodes into a blank vector.

this would not work without *__out++


of course, a better design would be

vector<Node> nodes(1000);
nodes.reserve(1000); // or remove 1000 above and use reserve
find_within_range( blah blah, back_inserter(nodes) );

but sometimes the programmer has no choice in where the data is written to.


note also that if there is no effect, then the compiler will optimise away
(remove) the extra work.


if you are itching for something to do to kdtree, i have some changes
pending since last year that need reviewing...


see ya
Paul
-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://lists.alioth.debian.org/pipermail/libkdtree-devel/attachments/20080730/baec8c55/attachment.htm