Can I build a KDTree of pointers to objects?

[Sylvain Bougerel]

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:
>
> //header PlanePoint.h:
> class PlanePoint : blah blah ..
>
> inline bool operator==(PlanePoint const * A, PlanePoint const * B);
>

No! You can't do this. You are defining an` ==' operator on a pointer,
you cannot overload the operator `==' on a pointer. It's not possible.
What you can do is:
class PlanePoint
{
  boll operator(const PlanePoint &b) { ... } // Here the first operand
is the class
}
// Or without the one above:
inline bool operator == (const PlanePoint &a, const PlanePoint &b) {...}
// But you can still compare an object to a pointer, so the following is valid:
inline bool operator == (const PlanePoint &a, const PlanePoint *b) {...}
// You just can't have the pointer as a first operand.

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; }
};

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.

But using set<> to manage pointer is a bad idea, you will leak very
likely, unless you handle desallocation of the pointer very carefully.
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.

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.


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