Can I build a KDTree of pointers to objects?

[Eric Fowler]

On Mon, Apr 28, 2008 at 8:33 PM, Sylvain Bougerel <
sylvain.bougerel.devel at gmail.com> wrote:

> Sorry this comes a little late:
>
> On Fri, Apr 25, 2008 at 12:16 PM, Eric Fowler <eric.fowler at gmail.com>
> wrote:
> > I have a toy app that is storing a set<> of pointers to a PlanePoint
> object,
> > itself little more than a wrapper for {int x, y;}.
> >
> > Since I am storing pointers I want to store pointers in my KDTree too.
> With
> > that in mind, I wrote this:
> >
>
> Now, in the KD tree, as Paul explained in this mail, we use an
> accessor to get the data, we do not directly manipulate the element.
> So you need to define the accessor just as Paul told you.
>
> May be, according to your example, it will look like smth like this:
>
> struct accessor {
>   typedef int result_type;
>   int operator () (const PlanePoint *e, int k) const { return
> (k==0)?e->x, e->y; }
> };


I had done something like this at some point and was still getting
errors.But I have made progress and shall revisit it.


>
> Okay I haven't tried. Of course, as Paul says you shouldn't move your
> PlanePoint around in memory. But if you're using pointers in your
> set<> as well, I don't think there is a danger.
>


> Why just not using a pointer at all? Your object is just a few `int'?
> You will gain in performance when you need to do computation (cause it
> does not need to access the memory of the pointer) and you will also
> gain in ease with your implementation. You might consume more memory,
> but not necessarily, because you will not leak memory with copies of
> your plane object.


Hmm, that is an idea. I was thinking of something like this:

class MyPoint
{
public: int x, y;

char * data;
int more_data;
double still_more_data;
bool by_now_you_get_the_idea;
};

...and did not want to duplicate all that stuff in the kdtree, especially
since I had reasons for storing the structs elsewhere (need to lookup on
different criteria, effectively a different index).

So I could just use the x,y, and a pointer to the MyPoint in a new struct
that is made just for KDTree-ability, and store and search over them. This
is a little redundant but the coding is simpler and memory-wise only a
little more costly.

But I think I will try to make the pointers work, mainly because that sort
of thing is my style, and I am getting too old to change =-)


>
>
> Also there is one side effect that Paul did not mention: you cannot
> change the coordinate of your PlanePoint once they are inside the
> tree. It's easy to overlook this with pointers because it can be done.
> But you would completely invalidate your tree. You would not get
> memory corruption, but it will just return weird results when you send
> a query.

Yes, I intend to be cautious. I understand the procedure is: (1) remove
point from KDTree; (2) change coordinates; (3) re-insert into KDTree; (4)
optimiZe() the tree.

>
>
>
> I recommend against the use of pointers. It does not mean that
> libkdtree should not support it. But it's generally a bad idea.
>
> Sylvain
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://lists.alioth.debian.org/pipermail/libkdtree-devel/attachments/20080428/a64dd6cd/attachment.htm